Shortest’ path’ni topish uchun Dijkstra algoritmi
Dijkstra’ning algoritmi graph’dagi bir vertex’dan boshqa har bir vertex’ga qisqa yo’lni topish uchun ishlatiladi.
Shortest path – digraph’da qisqa yo’llar haqida
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 topish uchun Prim algoritmi
Minimum spanning tree’ni topishning yana bir klassik algoritmlaridan biri – Prim algoritmi ishlash tartibi quyidagicha…
Minimum spanning tree’ni topish uchun Kruskal algoritmi
Graph’dagi minimum spanning tree’ni topishning klassik algoritmlaridan biri – Kruskal algoritmi g’oyasi tushunishga oson. Uning ishlash tartibi…
Greedy algoritmi
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.
PHP dasturchi bilishi kerak bo’lgan Javascript hususiyatlari
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
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.
Directed graph’da kuchli bog’langan komponentlar
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.
Yo’qotishlar bahosi
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.
Topological sort
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.