“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Chiziqsiz ma’lumotlar tuzilmasini mantiqiy tasvirlash
Qo’shma matrisa
Ko’rsatkichli bog’langan ro’yxat
Masalan, qo’shma matrisa orqali ifodalab olish
1
2
3
4
0
1
1
0
0
0
0
1
0
1
0
0
0
0
1
0

Yo’naltirilmagan graflar

• Yo’naltirilmagan graf G=(V, E) – bu tugunlar va ularni birlashtirib turuvchi yoylar dan tashkil topgan tuzilma xisoblanadi. Undagi ixtiyoriy yoy teskarisi bilan teng va u yo’naltirilmagan yoy deyiladi.
• Agar bo’lsa, u xolda u va v tugunlar qo’shni deyiladi va e yoy esa insident deyiladi.
• Tugunlarning chiqish darajasi deb u bilan qo’shni tugunlar soniga aytiladi.
• Chiqish darajasi 0 ga teng bo’lgan tugunlar izolyasiyalangan tugun deyiladi.

yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi.

yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi.

Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish algoritmi

Grafni ko’rikdan o’tkazish (Graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni ko’rib chiqish prosedurasidir.

Ikkita usuli mavjud:

• Tubiga qarab(Depth-First Search – DFS)
• Eniga qarab(Breadth-First Search – BFS)

Yo’naltirilmagan graflarni ko’ruvdan o’tkazishda ma’lumotlarni saqlash uchun bironta konteyner, navbat yoki stekdan foydalaniladi.

Navbat yordamida ko’ruvdan o’tkazishda graflar eniga qarab ko’ruvdan o’tkaziladi
1
2
3
4
6
7
5
8

• Ko’ruvdan o’tkazishni ixtiyoriy bir v tugundan boshlaymiz

2.. Uni konteynerga tashlaymiz.
Queue q;
q.push(v);
3. navbat bo’shamaguncha
While(!q.empty())

• Navbatdan tugunni chiqaramiz va uni ko’ruvdan o’tkazilganligini belgilaymiz. mark(current=q.pop());

• Barcha insident yoylarni tekshiramiz

• Agar yoy ko’ruvdan o’tmagan u tugunga olib borsa, uni navbatga joylaymiz. q.add(u);

• Акс холда агар ёй навбатга киритилган ёки кўрилган тугунга олиб борса, хеч нима қилмаймиз.

Graf:
1
2
4
5
7
8
6
3
Grafni eniga qarab ko’rishda navbat ishlatilishi
Agar oraliq tuzilma sifatida navbat qo’llanilsa, grafni eniga qarab ko’riladi.
1
2
3
4
6
7
5
8
Graf :
1
Eniga qarab qo’ruv daraxtini yaratsa xam bo’ladi, agar xar bir to’g’ri yoylarni belgilab olinsa.
1
2
3
4
5
6
7
8
1
Navbat:
1
2
1
1
4
5
5
2
3
4
5
6
7
8
4
2
3
5
7
6
8
Tubiga qarab ko’rishda stek qo’llanilishi
Agar oraliq tuzilma sifatida stek qo’llanilsa, grafni tubiga qarab ko’riladi.
1
2
3
4
6
7
5
8
Graf :
1
5
8
7
6
4
3
2
Tubiga qarab qo’ruv daraxtini yaratsa xam bo’ladi, agar xar bir to’g’ri va teskari yoylarni belgilab olinsa.
1
2
3
4
5
6
7
8
1
1
1
5
5
7
6
4
4
3
1
Stek :
2
3
4
5
6
7
8