Dasturchi, frilanser, gik va introvert
Biz o’tgan mavzularda ko’rib o’tganimiz, minimum spanning tree – edge’lari weight’ga ega undirected graph’dagi barcha vertex’larni o’z ichiga olgan qisqa yo’lni topishga bag’ishlangan edi. Edge-weight’li directed graph uchun esa shortest path (qisqa yo’l) algoritmlari bilan tanishib chiqamiz.
Minimum spanning tree’ni topishning yana bir klassik algoritmlaridan biri – Prim algoritmi ishlash tartibi quyidagicha…
Graph’dagi minimum spanning tree’ni topishning klassik algoritmlaridan biri – Kruskal algoritmi g’oyasi tushunishga oson. Uning ishlash tartibi…
Minimum spanning tree (MST) algoritmlarini boshlashdan avval biz ular uchun umumiy algoritm – Greedy algoritmi nazariyasini ko’rib chiqamiz. Greedy har bir qadamda optimal variantni tanlab, muammoni yechishning optimal yo’lini topishga urinadi.
PHPdan keyin Javascriptda (Jquery emas) kod yozishni boshlaganimda tilning ba’zi o’ziga xosliklari men uchun yangilik bo’lgan. Quyida ularni tushuntirishga harakat qilaman.
Minimum spanning tree (MST) – undirected graph’dagi barcha o’zaro bog’langan vertex’larni o’z ichiga olgan (spanning) va aylana bo’lmagan (acyclic) sub-graph’lar ichidan minimum weight’li sub-graph.
Kuchli bog’langan komponentlar (strongly connected components, SCC) connected components’ning directed graph uchun mo’ljallangan ko’rinishi bo’lib, yagona farqi – strongly connected components’da vertex’lar ikki taraflama bog’langan bo’lishi kerak.
Taylanddagi ekspatlar orasida yaqin ikki oy ichidagi muhokamalardan biri – amerikalik o’qituvchining Koh Chang orolidagi resortlardan birida bo’lib, yomon baho qo’ygani uchun, tuhmat qilish ayblovi bilan sudga berilgani bo’ldi.
Biz o’tgan graph masalalarida asosan undirected graph’larni ko’rib chiqdik. Aslida undirected graph directed graph’dan kodda ifodalanganda bor yo’g’i graph’dagi barcha vertex’larning ikki tomonlama (ikki yo’nalishli) bog’langani bilan farq qiladi. Shuning uchun undirected graph masalalaridagi yechimlar yoki algoritmlar direct graph uchun ham mos kelishi mumkin.
Kenigsberg (Königsberg, hozirgi Kaliningrad) shahridagi yetti ko’prikni qanday qilib bir ko’prikga ikki marta chiqmasdan bosib o’tish – qadimiy matematik masalalardan biri bo’lib, birinchi marta 1736-yilda Leonard Eyler tomonidan yechilgan. Eyler har bir ko’prikdan faqat bir marta foydalanib barcha ko’priklarni aylanib chiqish imkonsizligini isbotlab bergan.