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
N zu finden, die mit
den Kantenrichtungen kompatibel ist,
d.h.
(x, y)
E
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: