|
Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish
|
| bet | 64/163 | | Sana | 16.01.2024 | | Hajmi | 18,84 Mb. | | #138868 |
Bog'liq O zbekiston respublikasi oliy va o rta maxsus ta lim vazirligi tYo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish.
Reja
Yo’naltirilmagan graflar.
Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish algoritmi.
Minimal narxli daraxtlar skeleti.
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.
E’tibor qilish kerakki, yo’naltirilgan graflarda ilmoqli yoy bo’lishi mumkin, yo’naltirilmagan graflarda esa bunday yoy bo’lmaydi. Masalan, quyidagi rasmda yo’naltirilgan G1=(V1, E1) grafda V1={ a,b,c,d}tugunlar va E1={ (a,b), (a,c), (b,b), (b,d), (d,a)} yoylar berilgan bo’lsin. Unda G2=(V2, E2)yoy ilmoq xisoblanadi va uning kirish darajasi 2 ga, chiqish darajasi xam 2 ga teng. G2 Grafda esa e tugunning darajasi 0 ga teng va izolyasiyalangan.
1-rasm. Yo’naltirilgan G1 va yo’naltirilmagan G2 graflar.
Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish algoritmi
Yo’naltirilmagan graflarni ko’ruvdan o’tkazishda ma’lumotlarni saqlash uchun bironta konteyner yoki stekdan foydalaniladi. Konteyner yordamida ko’ruvdan o’tkazishda graflar eniga qarab ko’ruvdan o’tkaziladi. Uni algoritmini ko’rib chiqamiz. Ushbu graf berilgan bo’lsin.
Ko’ruvdan o’tkazishni ixtiyoriy bir v tugundan boshlaymiz.
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());
Barchainsident yoylarni tekshiramiz.
Agar yoy ko’ruvdan o’tmagan u tugunga olib borsa, uni navbatga joylaymiz. q.add(u);
Aksxoldaagaryoynavbatgakiritilganyokiko’rilgan tugunga olib borsa, xech nima qilmaymiz.
2-rasm. Navbat yordamida grafni ko’ruvdan o’tkazish etapi.
|
| |
