Teg

#acyclic graph

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