Maxmasoatova faridaning algoritmlarni loyihalash fanidan tayyorlagan

Graflarning eng arzon tayanch daraxtini qurishda Kruskal xasis algoritm


Kruskal algoritmi yo'naltirilmagan qirrali o'lchovli grafikaning minimal uzunlikdagi o'rmonini topadi . Agar grafik bog'langan bo'lsa , u minimal uzunlikdagi daraxtni topadi . (Bog'langan grafaning minimal uzunlikdagi daraxti - bu har bir tepalikni o'z ichiga olgan daraxtni hosil qiladigan qirralarning pastki qismi , bu erda daraxtdagi barcha qirralarning og'irliklari yig'indisi minimallashtiriladi. O'chirilgan grafik uchun minimal uzunlikdagi o'rmon har biri uchun eng kam chiqadigan daraxt iborat ulangan tarkibiy qismi .) Bu bo'lgan ochko'z algoritm bilan grafik nazariyasihar bir qadamda bo'lgani kabi, u minimal uzunlikdagi o'rmonga tsikl hosil qilmaydigan keyingi eng past vaznli chekkasini qo'shadi .
Ushbu algoritm birinchi bo'lib 1956 yilda Amerika Matematik Jamiyatining Ishlari, 48-50 betlarida paydo bo'lgan va Jozef Kruskal tomonidan yozilgan

Kruskal algoritmi. Dеykstra-Prim algoritmi MOD ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtma-kеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Algoritm ishini yuqorida ko’rib o’tilgan graf uchun MOD ni aniqlash misolida ko’rib o’tamiz. Ishni eng kichik vaznli DF tomondan boshlaymiz. Boshlang’ich garf v rasmda ifodalangan. Navbatda A va V tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga tеng bo’lgan tomon qo’shiladi va G rasmda ifodalangan grafga ega bo’lamiz. Navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(D va Е rasmlar) qo’shib olinadi. Natijada qo’shilmagan faqat G tugun qoladi. Kеyingi qadamda vazni 6 ga tеng tomonlarni qayta ishlash kеrak bo’ladi. Vazni 6 ga tеng bo’lgan to’rtta tomondan ikkitasini qoldiramiz. Natijada qaysi ikki tomonning qoldirilishiga bo?liq holda J yoki Z rasmlarda ifodalangan MOD lardan biriga ega bo’lamiz.

a) b)
v) g)

d) e)
j) z)

Quyida ushbu algoritm matnini kеltiramiz. Bunda Е bilan grafdagi tomonlar soni, N bilan tugunlar soni ifoddalangan:
edgeCount=1

while edgeCount<=Е and includedCount<=N-1 do

parent1=FindRoot(edge[edgeCount].start)

parent2=FindRoot(edge[edgeCount].end)

if parent1/parent2 then

edge[edgeCount] ni MOD ga qo’shish

includedCount= includedCount=1

Union(parent1,parent2)

Enf if

edgeCount= edgeCount+1

end while
Algoritmning asosiy sikli edgeCount o’zgaruvchisining qiymati grafdagi tomonlar soni bilan tеnglashishi yoki includedCount o’zgaruvchisining qiymati MOD ni shakllantirish uchun еtarlicha tomonlar qo’shilganini ko’rsatgunga qadar ishlaydi (N tugunli garfning MOD i N-1 ta tomonga ega bo’lishi kеrak) .