Algorytmy i struktury danych · Senior · Pytanie 34 z 75
Co oblicza algorytm Tarjana lub Kosaraju?
- 1Najkrótsze ścieżki z ujemnymi wagami krawędzi
- 2Maksymalny przepływ między dwoma wierzchołkami
- ✓Poprawna odpowiedź: Silnie spójne składowe grafu skierowanego
Wyjaśnienie
Silnie spójna składowa to grupa, w której z każdego wierzchołka da się dojść do każdego innego. Oba algorytmy działają w O(V + E) na DFS. Ściągnięcie takich składowych zamienia dowolny graf skierowany w DAG, co przydaje się w analizie zależności.