Drzewo najmniejszych odległości w grafie skierowanym acyklicznym

Question

Cześć, mamy problem z zadaniem odnośnie MST (minimalnego drzewa rozpinającego graf). Mamy do tego dwa algorytmy - Kruskala i Prima, oba ze złożonością obliczeniową O(E logV), gdzie E - lb. krawędzi, V - lb. wierzchołków.

 

Moje pytanie brzmi jak uzyskać lepszą złożoność dodając założenie, że graf jest acykliczny?

 

Będę wdzięczny za wszelkie przemyślenia, bo na razie wiem tyle że tych algorytmów nie wykorzystamy, bo w algorytmie Kruskala samo sortowanie wg. wagi to (E logV) a tego nie ominiemy, co do Prima tam nie ma za bardzo wykorzystać tej własności. Jakieś pomysły?

Answer 1

Istnieją szybsze algorytmy, dla różnych specjalnych przypadków. Nie wiedziałem nic dla grafów acyklicznych, ale chyba warto rzucić okiem:

https://en.wikipedia.org/wiki/Minimum_spanning_tree