Graphalgorithmen

Die auf den folgenden Seiten verwendete Java-Implementation von gerichteten, unbewerteten Graphen stützt sich auf ein Array von Listen, welches in effizienter Weise das Abarbeiten der Nachbarn eines Knotens mit folgenden Methoden erlaubt:

void    reset         (int x); // setzt die Adjazenzliste fuer x zurueck 
boolean moreNeighbors (int x); // testet, ob es weitere Nachbarn von x gibt
int     nextNeighbor  (int x); // liefert den naechsten Nachbarn von x

Die Klasse Graph_IO wurde definiert, um Graphen vom Benutzer einzulesen und ihre momentane Struktur anzuzeigen.

Die Klasse Graph_Tiefensuche führt auf einem gerichteten Graphen unter Verwendung eines Kellers eine Tiefensuche durch und vergibt Nummern an Knoten in der Reihenfolge, in der sie besucht werden. Bei nicht zusammenhängenden Graphen muß dazu die Suche mehrfach gestartet werden.

Die Klasse Graph_TopoSort führt auf einem gerichteten Graphen eine sogenannte topologische Sortierung durch und versucht eine Knoten-Nummerierung f : V $\rightarrow \Bbb{N}$ zu finden, die mit den Kantenrichtungen kompatibel ist, d.h. $(x,y) \in E \Rightarrow f(x) < f(y)$.

In der Klasse Graph_Test wird ein Graph eingelesen, angezeigt und die beiden Nummerierungen ermittelt.

Source: Graph.java     JavaDoc: Graph.html     Source: Graph_IO.java     JavaDoc: Graph_IO.html     Source: Graph_Tiefensuche.java     JavaDoc: Graph_Tiefensuche.html     Source: Graph_TopoSort.java     JavaDoc: Graph_TopoSort.html     Source: Graph_Test.java     JavaDoc: Graph_Test.html     Applet: