-jadval. Pryufer kodi orqali daraxtni tiklash ketma-ketligi

Download 4,61 Mb. Pdf ko'rish
bet	74/111
Sana	18.05.2024
Hajmi	4,61 Mb.
	#241929

1 ... 70 71 72 73 74 75 76 77 ... 111

Bog'liq
ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARI

8-jadval.
Pryufer kodi orqali daraxtni tiklash ketma-ketligi
Qadam
1
2
3
4
5
6
Kod satri
1
4
1
6
6
Antikod satri
2
3
3
5
5
4
7
7
5
1
7
5
5
7
7
6
7
Qirra qoʻshish
{1;2} {4;3} {1;4} {6;1} {6;5} {6;7 }
Qirralarning roʻyxatini tahlil qilib, asl daraxt olinganligiga ishonch
hosil qilamiz. E‘tibor bering, qirralarning tartibi avvalgi jadvaldagi kabi.
4-misol.
Pryufer kodini yaratish vazifasining oldida kodlangan
daraxtni tiklash vazifasi ham mavjud. Daraxtlarni qayta qurish
algoritmini quyidagi shartlar bilan koʻrib chiqamiz: kirish sifatida
Pryufer kodini ifodalovchi raqamlar (uchlar) ketma-ketligi, natijada
daraxt qirralarining roʻyxati boʻladi.
Kod hal qilish algoritmini batafsil koʻrib chiqamiz. Koddan
tashqari, bizga grafning barcha uchlari roʻyxati kerak. Biz bilamizki,
Pryufer kodi n-2 ta uchlardan iborat, bu yerda n - grafdagi uchlar soni.
Ya‘ni kodlangan daraxtdagi uchlar sonini kodning kattaligi boʻyicha
aniqlashimiz mumkin.
Natijada,
algoritmning
boshida
bizda
Pryuferning
oʻlchamdagi kodlari va grafdagi barcha uchlar qatori mavjud: [1 ... n].
Keyin quyidagi protsedura
marta takrorlanadi: Pryufer kodini oʻz
ichiga olgan massivning birinchi elementi olinadi va kod bilan massivda
boʻlmagan eng kichik uchni qidirish daraxt uchlari bilan massivda
amalga oshiriladi. Topilgan uch va Pryufer kodi bilan massivning joriy
elementi daraxtning qirrasini tashkil qiladi. Ushbu uchlar tegishli
massivlardan olib tashlanadi va yuqoridagi protsedura kodli qator
elementlari tugamaguncha takrorlanadi. Algoritm oxirida graf uchlari

117
bilan massivda ikkita uch qoladi; ular daraxtning soʻnggi uchini tashkil
qiladi. Natijada biz grafning kodlangan barcha qirralarining roʻyxatini
olamiz.
2-misolda olingan Pryufer kodi yordamida daraxtni tiklaylik.

Birinchi qadam
Pryufer kodi: 1 5 2 6 6 2 1 3
Daraxtlar uchlari massivi: 1 2 3 4 5 6 7 8 9 10
Pryufer kodida mavjud boʻlmagan minimal uch 4 ga teng
Qirralar roʻyxati: 1 4
Ikkinchi qadam
Pryufer kodi: 1 5 2 6 6 2 1 3
Daraxtlar uchlari massivi: 1 2 3 4 5 6 7 8 9 10
Pryufer kodida mavjud boʻlmagan minimal uch 7 ga teng
Qirralarning roʻyxati: 1 4, 5 7
Uchinchi qadam
Pryufer kodi: 1 5 2 6 6 2 1 3
Daraxtlar uchlari massivi: 1 2 3 4 5 6 7 8 9 10
Pryufer kodida mavjud boʻlmagan minimal tepalik 5 ga teng
Qirralarning roʻyxati: 1 4, 5 7, 2 5
Toʻrtinchi qadam
Pryufer kodi: 1 5 2 6 6 2 1 3
Daraxtlar uchlari massivi: 1 2 3 4 56 7 8 9 10
Pryufer kodida mavjud boʻlmagan minimal tepalik 8 ga teng
Qirralarning roʻyxati: 1 4, 5 7, 2 5, 6 8
Beshinchi qadam
Pryufer kodi: 1 5 2 6 6 2 1 3
Daraxtlar uchlari massivi: 1 2 3 4 56 7 8 9 10
Pryufer kodida mavjud boʻlmagan minimal vertex 9 ga teng
Qirralarning roʻyxati: 1 4, 5 7, 2 5, 6 8, 6 9

118
Oltinchi qadam
Pryufer kodi: 1 5 2 6 6 2 1 3
Daraxtlar uchlari massivi: 1 2 3 4 56 7 8 9 10
Pryufer kodida mavjud boʻlmagan minimal vertex 6 ga teng
Qirralarning roʻyxati: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6
Yettinchi qadam
Pryufer kodi: 1 5 2 6 6 2 1 3
Daraxtlar uchlari massivi: 1 2 3 4 5 6 7 8 9 10
Pryufer kodida mavjud boʻlmagan minimal tepalik 2 ga teng
Qirralarning roʻyxati: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2
Sakkizinchi qadam
Pryufer kodi: 1 5 2 6 6 2 1 3
Daraxtlar uchlari massivi: 1 2 3 4 5 6 7 8 9 10
Pryufer kodida mavjud boʻlmagan minimal tepalik 1 ga teng
Qirralarning roʻyxati: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1
Algoritmni yakunlash
Pryufer kodi: 1 5 2 6 6 2 1 3
Daraxtlar uchlari massivi: 1 2 3 4 5 6 7 8 9 10
Pryufer kodida mavjud boʻlmagan minimal tepalik 1 ga teng
Qirralarning roʻyxati: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1, 3 10

Download 4,61 Mb.

1 ... 70 71 72 73 74 75 76 77 ... 111

Download 4,61 Mb.

Pdf ko'rish