Implementation für gerichtete Graphen durch Adjazenzlisten

Jeder Knoten der Klasse Vertex enthält eine Liste von Kanten; jede Kante der Klasse Edge besteht aus Kosten und Zielknoten. Die Klasse Graph realisiert den Graph als Assoziation von Knotennamen und Knoten. Die Klasse GraphIO liest einen Graph aus einer Datei ein und zeigt seine Adjazenzlisten an. Die Klasse Result enthält Routinen zum Anzeigen einer Lösung, welche von dem jeweiligen Algorithmus in den Arbeitsvariablen der Knoten hinterlegt wurde. Die Klasse GraphTest.java liest einen gerichteten Graphen ein und wendet verschiedene Graphalgorithmen darauf an.

Source: Vertex.java     JavaDoc: Vertex.html     Source: Edge.java     JavaDoc: Edge.html     Source: Graph.java     JavaDoc: Graph.html    

Source: GraphIO.java     JavaDoc: GraphIO.html    

Source: Result.java     JavaDoc: Result.html    

Source: GraphTest.java     JavaDoc: GraphTest.html     Applet:

gerichteter, bewerteter Graph:
gezeigt sind Knotennamen und Kantenkosten

Eingabedatei graph.dat mit Graphbeschreibung

A B 50
A C 25
A D 10
B E 85
B F 20
C B 15
C D 10
C E 60
E C 25
F E 10

von GraphTest.java erzeugte Ausgabe result.dat

Adjazenzlisten des Graphen:

(E,C)25.0  
(F,E)10.0  
(A,B)50.0  (A,C)25.0  (A,D)10.0  
(B,E)85.0  (B,F)20.0  
(C,B)15.0  (C,D)10.0  (C,E)60.0  

Traversierungsreihenfolge:
D erhaelt Nr. 0
E erhaelt Nr. 1
F erhaelt Nr. 4
A erhaelt Nr. 5
B erhaelt Nr. 3
C erhaelt Nr. 2

Graph kann nicht topologisch sortiert werden

Der kuerzeste Weg (mit Gesamtkosten 70.0) lautet: 
A -> C -> B -> F -> E

Graph hat keinen Hamiltonkreis