prev up next

Previous: Graphalgorithmen für Adjazenzmatrizen Up: Graphen Next: Traversieren von Graphen

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
Hamburg Bremen  121
Hamburg Flensburg   157
Hamburg Hannover    152
Hamburg Berlin  289
Flensburg   Hamburg 157
Bremen  Hamburg 121
Bremen  Osnabrueck   126
Osnabrueck   Bremen  126
Osnabrueck   Muenster 61
Muenster Osnabrueck   61
Muenster Dortmund    71
Dortmund    Muenster 71
Dortmund    Hannover    213
Dortmund    Kassel  167
Dortmund    FFAM    221
Dortmund    Koeln    95
Hannover    Hamburg 152
Hannover    Berlin  286
Hannover    Kassel  165
Hannover    Dortmund    213
Koeln    Dortmund    95
Koeln    FFAM    193
Koeln    Stuttgart   368
Stuttgart   Koeln    368
Stuttgart   Muenchen 231
Muenchen Stuttgart   231
Muenchen FFAM    392
FFAM    Koeln    193
FFAM    Dortmund    221
Kassel  Dortmund    167
Kassel  Hannover    165
Berlin  Hannover    286
Berlin  Hamburg 289
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


prev up next
Previous: Graphalgorithmen für Adjazenzmatrizen Up: Graphen Next: Traversieren von Graphen