Teg

#directed 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 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