Algorytm Hopcrofta-Tarjana

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

xluzakx napisał(a):

czy jest ktoś w stanie powiedzieć mi ogólnie jak sie do tego zabrać

Na początek trzeba poczytać co to jest lista. Potem co to jest graf.

-.- Pisalem juz grafy, wiem co to listy. Chodzi mi o kontretny przyklad i konkretne zastosowanie.

xluzakx napisał(a):

-.- Pisalem juz grafy, wiem co to listy. Chodzi mi o kontretny przyklad i konkretne zastosowanie.

http://pl.wikipedia.org/wiki/Reprezentacja_grafu#Reprezentacja_przez_list.C4.99_s.C4.85siedztwa

Czyli te tablice next i head maja za zadanie szukac wierzcholkow z ktorych krawedz wchodzi oraz wychodzi, tak?

xluzakx napisał(a):

Czyli te tablice next i head maja za zadanie szukac wierzcholkow z ktorych krawedz wchodzi oraz wychodzi, tak?

Podaj definicję listy.

Nie przyszedlem na to forum po sprawdzenie mojej wiedzy tylko o rade, jesli nie masz nic wiecej do dodania to dziękuje za pomoc.

1 2 3 4 ... n [next]
2 ...
3 ....
4 ...
...
n
[head]

moze o to chodzi?

xluzakx napisał(a):

Nie przyszedlem na to forum po sprawdzenie mojej wiedzy tylko o rade, jesli nie masz nic wiecej do dodania to dziękuje za pomoc.

Czytam to co piszesz i na tej podstawie wnioskuję co jest najlepsze dla Ciebie, jak nie chcesz, to nie ma problemu... mi za korepetycje nikt nie płaci.

xluzakx napisał(a):

1 2 3 4 ... 5 [next]
2 ...
3 ....
4 ...
...
n
[head]
moze o to chodzi?

Nie wiem co to jest, na pewno nie lista o którą prosiłem.

Jeśli wiesz co to jest lista, to ją przytocz. Jeśli nie, to wróć do materiału o listach.

Lista to struktura ktora zawiera glowe i kolejne elementy, ewentualnie glowe i ogon jesli dwukierunkowa.

xluzakx napisał(a):

Lista to struktura ktora zawiera glowe i kolejne elementy, ewentualnie glowe i ogon jesli dwukierunkowa.

Dobrze, ale jeszcze trzeba coś dodać. Jak wyglądają elementy listy?

No połączone są liniowo, kazdy wskazuje na kolejny.

xluzakx napisał(a):

No połączone są liniowo, kazdy wskazuje na kolejny.

Nie. Elementy na nic nie wskazują. Elementy zawierają pole które wskazuje (np.) na element następny.
Co zawierają poza tym polem?

To co mają zawierać, w tym przypadku pewnie numer wierzcholkow grafu albo obiekt typu wezel.

xluzakx napisał(a):

To co mają zawierać, w tym przypadku pewnie numer wierzcholkow grafu albo obiekt typu wezel.

Wszystko się zgadza, więc czego nie wiesz? O co pytasz?

Reprezentacja grafu w postaci list sąsiedztwa polega na tym, że każdy
węzeł v_i grafu ma listę. Każdy element tej listy zawiera jakąś informację o
węźle v_j z którym węzeł v_i jest połączony. Czyli cała lista zawiera informację o
wszystkich węzłach v_j z którymi połączony jest węzeł v_i. Informacją tą
mogą być wskaźniki, mogą być indeksy jeśli trzymamy węzły w tablicy, mogą być
pary indeksów jeśli węzły trzymamy w dwuwymiarowej tablicy, itd.

Pytam o to co to sa tablica head i tablica next.

Czy dobrze rozumiem ze tablica head to tablica ze wszystkimi wezlami, natomiast tablica next to lista podlaczona do kazdego elementu head osobno ktora zawiera np. indeksy wezlow z ktorym dany element head sie laczy? Moim problemem jest interpretacja polecenia.

xluzakx napisał(a):

Pytam o to co to sa tablica head i tablica next.

Czy dobrze rozumiem ze tablica head to tablica ze wszystkimi wezlami, natomiast tablica next to lista podlaczona do kazdego elementu head osobno ktora zawiera np. indeksy wezlow z ktorym dany element head sie laczy? Moim problemem jest interpretacja polecenia.

Brzmi strasznie dziwnie, może ktoś coś pomylił, nie wiem, ale na pewno tablica to nie lista.

Ja bym zrobił to np. tak:

struct Neighbor {
Node *node;
Neighbor *next;
}

struct Node {
Info info; // informacje o węźle
Node *next; // następny węzeł grafu
Neighbor *list;
}

Przykład przeszukania wszystkich węzłów grafu:

Node *node = graph;
while( node ) {
print node->info;
node = node->next;
}

Przykład przeszukania listy sąsiedztwa węzła 'node':

Neighbor *neighbor = node->list;
while( neighbor ) {
print neighbor->node->info;
neighbor = neighbor->next;
}

Ale to nie jest jedyna droga...

Możesz mieć węzły w tablicy:
Node nodes[SIZE];
i wtedy Node nie musi mieć pola next, a przegląda się tak:

for( i=0 ; i<N ; i++ )
print nodes[i].info;

Można zrobić jeszcze inaczej:

struct Node {
Info info;
int start;
int end;
};

struct Edge {
int node;
};

struct Graph {
Node nodes[SIZE_N];
Edge edges[SIZE_E];
};

Graph graph;

Wtedy przejrzenie wszystkich węzłów sąsiednich węzła j będzie wyglądało tak:
for( i = graph.nodes[j].start ; i<graph.nodes[j].end ; i++ )
print graph.nodes[ graph.edges[i].node ].info

Ale za to operacja usuwania będzie problematyczna.

xluzakx napisał(a):

Pytam o to co to sa tablica head i tablica next.

Czy dobrze rozumiem ze tablica head to tablica ze wszystkimi wezlami, natomiast tablica next to lista podlaczona do kazdego elementu head osobno ktora zawiera np. indeksy wezlow z ktorym dany element head sie laczy? Moim problemem jest interpretacja polecenia.

Masz może Cormena? Strona 560, podsumowanie do rozdziału wprowadzającego o grafach:
"Hopcroft i Tarjan byli zwolennikami użycia list sądziedztwa"
W poprzedniej części rozdziału jest przykład reprezentacji listowej. Główna idea tej
reprezentacji jest taka sama jak wyżej dałem przykłady.