Algorytmy i struktury danych · Middle · Pytanie 65 z 75
Który algorytm znajduje minimalne drzewo rozpinające, dodając najtańsze krawędzie niezamykające cyklu?
- 1Sortowanie topologiczne
- ✓Poprawna odpowiedź: Algorytm Kruskala
- 3Algorytm Dijkstry
Wyjaśnienie
Kruskal sortuje krawędzie po wadze i za pomocą union-find pomija krawędzie łączące wierzchołki z tej samej składowej. Dijkstra liczy najkrótsze ścieżki, a to inny problem.