Witam.
Mam do zaprogramowania (java) graf metodą Hopcrofta-Tarjana, czy jest ktoś w stanie powiedzieć mi ogólnie jak sie do tego zabrać i jak on powinien działać? Nie bardzo jestem w stanie przekopać się przez angielskie dokumentacje i artykuły a w polskich publikacjach nie bardzo ciężko o konkretne dane. Dodaje część polecenia:
"W celu rozwiązania zadania należy wykorzystać strukturę danych do reprezentacji grafu zaproponowaną 40 lat temu przez John’a
Hopcrofta i Roberta Tarjana (w pracy Efficient Algorithm for Graph Manipulation, CACM, 1973, vol 16, no 6). Niech G=(V,E) będzie grafem
zorientowanym, w którym V reprezentuje zbiór wierzchołków etykietowanych kolejnymi liczbami 1,2,…n gdzie n=|V| oraz E definiuje zbiór
m=|E| krawędzi grafu reprezentowanych przez pary (u,v) gdzie u ∈ {1,2….n} oraz v ∈ {1,2….n}.Zaproponowane metoda opisu grafu oparta jest na strukturach listowych z użyciem dwóch tablic next[1, …, n, n+1, …, n+2m] oraz
head[n+1, n+2,…., n+2m]. Bezpośrednie odwołania do elementów struktury są niedozwolone. Dostęp winien odbywać się wyłącznie z użyciem
odpowiednio zaimplemntowanych metod ( np. przykładowo getVertex(…), getEdge(…), getNextEdge(…) )"
Kompletnie nie mam pojęcia co to za struktury listowe ani do czego służą. Każda porada się przyda. Dzięki