3. Graphstrukturen (LK)
Als Spezialfall eines Graphen betrachten wir hier den ungerichteten, gewichteten Graphen. D.h. eine Kantenverbindung zwischen zwei Knoten wird grundsätzlich in beide Richtungen interpretiert und jeder Kante wird ein Gewicht (z.B. die Weglänge oder die benötigte Zeit) zugeordnet. Durch die Gesamtheit aller Kanten ergibt sich der Graph.
Eine Datenstruktur für Graphen
Um Graphen zu modellieren, stehen die drei Klassen Vertex, Edge und Graph zur Verfügung.
Einen Graphen aufbauen
Der folgende Quelltext baut mithilfe der drei Klassen einen einfachen Beispielgraphen auf:
Im Quelltext ist deutlich zu sehen, dass die Knoten und Kanten des Graphen getrennt erzeugt und dem Graphen zugewiesen werden.
Graph g = new Graph();
Vertex v1 = new Vertex("1");
Vertex v2 = new Vertex("2");
Vertex v3 = new Vertex("3");
g.addVertex(v1);
g.addVertex(v2);
g.addVertex(v3);
Edge e1 = new Edge(v1,v2,5);
Edge e2 = new Edge(v1,v3,7);
Edge e3 = new Edge(v2,v3,13);
g.addEdge(e1);
g.addEdge(e2);
g.addEdge(e3);
Beispiel: Nächster Nachbar
Als exemplarische Anwendung der drei Klassen wird hier in einem gegebenem Graphen für einen gegebenen Knoten der nächstgelegene Nachbar bestimmt, d.h. die ID desjenigen Knoten, der mit dem gegebenen Knoten direkt verbunden ist und dessen zugehörige Kante das geringste Gewicht aufweist.
Dazu wird mithilfe der Methode getNeighbours() zunächst eine Liste aller Nachbarknoten erfragt. Diese Liste wird nun durchlaufen. Dabei wird jeweils überprüft, ob das bisherige minimale Kantengewicht von der aktuellen Kante (vom Ausgangsknoten zum Nchbarknoten) unterboten werden kann.
public String findeNaechstenNachbarn(String ID) {
Vertex startnode = g.getVertex(ID);
if (startnode==null) { return "Knoten unbekannt"; }
else {
List<Vertex> l = g.getNeighbours(startnode);
l.toFirst();
String next_neighbour = "kein Nachbar";
double min = 10000.0;
while (l.hasAccess()) {
Vertex node = l.getContent();
Edge e = g.getEdge(startnode,node);
double distance = e.getWeight();
if (distance<min) {
min = distance;
next_neighbour = node.getID();
}
l.next();
}
return next_neighbour;
}
}
Strategien zum Graphdurchlauf
Ziel des Graphendurchlauf ist es, alle Knoten eines Graphen nach einer festgelegten Strategie zu besuchen. Das Besuchen steht dabei stellvertretend für die Verarbeitung des Knotens, in den folgenden Quellcode-Beispielen wird dazu lediglich die ID des aktuelle besuchten Knotens ausgedruckt.
Beim Durchlauf von Graphen kommen analog zu Bäumen wieder die beiden Strategien der Tiefensuche und der Breitensuche in Betracht. Die Tiefensuche kann entweder rekursiv oder mithilfe eines Stacks umgesetzt werden. Um die Analogie zur Breitensuche herausarbeiten zu können, wird an dieser Stelle ein Stack verwendet. Das im nächsten Abschnitt beschriebene Backtracking, das auf der Tiefensuche basiert, wird dagegen vollständig rekursiv realisiert.
Tiefensuche
Zentrales Hilfsmittel der Tiefensuche ist ein Stack. Er sorgt dafür, dass ausgehend vom aktuellen Knoten immer der letzte Nachbar weiter verfolgt wird. (Bemerkung: Die Festlegung auf den letzten Nachbarn wurde hier willkürlich getroffen. Da es keine Anordnung von Nachbarknoten gibt, hat diese Festlegung keine Auswirkung auf die Funktionsfähigkeit des Verfahrens, sondern lediglich auf die Reihenfolge der besuchten Knoten.)
Zu Beginn wird der Startknoten auf den Stack gelegt, anschließend alle seine noch nicht besuchten Nachbarn. Da nun der oberste Knoten vom Stack genommen und weiter verarbeitet wird, geht die Verarbeitung also mit dem zuletzt auf den Stack gelegten Nachbarknoten weiter.
public void sucheTief(Graph g, String startid) {
g.setAllVertexMarks(false);
Vertex startnode = g.getVertex(startid);
Stack<Vertex> s = new Stack<Vertex>();
s.push(startnode);
while (!s.isEmpty()) {
Vertex aktuell = (Vertex) s.top();
if (!aktuell.isMarked()) { // VERARBEITEN
System.out.println(aktuell.getID());
}
aktuell.setMark(true);
List<Vertex> l = g.getNeighbours(aktuell);
l.toFirst();
boolean gefunden = false;
while (l.hasAccess()) { // nicht-markieter Knoten vorhanden?
Vertex nachbar = l.getContent();
if (!nachbar.isMarked()) {
s.push(nachbar);
gefunden = true;
break;
}
else {
l.next();
}
}
if (!gefunden) { s.pop(); }
}
}
Breitensuche
Im Unterschied zur Tiefensuche wird bei der Breitensuche eine Schlange als Hilfsdatenstruktur eingesetzt. Da für jeden aktuellen alle noch nicht besuchten Nachbarn an die Schlange angehängt werden, ergibt sich eine "ebenenweise" Abarbeitung des Graphen.
private Queue<Vertex> nichtDoppeltEinfuegen(Queue<Vertex> q, Vertex node) {
Queue<Vertex> qneu = new Queue<Vertex>();
boolean insert = true;
while (!q.isEmpty()) {
Vertex n = q.front();
q.dequeue();
if (n.getID().equals(node.getID())) {
insert = false;
}
qneu.enqueue(n);
}
if (insert) { qneu.enqueue(node); }
return qneu;
}
Die Hilfsmethode, die das nicht-doppelte Einfügen in die Schlange realisiert, sei hier der Vollständigkeit halber mit angegeben:
private Queue<Vertex> nichtDoppeltEinfuegen(Queue<Vertex> q, Vertex node) {
Queue<Vertex> qneu = new Queue<Vertex>();
boolean insert = true;
while (!q.isEmpty()) {
Vertex n = q.front();
q.dequeue();
if (n.getID().equals(node.getID())) {
insert = false;
}
qneu.enqueue(n);
}
if (insert) { qneu.enqueue(node); }
return qneu;
}
Backtracking
Der folgende Backtracking-Algorithmus bestimmt alle Wege, die von einem gegebenen Startknoten zu einem gegebenen Zielknoten führen. Es ist leicht einzusehen, dass dieser Algorithmus exponentielle Laufzeit haben muss.
Die Startmethode trifft alle Vorbereitungen, um das Backtracking in Gang zu setzen.
public void sucheWeg(Graph g, String vonID, String nachID) {
g.setAllVertexMarks(false);
Vertex vonKnoten = g.getVertex(vonID);
Vertex nachKnoten = g.getVertex(nachID);
List<Vertex> knotenliste = new List<Vertex>();
vonKnoten.setMark(true); // Markiere den Startknoten
knotenliste.append(vonKnoten);
backtrack(g, vonKnoten, nachKnoten, knotenliste); // Starte die Rekursion!
}
Die zentrale Idee des Algorithmus besteht darin, dass ausgehend von einem bislang ermittelten Pfad mit seinem bisherigen Endknoten ein Weg beginnend mit dem bisherigen Endknoten und endend mit dem gegebenen Endknoten gefunden werden soll. Der rekursive Algoritthmus sorgt dafür, dass für jedes Zwischenergebnis (also jeden Zwischenpfad) alle weiteren möglichen Pfade gesucht werden. Dabei werden nur neue (Nachbar-)Knoten berücksichtigt, die noch nicht besucht worden sind.
Auf das eigentliche Backtracking (Speichere die Länge des bislang kürzesten gefundenen Weges und verwerfe Alternativwege, deren Länge bereits größer ist.) wird hier zur Vereinfachung verzichtet.
private void backtrack(Graph g, Vertex vonKnoten, Vertex nachKnoten, List<Vertex> weg) {
if (vonKnoten == nachKnoten) { // Ziel schon erreicht?
String hilf = druckeWegAus(g, weg);
System.out.println(hilf);
}
else {
List<Vertex> nachbarKnoten = g.getNeighbours(vonKnoten);
nachbarKnoten.toFirst();
while (nachbarKnoten.hasAccess()) { // Bearbeite alle Nachbarknoten
Vertex knoten = nachbarKnoten.getContent();
if (!knoten.isMarked()) {
knoten.setMark(true);
weg.append(knoten);
backtrack(g, knoten, nachKnoten, weg); // Suche ueber diesen Nachbarn weiter nach dem Ziel
knoten.setMark(false);
weg.toLast();
weg.remove();
}
nachbarKnoten.next();
}
}
}
Zum Ausdrucken eines vollständig gefundenen Pfades vom Start- zum Endknoten wird eine Hilfsmethode verwendet, die hier der Vollständigkeit halber mit angegeben ist.
private String druckeWegAus(Graph g, List<Vertex> wegliste) {
// Bestimme zunaechst die Weglaenge
double wegLaenge = 0;
wegliste.toFirst();
Vertex wegKnoten1 = wegliste.getContent();
wegliste.next();
while (wegliste.hasAccess()) {
Vertex wegKnoten2 = wegliste.getContent();
Edge e = g.getEdge(wegKnoten1, wegKnoten2);
double distanz = e.getWeight();
wegLaenge = wegLaenge + distanz;
wegKnoten1 = wegKnoten2;
wegliste.next();
}
// Baue Zeichenkette zusammen
wegliste.toFirst();
String s = wegLaenge + ": ";
while (wegliste.hasAccess()) {
Vertex wegKnoten = wegliste.getContent();
s = s + wegKnoten.getID()+" ";
wegliste.next();
}
return s+"\n";
}