Kategoriya

Algoritmlar

Noyabr 25, 2020by Sherzod Shermukhamedov

Weight'ga ega DAGlarda shortest path'ni topish

Endi biz DAGlar (directed acyclic graph) uchun shortest path'ni topishni ko'rib chiqamiz. Aslida DAGlar uchun Dijkstra'ning algoritmi ham ishlayveradi, ammo bizdagi graph'ning acyclic, ya'ni aylanasi yo'q ekanligini bilar ekanmiz, bu bizga shortest path'ni topish ishini yengillashtiradimi?

Noyabr 24, 2020by Sherzod Shermukhamedov

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.

Noyabr 19, 2020by Sherzod Shermukhamedov

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.

Noyabr 18, 2020by Sherzod Shermukhamedov

Minimum spanning tree'ni topish uchun Prim algoritmi

Minimum spanning tree'ni topishning yana bir klassik algoritmlaridan biri - Prim algoritmi ishlash tartibi quyidagicha...

Noyabr 17, 2020by Sherzod Shermukhamedov

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...

Noyabr 16, 2020by Sherzod Shermukhamedov

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.

Noyabr 15, 2020by Sherzod Shermukhamedov

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.

Noyabr 14, 2020by Sherzod Shermukhamedov

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.

Noyabr 13, 2020by Sherzod Shermukhamedov

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 yechim

Noyabr 12, 2020by Sherzod Shermukhamedov

Kenigsbergning yetti ko'prigi

The-Koenigsberg-bridge-problem-a-seven-bridges-of-Koenigsberg-b-graph-representation

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