Witam!
Mam, może troche głupie pytanie, ale:
Jak zrobić graf transponowany z listy sąsiedztwa w czasie O(V+E)?
Cormen mówi, że można to zrobić w takim czasie, jednak ja potrafię wymyślić tylko algorytm działający w czasie O(V * E).
0
0
Przechodzisz przez listę krawędzi w każdym wierzchołku. Każdą taką krawędź dodajesz w nowym grafie na początek listy krawędzi w docelowym wierzchołku i voila. V+E (raz przez wierzchołki, raz przez krawędzie, których jest w sumie E)