AuK/Durchläufe durch Graphen SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
Der '''Graphendurchlauf''' (engl. ''graph traversal'') bildet die Grundlage vieler Graphenalgorithmen. Die Idee besteht darin, alle Knoten bzw. Kanten in einem Graphen systematisch zu besuchen, um beispielsweise Informationen über dessen Struktur zu sammeln.
[[Bild:Croxeldyffic_Labyrinth03.png|thumb|200px|right|Ein Labyrinth mit Startpunkt (grün) und Ziel (rot) [http://www.swisseduc.ch/informatik/diskrete_mathematik/tiefensuche_labyrinth/applet.html (Animation)]]]
Als Motivation für die Lösung dieses Problems soll folgendes Beispiel dienen: Eine Person befindet sich in einem Labyrinth, und sucht einen Ausgang, indem sie alle möglichen Kreuzungen von Gängen in Augenschein nimmt. Übertragen auf die Graphentheorie, existieren hierfür zwei bekannte algorithmische Lösungsverfahren, die Hauptgegenstand dieser Vorlesung sind. In unserem Beispiel sind die Gänge des Labyrinths die Kanten und alle Kreuzugen die Knoten des Graphen.
Stellen wir uns vor, die eingeschlossene Person folgt einem bestimmten Gang solange, bis sie in eine Sackgasse gerät, zur letzten Kreuzung zurückkehrt und einem anderen Weg auf die gleiche Art verfolgt. Dieses systematische Vordringen in die "Tiefe" nennen wir '''Tiefensuche'''.
Sucht jedoch eine Gruppe von Leuten den Ausgang, so ist es wahrscheinlicher, dass sie gemeinsam vom Startpunkt ausschwärmen in die "Breite" vordringen. Analog dazu sprechen wir von einer '''Breitensuche'''.
Am Ende des Kapitels wird es uns möglich sein, das Labyrinth-Problem und viele andere graphentheoretische Probleme mithilfe der beiden Algorithmen zu lösen.
<div style="background-color:#EEE; border: 1px dashed; max-width:75%">
<p style="padding:10px"><b>Hinweis:</b> Im Folgenden wird häufig von <b>Suche</b> die Rede sein, obwohl es sich meistens eher um einen <b>Durchlauf</b> handelt. Durch die Übernahme der englischen Begrifflichkeiten DFS und BFS (<i>depth-first</i> und <i>breadth-first search</i>) haben sich die Bezeichnungen Tiefen- und Breitensuche anstelle von -durchlauf eingebürgert. Wir hoffen, damit kein allzu große Verwirrung zu stiften.</p>
</div>
<pre>
TODO-Pic:
// suchbäume dfs & bfs
// hamilton
// SCC - bsp-graph + lösung
Applets:
// bfs/dfs-applet: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html meh~
// dfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/DFSApplet.html w00ts~
// bfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/BFSApplet.html w00ts2x~
// eu/hm-applets zum knobeln: http://www.cut-the-knot.org/Curriculum/Combinatorics/GraphPractice.shtml spiffy~
// laby-applet: http://www.swisseduc.ch/informatik/diskrete_mathematik/tiefensuche_labyrinth/applet.html lolz~
</pre>
= Wiederholung =
Zum Verständnis der später vorgestellten Graphenalgorithmen sind grundlegende Kenntnisse über Graphen und spezielle Datenstrukturen notwendig, die jedoch bereits Themen in vorigen Veranstaltungen waren und im Folgenden nur aufgefrischt werden sollen.
== Graphrepräsentation ==
<div style="background-color:#EEE">
$\rightarrow$ siehe Vorlesung [http://programmingwiki.de/AuK/Graphrepr%C3%A4sentationen_SS12 Graphrepräsentation]
</div>
'''Kontrollfragen:'''
<ol>
<li> <b>Was ist der Unterschied zwischen <i>gerichteten</i> und <i>ungerichteten</i> Graphen?</b>
<popup title="Lösung">
<ol>
<div align="center">
<gallery widths="300px" heights="300px">
Bild:Croxeldyffic_G01.PNG|Ein ungerichteter Graph
Bild:Croxeldyffic_G01_1.PNG|Ein gerichteter Graph
</gallery>
</div>
In einem <i>ungerichteten</i> Graphen kann eine Kante $(u,v)$ in beliebiger Richtung überquert werden, während in einem <i>gerichteten</i> Graphen die zulässige Durchlaufrichtung durch einen Pfeil gekennzeichnet ist (ähnlich einer Einbahnstraße).
Will man einen ungerichteten Graphen gerichtet darstellen, so verdoppelt sich die Kantenmenge, d.h. enthält die Kantenmenge $K$ des ungerichteten Graphen die Kante $(u,v)$, muss die Kantenmenge $K$ des gerichteten Graphen die Kanten $(u,v)$ und $(v,u)$ enthalten.
</ol>
</popup>
</li>
<li><b>Welche Darstellungsformen für Graphen gibt es?</b>
<ol style="list-style-type:lower-alpha">
<li> Wie können diese im Computer realisiert werden? </li>
<li> Welche ist am besten? </li>
</ol>
<popup title="Lösung">
<ol style="list-style-type:lower-alpha">
<li>
<ul>
<li><b>Feld:</b> Ein Adjazenzfeld ist eine sehr einfache Darstellungsform, in der alle Zielknoten in einem Array geordnet nach Startknoten gespeichert werden.</li>
<li><b>Liste:</b> Eine Adjazenzliste ist eine verkettete Liste mit Nachfolgern bzw. Nachbar eines Knotens. </li>
<li><b>Matrix:</b> Eine Adjazenzmatrix ist ein mehrdimensionales ($V \times V$ mit $V$ als Knotenanzahl) Array mit booleschen Variablen, in der $a[u,v]$ auf 1 oder true gesetzt wird, wenn eine Kante $(u,v)$ existiert. Analog dazu gibt eine Inzidenzmatrix ($V \times E$-großes Array) die Inzidenzbeziehungen zwischen Knoten und Kanten in einem Graphen an.</li>
</ul>
</li>
<li> Wir vergleichen die drei bzw. vier Darstellungsformen miteinander:
<table border="1" cellpadding="1" cellspacing="3">
<tr style="background-color:#EEE">
<td> </td>
<td>Adjazenzfeld</td>
<td>Adjazenzliste</td>
<td>Adjazenzmatrix</td>
<td>Inzidenzmatrix</td>
</tr>
<tr>
<td style="background-color:#EEE">Speicheraufwand</td>
<td>$\mathcal{O}\: (|V| + |E|)$</td>
<td>$\mathcal{O}\: (|V| + |E|)$</td>
<td>$\mathcal{O}\: (|V|^2)$</td>
<td>$\mathcal{O}\: (|V| \cdot |E|)$</td>
</tr>
<tr>
<td style="background-color:#EEE">Nachbarabfrage</td>
<td>$\mathcal{O}\: (d)^*$ <br> <font size="-2">* $d$ = max. Ausgangsgrad</font> </td>
<td>$\mathcal{O}\: (d)^*$ <br> <font size="-2">* $d$ = max. Ausgangsgrad</font></td>
<td>$\mathcal{O}\: (1)$</td>
<td>$\mathcal{O}\: (|E|)$</td>
</tr>
<tr>
<td style="background-color:#EEE">Vorteile</td>
<td>+ kompakte Darstellung</td>
<td>+ kompakte Darstellung<br>+ effizient für dynamische Graphen</td>
<td>+ schneller Zugriff<br>+ effizient bei dichten Graphen<br>+ schnelles Löschen von Kanten</td>
<td>+ besser bei lichten Graphen</td>
</tr>
<tr>
<td style="background-color:#EEE">Nachteile</td>
<td>- nur für statische Graphen</td>
<td>- ineffizient für dichte Graphen</td>
<td>- hoher Speicheraufwand<br>- ineffizient bei lichten Graphen</td>
<td>- hoher Speicheraufwand bei dichten Graphen<br>- langsames Löschen von Kanten</td>
</tr>
</table>
<b>Fazit:</b> Die Anzahl der Kanten ist bei den meisten Graphen höher als die Knotenanzahl, daher ist aufgrund der schnellen Zugriffszeit die Adjazenzmatrix als Darstellungsform empfohlen.
</li>
</ol>
</popup>
</li>
</ol>
== Bäume ==
<div style="background-color:#EEE">
$\rightarrow$ siehe Vorlesung [http://programmingwiki.de/AuK/Sortierte_Folgen_SS12 Sortierte Folgen]
</div>
'''Kontrollfragen:'''
<ol>
<li><b>Was sind die Bestandteile eines Baumes?</b>
<ol style="list-style-type:lower-alpha">
<li>Welche Arten von Knoten gibt es?</li>
<li>Was ist ein Pfad? </li>
</ol>
<popup title="Lösung">
<ol style="list-style-type:lower-alpha">
<li>
<ul>
<li><b>Wurzelknoten:</b> Der Startknoten, von dem alle Pfade ausgehen.
<li><b>Kindknoten:</b> Der Nachfolger eines Knotens.
<li><b>Vaterknoten:</b> Der Vorgänger eines Knotens. Die Wurzel eines Baumes besitzt keinen Vater.
<li><b>Geschwister- bzw. Bruderknoten:</b> Knoten mit dem gleichen Vater.
<li><b>Blattknoten:</b> Knoten ohne Nachfolger (Kinder).<br><br>
</ul>
</li>
<li>Ein Pfad entspricht einem Weg von einem Knoten zum anderen. In Bäumen sind meist Pfade, die von der Wurzel ausgehen, gesucht.</li>
</ol>
</popup>
</li>
</ol>
== Datenstrukturen Stack und Queue ==
<div style="background-color:#EEE">
$\rightarrow$ siehe Vorlesung [http://programmingwiki.de/AuK/Priorit%C3%A4tswarteschlangen_SS12 Prioritätswarteschlangen]
</div>
'''Kontrollfragen:'''
<ol>
<li><b>Nach welchem Prinzip arbeitet eine Warteschlange?</b>
<popup title="Lösung">
<p>Eine Warteschlange (engl. <i>queue</i>) arbeitet nach dem FIFO-Prinzip, d.h. das Element, das zuerst in die Warteschlange abgelegt wurde, wird zuerst bearbeitet (ähnlich einer Schlange im Supermarkt).<br>
Folgende Operationen sind notwendig:
<ul>
<li>Element hinzufügen (enqueue): Das Element wird nach dem letzten Element eingefügt.</li>
<li>erstes Element anzeigen (peek): Das zuerst hinzugefügte Element wird ausgegeben.</li>
<li>Element löschen (dequeue): Das zuerst hinzugefügte Element wird ausgegeben und aus der Schlange entfernt.</li>
<li>Prüfung, ob Schlange leer ist (isEmpty)</li>
</ul></p>
'''Implementierung:'''
<code id="4f9d33b72b119">
public Object Queue()
{
int[] elemente = new int[0];
int top;
int groesse = elemente.length;
public boolean istLeer()
{
groesse = elemente.length;
return groesse == 0;
}
public int peek()
{
top = elemente[0];
return top;
}
public void enqueue(int element)
{
groesse = elemente.length;
int[] neu = new int[groesse +1];
for (int i=0; i<=groesse-1; i++)
neu[i] = elemente[i];
neu[groesse] = element;
elemente = neu;
top = elemente[0];
}
public int dequeue()
{
top = elemente[0];
groesse = elemente.length;
int[] neu = new int[groesse-1];
for(int i = 0; i < groesse-1; i++)
neu[i] = elemente[i+1];
elemente = neu;
return top;
}
return this;
}
</code>
</popup>
<run id="4fad7665d2435">
queuey01 = Queue();
queuey01.istLeer();
// queuey01.enqueue(1);
// queuey01.enqueue(2);
// queuey01.enqueue(3);
// queuey01.istLeer();
// queuey01.peek();
// queuey01.dequeue();
// queuey01.dequeue();
// queuey01.peek();
// queuey01.dequeue();
// queuey01.istLeer();
</run>
</li>
<li><b>Nach welchem Prinzip arbeitet ein Stack?</b></li>
<popup title="Lösung">
<p>Im Gegensatz zur Warteschlange arbeitet ein Stack nach dem LIFO-Prinzip, d.h. das Element, das zuletzt auf den Stack abgelegt wurde, wird zuerst bearbeitet (ähnlich einem Stapel Bücher etc.).<br>
Folgende Operationen sind notwendig:
<ul>
<li>Element hinzufügen (push): Das Element wird an erster Stelle eingefügt.</li>
<li>erstes Element anzeigen (peek): Das zuletzt hinzugefügte Element wird ausgegeben.</li>
<li>Element löschen (pop): Das zuletzt hinzugefügte Element wird ausgegeben und aus dem Stack entfernt.</li>
<li>Prüfung, ob Stack leer ist (isEmpty)</li>
</ul></p>
'''Implementierung:'''
<code id="4f986cf808f9a">
public Object Stack()
{
int groesse = 20;
int[] elemente = new int[groesse];
int top = -1;
public void push(int j)
{elemente[++top] = j;}
public int pop()
{return elemente[top--];}
public int peek()
{return elemente[top];}
public boolean istLeer()
{return (top == -1);}
return this;
}
</code>
</popup>
<run id="4fad7665d24cb">
stacky01 = Stack();
stacky01.istLeer();
// stacky01.push(1);
// stacky01.push(2);
// stacky01.push(3);
// stacky01.istLeer();
// stacky01.peek();
// stacky01.pop();
// stacky01.pop();
// stacky01.peek();
// stacky01.pop();
// stacky01.istLeer();
</run>
</li>
</ol>
= Grundlagen zum Graphendurchlauf =
== Allgemeiner Durchlauf-Algorithmus ==
'''Unsere zentrale Frage lautet: <i>Wie können wir die Knoten eines Graphen durchlaufen, sodass jeder Knoten mindestens einmal besucht wird?</i>'''
Um am Ende eine vernünftige Durchlaufordnung angeben zu können, überlegen wir uns folgendes Verfahren:
<ul>
<li> <b>Eingaben: </b>
<ol>
<li> zusammenhängender Graph $G$ als Adjazenzlisten- oder -matrixdarstellung</li>
<li> eine Menge von Knoten $v \in V$ mit den Zuständen $unbesucht$ und $besucht$</li>
<li> eine Arbeitsliste $L$, die besuchte aber noch nicht abgearbeitete Knoten beinhaltet.</li>
</ol>
</li>
<li> <b>Algorithmus:</b>
<ol>
<li>Initialisierung: nur der Startknoten $v$ ist mit $besucht$ markiert und befindet sich in der Arbeitsliste $L$</li>
<li>solange $L$ nicht leer ist:
<ol>
<li> wähle einen Knoten $v$ aus $L$</li>
<li> wähle und markiere einen unbesuchten Nachbarn $u$ von $v$ als besucht und speichere $u$ in die Arbeitsliste $L$</li>
<li> falls $v$ keine unbesuchten Nachbarn besitzt, entferne $v$ aus $L$<br><br></li>
</ol>
</ol>
<div style="background-color:#EEE">
'''Algorithmus:''' ''Graphendurchlauf_allgemein (Graph $G$, Knoten $v \in V(G)$, Arbeitsliste $L$)'' <br>
<math>
\begin{array}{l|l}
1 & v \leftarrow besucht\\
2 & L \leftarrow L \oplus v\\
3 & \mathbf{while}\; (L \neq\: \emptyset)\; \mathbf{do} \\
4 &\;\;\;\;\; \text{\small waehle Knoten } v \in L \\
5 &\;\;\;\;\;\; \mathbf{if}\; (\!\text{\small es gibt } u \in V(G) \text{\small mit } u=Nachbar\; von\; v \text{\small und } u=unbesucht)\; \mathbf{then} \\
6 &\;\;\;\;\;\;\;\;\;\;\;\; u \leftarrow besucht\\
7 &\;\;\;\;\;\;\;\;\;\;\;\; L \leftarrow L \oplus u\\
8 &\;\;\;\;\;\; \mathbf{else}\; L \leftarrow L \ominus u \\
\end{array}
</math><br>
'''end''' ''Graphendurchlauf_allgemein''
</div></li>
</ul><br>
Suchen wir im Graphen dagegen ein bestimmtes Element, so wie wir bei unserem Labyrinth-Problem nach dem Ausgang (Zielknoten) suchen, genügt es, den Algorithmus bis zum Auffinden des gesuchten Elements auszuführen und mit Ausgabe des Pfades bis zum Ziel terminieren zu lassen. Nachdem wir also das Ziel erreicht haben, ist es nicht nötig, den Graphen weiter zu durchlaufen, selbst wenn es noch unbesuchte Knoten gibt. Der Suchalgorithmus terminiert spätestens, wenn alle Knoten durchlaufen wurden, sodass sicher ist, dass das Element, falls es im Graphen enthalten ist, auch gefunden wird.
In der Praxis ist diese Bedingung abhängig vom gewählten Verfahren nicht immer erfüllbar. Mehr dazu in den Abschnitten ''Breiten-'' und ''Tiefensuche''.
== Die Arbeitsliste $L$ ==
Die Art und Weise wie die einzelnen besuchten Knoten in die Arbeitsliste $L$ eingefügt werden sollen, ist beim Graphendurchlauf von großer Bedeutung. Hierfür gibt es zwei Möglichkeiten.
=== Die Arbeitsliste als Stack ===
Wird die Arbeitsliste als Stack implementiert, wird jeder besuchte Knoten nach dem LIFO-Prinzip eines Stacks auf $L$ abgelegt.
'''Arbeitsweise:'''
<ol>
<li> markiere den Startknoten $v$ als $besucht$ und legen ihn auf den leeren Stack ab</li>
<li> solange der Stack nicht leer ist:
<ol>
<li>ermittle alle unbesuchten Nachbarn des obersten Knotens $v$ im Stack und lege sie auf den Stack ab</li>
<li>falls der oberste Knoten keine unbesuchten Nachbarn besitzt, entferne ihn aus dem Stack und fahre mit dem neuen ersten Element fort.
</ol>
</li>
</ol>
Mit dieser Implementierung lässt sich die ''Tiefensuche'' realisieren.
=== Die Arbeitsliste als Queue ===
[[Bild:Croxeldyffic_Queue_med.gif|thumb|right|350px| Arbeitsliste $L$ als Queue]]
Wird die Arbeitsliste dagegen als Queue implementiert, werden die besuchten Knoten nach dem FIFO-Prinzip einer Warteschlange an $L$ angefügt.
'''Arbeitsweise:'''
<ol>
<li> markiere den Startknoten $v$ als $besucht$ und füge ihn in die leere Queue ein</li>
<li> solange die Queue nicht leer ist:
<ol>
<li>ermittle alle unbesuchten Nachbarn des ersten Knotens $v$ in der Queue und hänge sie an die Warteschlange an</li>
<li>falls $v$ keine unbesuchten Nachbarn besitzt, entferne $v$ aus der Queue und fahre mit dem neuen ersten Element fort</li>
</ol>
</li>
</ol>
Mit dieser Implementation kann die ''Breitensuche'' realisiert werden.
== Laufzeitverhalten ==
Mit welcher Laufzeit kann bei diesem Algorithmus gerechnet werden?
Relevant für den Algorithmus ist die Anzahl der Knoten und Kanten im Graphen. Daher ist die vom Verfahren benötigte Zeit ungeachtet der verwendeten Datenstruktur für die Arbeitsliste $L$ stets proportional zur Summe der Anzahl aller vom Startknoten erreichbaren Knoten und Kanten. Der Schleifendurchlauf im Funktionskörper führt stets gleich viele Schritte aus, wobei kein Knoten doppelt abgearbeitet wird. Wir notieren eine Maximallaufzeit von $\mathcal{O}\: (|V| + |E|)$ mit $V$ als Knoten- und $E$ als Kantenanzahl.
== Zusammenhängende Graphen ==
Als Eingabe für den Durchlauf-Algorithmus haben wird einen ''zusammenhängenden'' Graphen angegeben. Wir fragen jetzt, wann ist ein Graph zusammenhängend bzw. was ist er es nicht?
'''Definition:'''
''Ein Graph $G$ heißt zusammenhängend, wenn je zwei Knoten von $G$ verbindbar sind, d.h. es existiert eine Kante zwischen den beiden Knoten. Ein zusammenhängender Graph enthält keine isolierten Knoten''
'''Beispiele:'''
<gallery widths="300px" heights="300px">
</gallery>
Ein Anwendungsbeispiel hierzu findet sich in vielen Städten: Einbahnstraßen. Befinden sich in einem Stadtteil besonders viele Einbahnstraßen, stellt sich als Autofahrer die Frage, ob man noch von jedem Ort aus jeden anderen Ort erreichen kann.
Ist ein Graph nicht zusammenhängend, kann man ihn in gewisse Komponenten (Teilgraphen) zerlegen, die unter sich zusammenhängend sind. Die Menge dieser Teilgraphen ergibt widerum den Graphen. Wir sprechen hier bei ungerichteten Graphen von sogenannten '''Zusammenhangskomponenten''' und bei gerichteten Graphen von <b><i>starken</i> Zusammenhangskomponenten</b> (engl. ''strongly connected components'', SCCs), deren Bestimmung wir an späterer Stelle kennenlernen werden. Besteht ein Graph aus nur einer Zusammenhangskomponenten, ist er zusammenhängend.
== Unsere interne Graphenrepräsentation ==
Eine Vielzahl der nachfolgenden Algorithmen wollen wir einerseits durch Rechnung per Hand als auch mittels Computer umsetzen und anwenden. Der Vorteil hierfür liegt vorallem bei Berechnungen und Operationen auf sehr umfangreichen und dichten Graphen. Wir verwenden in allen Programmbeispielen auschschließlich die Programmiersprache JAVA, da wir mithilfe der Objektorientierung die einzelnen Sachverhalte einfach und verständlich modellieren können.
// uml-diags?
=== Knoten ===
<code id="4f9875926c8ee">
public Object Vertex (char label)
{
char label = label;
boolean bereitsBesucht = false;
Object next = null, prev = null;
String farbe = "weiss";
int gefunden = -1, abgearbeitet = -1;
int markierung = 0;
return this;
}
</code>
<code id="4fad535c9c64b" hidden>
public Object Edge (int s, int t)
{
int start=s;
int target=t;
String kantenart = "leer";
boolean traversed = false;
return this;
}
</code>
=== Graph ===
<code id="4f987d51e2b3c">
public Object Graph(int max, String a)
{
int knotenanzahl = max;
int kantenanzahl = ((max+1)*(max+1));
String art = a;
int zeit = 0;
int c;
Object[] knotenliste = new Object[knotenanzahl];
int[][] adjazenzMatrix = new int[knotenanzahl+1][knotenanzahl+1];
Object[] kantenliste = new Object[kantenanzahl];
Object[] eulerliste = kantenliste;
int kantengesamt=0;
int eulerkanten=0;
int kantengenutz=0;
int kanten = 0;
int knoten = 0;
Object stacky = Stack();
Object queuey = Queue();
Object topologie = Stack();
for(int x=0; x<=knotenanzahl; x++)
for(int y=0; y<=knotenanzahl; y++)
adjazenzMatrix[x][y] = 0;
public void addEdge(int start, int end)
{
if(this.art == "ungerichtet"){
adjazenzMatrix[start-1][end-1] = 1;
adjazenzMatrix[end-1][start-1] = 1;
knotenliste[start-1].next = knotenliste[end-1];
knotenliste[start-1].prev = knotenliste[end-1];
knotenliste[end-1].prev = knotenliste[start-1];
knotenliste[end-1].next = knotenliste[start-1];
}
if(this.art == "gerichtet"){
adjazenzMatrix[start-1][end-1] = 1;
knotenliste[start-1].next = knotenliste[end-1];
knotenliste[end-1].prev = knotenliste[start-1];
}
}
public void addVertex(char lab)
{
knotenliste[knoten++] = Vertex(lab);
}
public void displayVertex(int v, String ausgabe)
{
if(ausgabe=="standard")
System.out.print(knotenliste[v].label);
if(ausgabe=="erweitert"){
System.out.print("Label: " + knotenliste[v].label + " ");
System.out.print("Farbe: " + knotenliste[v].farbe + " ");
if(knotenliste[v].prev == null)
System.out.print("Voriges Element: # ");
else
System.out.print("Voriges Element: " + knotenliste[v].prev.label + " ");
System.out.print("Wann entdeckt: " + knotenliste[v].gefunden + " ");
System.out.print("Wann geschlossen: " + knotenliste[v].abgearbeitet + " ");
}
}
public void zeigeAdjMatrix()
{
System.out.println("\nAdjazenzmatrix:");
Object[][] showMat = new Object[knotenanzahl+1][knotenanzahl+1];
showMat[0][0] = ' ' ;
for(int i=0; i<knotenanzahl; i++){
for(int row=1; row<=knotenanzahl; row++){
showMat[0][row] = this.knotenliste[row-1].label;
showMat[i+1][row] = this.adjazenzMatrix[i][row-1];
}
for(int col=1; col<=knotenanzahl; col++){
showMat[col][0] = this.knotenliste[col-1].label;
showMat[col][i+1] = this.adjazenzMatrix[col-1][i];
}
}
for (int k = 0; k<=knotenanzahl; ++k) {
for (int l = 0; l<=knotenanzahl; ++l) {
System.out.print(showMat[k][l] + "\t");
}
System.out.println("");
}
}
</code>
<code id="4faf0e7675d95">
public void dfs(int start)
{
System.out.print("\n\nDFS-Durchlaufordnung: ");
start--;
knotenliste[start].bereitsBesucht=true;
displayVertex(start, "standard");
stacky.push(start);
while (!stacky.istLeer())
{
int v = naechsterUnbesuchterNachbar(stacky.peek());
if(v == -1) stacky.pop();
else
{
knotenliste[v].bereitsBesucht = true;
displayVertex(v, "standard");
stacky.push(v);
}
}
for(int i=0; i<knotenanzahl;i++){
if(knotenliste[i].bereitsBesucht==false){
System.out.println("... Graph nicht zusammenhängend!");
break;}
else continue;
}
for(int j=0; j<knoten; j++)
knotenliste[j].bereitsBesucht = false;
}
public void bfs(int start)
{
System.out.print("\n\nBFS-Durchlaufordnung: ");
start--;
knotenliste[start].bereitsBesucht=true;
displayVertex(start, "standard");
queuey.enqueue(start);
while (!queuey.istLeer())
{
int v = naechsterUnbesuchterNachbar(queuey.peek());
if(v == -1) queuey.dequeue();
else
{
knotenliste[v].bereitsBesucht = true;
displayVertex(v, "standard");
queuey.enqueue(v);
}
}
for(int i=0; i<knotenanzahl;i++){
if(knotenliste[i].bereitsBesucht==false){
System.out.println("... Graph nicht zusammenhängend!");
break;}
else continue;
}
for(int j=0; j<knoten; j++)
knotenliste[j].bereitsBesucht = false;
}
public int naechsterUnbesuchterNachbar(int v)
{
for(int j=0; j<knotenanzahl; j++){
if(adjazenzMatrix[v][j] == 1 && knotenliste[j].bereitsBesucht==false)
return j;
}
return -1;
}
</code>
<code id="4faf0e7675ea8">
public void dfsrek(int start, char c)
{
System.out.println("\n\nDFS-Durchlaufordnung(rekursiv): ");
start--;
for (int j=0; j<knoten; j++)
{
knotenliste[j].farbe = "weiss";
knotenliste[j].prev = null;
}
zeit = 0;
for (int j=start; j<knoten; j++)
{
if (knotenliste[j].farbe == "weiss")
dfsvisit(j, c);
}
if (start != 0)
for (int j = 0; j < start; j++) {
if (knotenliste[j].farbe == "weiss")
dfsvisit(j, c);
};
for(int j=0; j<knoten; j++)
{
displayVertex(j, "erweitert");
System.out.println();
};
}
public void dfsvisit(int u, char c)
{
knotenliste[u].farbe = "grau";
zeit++;
knotenliste[u].gefunden = zeit;
if (knotenliste[u].label == c)
System.out.println(c + " in Schritt " + knotenliste[u].gefunden + " gefunden\n");
for (int j=0; j<knoten; j++)
if (adjazenzMatrix[u][j] == 1 && knotenliste[j].farbe == "weiss") {
knotenliste[j].prev = knotenliste[u];
dfsvisit(j, c);
};
knotenliste[u].farbe = "schwarz";
zeit++;
knotenliste[u].abgearbeitet = zeit;
topologie.push(u + 1);
}
public void displayTopo()
{
System.out.println("\nTopologisch sortiert: ");
for(int j=0; j<knoten ; j++){
System.out.print(topologie.peek() + " ");
topologie.pop();
}
System.out.println();
}
</code>
<code id="4faf0e7675f8c">
// ab hier beginnt der ernst des lebens... -.-
public void displayKantenart(int z) // z ist Kante in der liste, 0 fuer
// alle
{
z = z - 1;
if (z != -1) {
System.out.print("Kante: "
+ knotenliste[kantenliste[z].start - 1].label + " "
+ knotenliste[kantenliste[z].target - 1].label
+ " ist eine ");
System.out.println(kantenliste[z].kantenart);
} else
for (int i = 0; i < kanten; i++) {
System.out.print("Kante: "
+ knotenliste[kantenliste[i].start - 1].label + " "
+ knotenliste[kantenliste[i].target - 1].label
+ " ist eine ");
System.out.println(kantenliste[i].kantenart);
}
}
public void ermittleKantenart() {
if (art == "gerichtet") {
for (int j = 0; j < kanten; j++) {
if ((kantenliste[j].start == kantenliste[j].target)
&& (art == "gerichtet"))
kantenliste[j].kantenart = "Reuckwaertskante";
else if ((knotenliste[kantenliste[j].start - 1].gefunden + 1) == knotenliste[kantenliste[j].target - 1].gefunden)
kantenliste[j].kantenart = "Baumkante";
}
for (int u = 0; u < kanten; u++)
if (kantenliste[u].kantenart == "leer")
if ((verbindetBaumkanten(kantenliste[u].start,
kantenliste[u].target))
&& (knotenliste[kantenliste[u].start - 1].gefunden > knotenliste[kantenliste[u].target - 1].gefunden)
&& (knotenliste[kantenliste[u].start - 1].abgearbeitet < knotenliste[kantenliste[u].target - 1].abgearbeitet))
kantenliste[u].kantenart = "Reuckwaertskante";
else if ((verbindetBaumkanten(kantenliste[u].start,
kantenliste[u].target))
&& (knotenliste[kantenliste[u].start - 1].gefunden < knotenliste[kantenliste[u].target - 1].gefunden)
&& (knotenliste[kantenliste[u].start - 1].abgearbeitet > knotenliste[kantenliste[u].target - 1].abgearbeitet))
kantenliste[u].kantenart = "Vorwaertskante";
else if (!(kantenliste[u].start == kantenliste[u].target)
&& (art == "gerichtet"))
kantenliste[u].kantenart = "Querkante";
}
else if (art == "ungerichtet") {
for (int j = 0; j < kanten; j++) {
if ((knotenliste[kantenliste[j].target - 1].gefunden + 1) == knotenliste[kantenliste[j].start - 1].gefunden)
kantenliste[j].kantenart = "Baumkante";
else if ((knotenliste[kantenliste[j].start - 1].gefunden + 1) == knotenliste[kantenliste[j].target - 1].gefunden)
kantenliste[j].kantenart = "Baumkante";
else if ((knotenliste[kantenliste[j].start - 1].gefunden > kanten) && (knotenliste[kantenliste[j].target - 1].abgearbeitet > kanten))
kantenliste[j].kantenart = "Baumkante";
else
kantenliste[j].kantenart = "Reuckwaertskante";
}
}
}
public boolean verbindetBaumkanten(int start, int target) {
for (int j = 0; j < kanten; j++) {
if ((kantenliste[j].start == target)
&& (kantenliste[j].kantenart == "Baumkante"))
return true;
else if ((kantenliste[j].target == start)
&& (kantenliste[j].kantenart == "Baumkante"))
return true;
else if ((kantenliste[j].target == target)
&& (kantenliste[j].kantenart == "Baumkante"))
return true;
else if ((kantenliste[j].start == start)
&& (kantenliste[j].kantenart == "Baumkante"))
return true;
}
return false;
}
</code>
<code id="4faf0e76761a6">
public void fleury()
{
for(int i=0; i< kantengesamt;i++)
if((kantenliste[i].kantenart!="Querkante")&&(kantenliste[i].traversed==false)){
eulerliste[0]=kantenliste[i];
kantenliste[i].traversed=true;
eulerkanten++;
}
fleuryhelp(eulerliste[0].target);
}
public void fleuryhelp(int t)
{
for(int i=0; i< kantengesamt;i++)
if((t==kantenliste[i].start)&&(kantenliste[i].kantenart!="Querkante")&&(kantenliste[i].traversed==false)){
kantenliste[i].traversed=true;
eulerliste[eulerkanten]=kantenliste[i];
eulerkanten++;
fleuryhelp(kantenliste[i].target);
}
for(int i=0; i< kantengesamt;i++)
if ((kantenliste[i].traversed==false)&&(t==kantenliste[t].start)&&(kantenliste[i].kantenart=="Querkante")){
kantenliste[i].traversed=true;
eulerliste[eulerkanten]=kantenliste[i];
eulerkanten++;
fleuryhelp(kantenliste[i].target);
}
}
public void displayEulerliste()
{
System.out.print("Eulerpfad/kreis: ");
for(int i=0; i< eulerkanten;i++)
System.out.print("( "+eulerliste[i].start+" "+eulerliste[i].target+" )");
System.out.println();
}
</code>
<code id="4faf0e76762b2">
public void pruefeGrad()
{
System.out.println("\n\nEin- und Ausgangsgrade:");
int countIndegree=0, countOutdegree=0;
int[] In = new int[knotenanzahl];
int[] Out = new int[knotenanzahl];
for(int i=0; i<knotenanzahl; i++){
for(int j=0; j<knotenanzahl;j++){
if (adjazenzMatrix[j][i] ==1)
countIndegree++;
if(adjazenzMatrix[i][j] == 1)
countOutdegree++;
}
In[i]=countIndegree;
Out[i]=countOutdegree;
System.out.print("Eingangsgrad von Knoten " + knotenliste[i].label + ": " + countIndegree + "\t");
System.out.print("Ausgangsgrad von Knoten " + knotenliste[i].label + ": " + countOutdegree + "\n");
countIndegree=0;
countOutdegree=0;
}
int ungerade=0;
for (int l=0; l<knotenanzahl; l++){
if(Out[l]%2 !=0)
ungerade++;
}
System.out.println("\n--> Anzahl Knoten ungeraden Ausgangsgrades: " + ungerade);
if(ungerade== 0)
System.out.println("==> Eulerkreis möglich!");
else if(ungerade==2)
System.out.println("==> Eulerpfad möglich!");
else
System.out.println("==> Weder Eulerkreis noch -pfad möglich!");
int test=0;
for(int k=0; k<knotenanzahl; k++){
if((In[k] != 0) && (Out[k] != 0))
test++;
}
if(test==knotenanzahl)
System.out.println("==> Hamiltonpfad und/ oder -kreis möglich!");
else
System.out.println("==> Kein Hamiltonkreis, jedoch Hamiltonpfad möglich!");
}
</code>
<code id="4fafabc988fda">
public void connectedComponents()
{
System.out.println("\n\nZusammenhangskomponenten: ");
for(int i=0; i<knotenanzahl; i++)
knotenliste[i].markierung=0;
c=0;
for(int j=0; j<knotenanzahl;j++){
if(knotenliste[j].markierung==0){
c++;
dfscc(j);
}
}
for(int j=1; j<=c;j++){
System.out.println("\nSCC " + j + ":");
for(int i=0; i<knotenanzahl;i++){
if(j==knotenliste[i].markierung)
System.out.print("Knoten " + knotenliste[i].label + "\n");
else continue;
};
}
}
public void dfscc(int v)
{
knotenliste[v].markierung=c;
for(int i=0;i<knotenanzahl;i++){
if(adjazenzMatrix[v][i] == 1 && knotenliste[i].markierung==0 &&
knotenliste[i].prev!=null && knotenliste[i].next != null)
dfscc(i);
}
}
return this;
}
</code>
Einige der in der Klassendefinition von <font face="Courier New"><b>Graph</b></font> enthaltenen Methoden sollen an dieser Stelle nun getestet werden. Wir erstellen zwei Beispielgraphen jeweils unterschiedlichen Typs und mit unterschiedlicher Knoten- und Kantenanzahl. Des Weiteren lassen wir uns die zugehörigen Adjazenzmatrizen anzeigen.
<run id="4fafabc9891b0">
G_bsp01 = Graph(5, "gerichtet");
G_bsp01.addVertex('A'); // 1, start
G_bsp01.addVertex('B'); // 2
G_bsp01.addVertex('C'); // 3
G_bsp01.addVertex('D'); // 4
G_bsp01.addVertex('E'); // 5
G_bsp01.addEdge(1, 2);
G_bsp01.addEdge(1, 4);
G_bsp01.addEdge(2, 1);
G_bsp01.addEdge(2, 4);
G_bsp01.addEdge(4, 5);
G_bsp01.addEdge(5, 3);
G_bsp01.addEdge(3, 5);
G_bsp01.addEdge(3, 3);
G_bsp01.zeigeAdjMatrix();
</run>
<run id="4fafabc9892a0">
G_bsp02 = Graph(7, "ungerichtet");
G_bsp02.addVertex('1'); // start
G_bsp02.addVertex('2');
G_bsp02.addVertex('3');
G_bsp02.addVertex('4');
G_bsp02.addVertex('5');
G_bsp02.addVertex('6');
G_bsp02.addVertex('7');
G_bsp02.addEdge(1, 2);
G_bsp02.addEdge(1, 3);
G_bsp02.addEdge(2, 4);
G_bsp02.addEdge(3, 4);
G_bsp02.addEdge(3, 5);
G_bsp02.addEdge(4, 5);
G_bsp02.addEdge(6, 7);
G_bsp02.zeigeAdjMatrix();
</run>
'''Übungsaufgaben:'''
<ol>
<li> Zeichnen Sie die beiden Graphen $G_{bsp01}$ und $G_{bsp02}$ per Hand. </li>
<li> Sind beide Graphen zusammenhängend?
</ol>
<popup title="Lösung">
<ol>
<li> mögliche Anordnung der Knoten:
<gallery widths="350px" heights="350px">
Bild:Croxeldyffic_G_bsp01.png | Digraph $G_{bsp01}$
Bild:Croxeldyffic_Gbsp02.png | Ungerichteter Graph $G_{bsp02}$
</gallery>
</li>
<li> Graph $G_{bsp01}$ ist ein zusammenhängender Digraph, während Graph $G_{bsp02}$ einen unzusammenhängenden, ungerichteten Graphen repräsentiert.
</li>
</ol>
</popup>
= Tiefensuche =
[[Bild:Croxeldyffic_Dfs01.gif|thumb|390px|right|Das Voranschreiten einer iterativen Tiefensuche in einem gerichteten Graphen]]
Die Tiefensuche beginnt mit einem beliebigen Startknoten $u \in V(G)$ und folgt einer mit $u$ adjazenten Kante, bis zum nächsten Knoten $v\in V(G)$ der noch nicht besucht wurde(unmarkiert ist). Von diesem aus wird wieder ein erreichbarer Knoten gesucht. Man folgt also solange einem Kantenzug, bis man ein Blatt erreicht hat. Alle dabei entdeckten Knoten werden markiert.<br>
Nun verfolgt man den entstandenen Kantenzug solange zurück(''backtracing''), bis man einen Knoten findet, mit dem noch unbesuchte Knoten verbunden sind. Wird solch ein Knoten entdeckt, wählt man ihn als neuen Startknoten und folgt wieder seinen adjazenten Kanten.<br>
Anschließend wird solange ein neuer unmarkierter Knoten als Startknoten gewählt und abgearbeitet, bis alle Knoten markiert sind.<br>
Auf diese Weise entsteht ein Suchwald. Obwohl der Algorithmus einen Graphen $G$ ''immer'' vollständig abarbeitet, können abhänig vom Startknoten und der konkreten Implementierung ''verschiedene Suchwälder'' entstehen. Meistens ist aber jeder Wald sinnvoll verwendbar. <br>
== Iterativ mit Stack ==
Nur für zusammenhängende Graphen und bei manchen Graphen unvollständig
<div style="background-color:#EEE">
'''Algorithmus:''' ''Tiefendurchlauf (Graph $G$, Knoten $v \in V(G)$, Stack $S$)'' <br>
<math>
\begin{array}{l|l}
1 & v \leftarrow besucht\\
2 & S \leftarrow push(v)\\
3 & \mathbf{while}\; (S \neq\: \emptyset)\; \mathbf{do} \\
4 &\;\;\;\;\; \text{\small waehle Knoten } v \in S \text{\small mit } v = peek(S) \\
5 &\;\;\;\;\;\; \mathbf{if}\; (\!\text{\small es gibt } u \in V(G) \text{\small mit } u=Nachbar\; von\; v \text{\small und } u=unbesucht)\; \mathbf{then} \\
6 &\;\;\;\;\;\;\;\;\;\;\;\; u \leftarrow besucht\\
7 &\;\;\;\;\;\;\;\;\;\;\;\; S \leftarrow push(u)\\
8 &\;\;\;\;\;\; \mathbf{else}\; S \leftarrow pop(u) \\
\end{array}
</math><br>
'''end''' ''Tiefendurchlauf''
</div>
== Rekursive DFS ==
[[Bild:Croxeldyffic_Dfsrek.GIF|thumb|390px|right|Das Voranschreiten der rekursiven Tiefensuche mit Einfärben in einem gerichteten Graphen]]
<ul> <li> Eingaben:
<ol>
<li> Graph $G$ als Adjazenzlisten- oder -matrixdarstellung</li>
<li> Eine Menge von Knoten $V(G)$mit den Zuständen:</li>
<ol>
<li> $farbe=weiss$ für unbesuchte Knoten
<li> $farbe=grau$ für besuchte Knoten</li>
<li> $farbe=schwarz$ für abgeschlossene Knoten<br><br></li>
<li> $\pi=nil$ (der Vorgänger)</li>
<li> $d[u]=0$ (die Zeit der Entdeckung)</li>
<li> $f[u]=0$ (die Zeit des Abschließens) </li>
</ol>
</ol>
<div style="background-color:#EEE">
'''Algorithmus:''' ''DFSrek (Graph $G$)'' <br>
<math>
\begin{array}{l|l}
1 & \mathbf{for}\; alle Knoten\; u\in V(G)\\
2 &\;\;\;\;\; \mathbf{do} farbe[u] \leftarrow weiss\\
3 &\;\;\;\;\; \pi[u] \leftarrow NIL\\
4 & zeit \leftarrow 0\\
5 & \mathbf{for}\; alle Knoten\; u\in V(G)\\
6 &\;\;\;\;\; \mathbf{do}\;\mathbf{if}\; farbe[u] = weiss\\
7 &\;\;\;\;\;\;\;\;\;\;\;\mathbf{then} \;DFSvisit(u)\\
\end{array}
</math><br>
'''end''' ''DFSrek''
</div>
<div style="background-color:#EEE">
'''Algorithmus:''' ''DFSvisit ($u$)'' <br>
<math>
\begin{array}{l|l}
1 & farbe[u] \leftarrow grau\\
2 & zeit \leftarrow zeit+1\\
3 & \pi[u] \leftarrow zeit\\
4 & \mathbf{for}\; alle\; v \in Adj(u)\\
5 & \;\;\;\;\; \mathbf{do}\;\mathbf{if}\; farbe[v] = weiss\\
6 & \;\;\;\;\;\;\;\;\;\;\;\mathbf{then} \;\pi[v] \leftarrow u\\
7 & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ DFSvisit(v)\\
8 & farbe[u] \leftarrow schwarz\\
9 & f[u] \leftarrow zeit \leftarrow zeit+1\\
\end{array}
</math><br>
'''end''' ''DFSvisit''
</div></li>
</ul>
<popup title="Funktion">
<div>
<table cellpadding="3" cellspacing="0" width="100%" style="border: 1px solid #D6D6D6; background-color:#F9F9F9; font-family:Courier New;">
<tr>
<td align="right" valign="top" style="background-color:#F0F0F0; color:#817F7D; font-size:0.8em" width="20px">
1<br>
2<br>
3<br>
4<br>
5<br>
6<br>
7<br>
8<br>
9<br>
10<br>
11<br>
12<br>
13<br>
14<br>
15<br>
16<br>
17<br>
18<br>
19<br>
20<br>
21<br>
22<br>
23<br>
24<br>
25<br>
26<br>
27<br>
28<br>
29<br>
30<br>
31<br>
32<br>
33<br>
34<br>
35<br>
36<br>
37<br>
38<br>
39<br>
40<br>
41<br>
42<br>
43<br>
44<br>
45<br>
46<br>
47<br>
48<br>
49<br>
50<br>
51<br>
52<br>
53<br>
54<br>
55<br>
</td>
<td valign="top">
<font color="#C92120"><b>public void</b></font> dfsrek((<font color="#C92120"><b>int</b></font> start, (<font color="#C92120"><b>char</b></font> c)
{
System.out.println(<font color="#00F"><b> "\n\nDFS-Durchlaufordnung(rekursiv): "</b></font>);
start--;
<font color="#C92120"><b>for</b></font> (<font color="#C92120"><b>int</b></font> j=0; j<knoten; j++)
{
knotenliste[j].farbe = <font color="#00F"><b> "weiss"</b></font>;
knotenliste[j].prev = null;
}
zeit = 0;
<font color="#C92120"><b>for</b></font> (<font color="#C92120"><b>int</b></font> j=start; j<knoten; j++)
{
<font color="#C92120"><b>if</b></font> (knotenliste[j].farbe == <font color="#00F"><b> "weiss"</b></font>)
dfsvisit(j, c);
}
<font color="#C92120"><b>if</b></font> (start != 0)
<font color="#C92120"><b>for</b></font> (<font color="#C92120"><b>int</b></font> j = 0; j < start; j++) {
<font color="#C92120"><b>if</b></font> (knotenliste[j].farbe == <font color="#00F"><b> "weiss"</b></font>)
dfsvisit(j, c);
};
<font color="#C92120"><b>for</b></font>(<font color="#C92120"><b>int</b></font> j=0; j<knoten; j++)
{
displayVertex(j, <font color="#00F"><b> "erweitert"</b></font>);
System.out.println();
};
}
<font color="#C92120"><b>public void</b></font> dfsvisit(<font color="#C92120"><b>int</b></font> u, <font color="#C92120"><b>char</b></font> c)
{
knotenliste[u].farbe = <font color="#00F"><b> "grau"</b></font>;
zeit++;
knotenliste[u].gefunden = zeit;
<font color="#C92120"><b>if</b></font> (knotenliste[u].label == c)
System.out.println(c + <font color="#00F"><b> " in Schritt "</b></font> + knotenliste[u].gefunden + <font color="#00F"><b> " gefunden\n"</b></font>);
<font color="#C92120"><b>for</b></font> (<font color="#C92120"><b>int</b></font> j=0; j<knoten; j++)
<font color="#C92120"><b>if</b></font> (adjazenzMatrix[u][j] == 1 && knotenliste[j].farbe == <font color="#00F"><b> "weiss"</b></font>) {
knotenliste[j].prev = knotenliste[u];
dfsvisit(j, c);}
knotenliste[u].farbe = <font color="#00F"><b> "schwarz"</b></font>;
zeit++;
knotenliste[u].abgearbeitet = zeit;
topologie.push(u + 1);
}
}
</td>
</tr>
</table>
</div>
</popup>
==Klassifizierung der Kanten==
Wie schon beschrieben erzeugt die DFS einen vom Durchlauf abhängigen Tiefensuchwald. Man kann nun jede Kante einem von vier Typen zuordnen, entsprechend ihrer Sondierung in der DFS
<ul><li> Typen:
<ol>
<li> '''Baumkanten''' sind Kanten im Tiefensuchwald $G_\pi$ . Kante $(u,v)$ ist eine Baumkante, falls $v$ bei der Sondierung der Kante $(u,v)$ entdeckt wurde</li>
<li> '''Rückwärtskanten''' sind Kanten $(u,v)$, die $u$ mit einem Vorfahren $v$ im Tiefensuchbaum verbinden. Ebenso Schlingen in gerichteten Graphen</li>
<li> '''Vorwärtskanten''' sind alle nicht-Baumkanten $(u,v)$ die $u$ mit einem Nachfahren $v$ im Tiefensuchbaum verbinden</li>
<li> '''Querkanten''' sind alle verbliebenen Kanten, solange nicht der eine Vorfahre des anderen ist</li>
</ol>
= Breitendurchlauf/ -suche =
[[Bild:Croxeldyffic_Bfs01.gif|thumb|390px|right|Das Voranschreiten einer Breitensuche in einem gerichteten Graphen]]
Während die Tiefensuche zunächst einem Pfad bis zur nächsten Sackgasse folgt und dabei recht unbalancierte Suchwälder erzeugt, kommt die Breiten einem vorsichtigerem Voranschreiten gleich. Bevor das Verfahren einen weiteren Schritt in die Tiefe unternimmt, werden zunächst alle Knoten auf der momentanen Ebene (engl. ''Layer'') besucht. Von einem Startknoten $v$ werden also zunächst alle Knoten mit dem Abstand $d(v)=1$, d.h. alle unmittelbaren Nachbarknoten untersucht und in den nächsten Schritten jeweils alle Knoten mit dem Abstand $d+1$, d.h. alle Nachfolger der Nachfolger.
Dieses schichtweise Voranschreiten hat zwei Vorteile gegenüber der Tiefensuche:
# Es werden ausbalancierte Suchwälder erzeugt.
# Es wird sichergestellt, dass das Verfahren mit Sicherheit bei einer Knotensuche terminiert, falls sich das gesuchte Element im Graphen befinden sollte. Bei der Tiefensuche kann es dagegen passieren, bei Zyklen eine Endlosschleife zu produzieren, falls man bei der Implementation das Auftreten von Kreisen nicht berücksichtigt.
Abgeleitet von der allgemeinen Durchlaufvorschrift unter Benutzung einer Warteschlange $Q$ als Arbeitsliste, beschreibt folgender Algorithmus die Arbeitsweise der Breitensuche.
<div style="background-color:#EEE; max-width:600px">
'''Algorithmus:''' ''Breitendurchlauf (Graph $G$, Knoten $v \in V(G)$, Queue $Q$)'' <br>
<math>
\begin{array}{l|l}
1 & v \leftarrow besucht\\
2 & Q \leftarrow enqueue(v)\\
3 & \mathbf{while}\; (Q \neq\: \emptyset)\; \mathbf{do} \\
4 &\;\;\;\;\; \text{\small waehle Knoten } v \in Q \text{\small mit } v = peek(Q) \\
5 &\;\;\;\;\;\; \mathbf{if}\; (\!\text{\small es gibt } u \in V(G) \text{\small mit } u=Nachbar\; von\; v \text{\small und } u=unbesucht)\; \mathbf{then} \\
6 &\;\;\;\;\;\;\;\;\;\;\;\; u \leftarrow besucht\\
7 &\;\;\;\;\;\;\;\;\;\;\;\; Q \leftarrow enqueue(u)\\
8 &\;\;\;\;\;\; \mathbf{else}\; Q \leftarrow dequeue(u) \\
\end{array}
</math><br>
'''end''' ''Breitendurchlauf''
</div>
Der Algorithmus kann aufgrund seiner klaren Struktur sehr einfach in Programmcode übertragen werden. Wie wir bereits bei der DFS-Implementierung mit Stack bemerkt haben, können wir mit diesem Algorithmus nur zusammenhängende Graphen durchlaufen.
<popup title="Funktion">
<div>
<table cellpadding="3" cellspacing="0" width="100%" style="border: 1px solid #D6D6D6; background-color:#F9F9F9; font-family:Courier New;">
<tr>
<td align="right" valign="top" style="background-color:#F0F0F0; color:#817F7D; font-size:0.8em" width="20px">
1<br>
2<br>
3<br>
4<br>
5<br>
6<br>
7<br>
8<br>
9<br>
10<br>
11<br>
12<br>
13<br>
14<br>
15<br>
16<br>
17<br>
18<br>
19<br>
20<br>
21<br>
22<br>
23<br>
24<br>
25<br>
26<br>
27<br>
28<br>
29<br>
30<br>
31<br>
32<br>
33<br>
34<br>
35<br>
36<br>
37<br>
38<br>
39<br>
40<br>
</td>
<td valign="top">
<font color="#C92120"><b>public void</b></font> bfs (<font color="#C92120"><b>int</b></font> start)
{
System.out.println(<font color="#00F"><b> "BFS-Durchlaufordnung:" </b></font>);
start--;
knotenliste[start].bereitsBesucht = true;
displayVertex(start);
theQueue.enqueue(start);
<font color="#C92120"><b>while</b></font> ( !theQueue.istLeer() )
{
<font color="#C92120"><b>int</b></font> v = naechsterUnbesuchterNachbar( theQueue.peek() );
<font color="#C92120"><b>if</b></font> (v == -1)
theQueue.dequeue();
<font color="#C92120"><b>else</b></font>
{
knotenliste[v].bereitsBesucht = true;
displayVertex(v);
theQueue.enqueue(v);
}
}
<font color="#C92120"><b>for</b></font>(<font color="#C92120"><b>int</b></font> i=0; i<knotenanzahl;i++){
<font color="#C92120"><b>if</b></font>(knotenliste[i].bereitsBesucht==false){
System.out.println(<font color="#00F"><b>"... Graph nicht zusammenhängend!"</b></font>);
break;}
<font color="#C92120"><b>else</b></font> continue;
}
<font color="#C92120"><b>for</b></font>(<font color="#C92120"><b>int</b></font> j=0; j<knotenanzahl; j++)
knotenliste[j].bereitsBesucht = false;
}
</td>
</tr>
</table>
</div>
</popup>
<run id="4faeef3199c94">
G_PDF09 = Graph(6, "gerichtet");
G_PDF09.addVertex('A'); // 1 (start)
G_PDF09.addVertex('B'); // 2
G_PDF09.addVertex('C'); // 3
G_PDF09.addVertex('D'); // 4
G_PDF09.addVertex('E'); // 5
G_PDF09.addVertex('F'); // 5
G_PDF09.addEdge(1, 2); // A-B
G_PDF09.addEdge(1, 4); // A-D
G_PDF09.addEdge(1, 6); // A-F
G_PDF09.addEdge(2, 3); // B-C
G_PDF09.addEdge(2, 4); // B-D
G_PDF09.addEdge(3, 4); // C-D
G_PDF09.addEdge(3, 5); // C-E
G_PDF09.addEdge(3, 6); // C-F
G_PDF09.addEdge(4, 5); // D-E
G_PDF09.addEdge(4, 3); // D-C
G_PDF09.addEdge(5, 6); // E-F
G_PDF09.zeigeAdjMatrix();
G_PDF09.bfs(1);
</run>
'''Übungsaufgaben:'''
<ol>
<li> Durchlaufen Sie die folgenden Graphen zunächst per Hand und überprüfen Sie Ihre Lösung anschließend mit dem Programm.
<ol style="list-style-type:lower-alpha">
<li> $G_1$ </li>
<li> $G_2$ (''Was fällt bei diesem Graphen auf? Interpretieren Sie die Programmausgabe.'') </li>
</ol>
<gallery widths="300px" heights="300px">
</gallery>
</li>
<li> Testen Sie das BFS-Applet auf: [http://www.lupinho.net/lupinho.de/gishur/html/BFSApplet.html Lupinho.de] mit
<ol style="list-style-type:lower-alpha">
<li> einem ungerichteten Graphen. </li>
<li> einem gerichteten Graphen. </li>
<li> einen unzusammenhängenden Graphen. </li>
</ol>
</li>
</ol>
* graph geben und bfs per hand berechnen lassen, mit prog überprüfen
* applet
== erzeugter Suchbaum ==
= Iterative Tiefensuche (Kombination) =
= Anwendung/ weiterführende Themen =
== Topologisches Sortieren ==
Die Topologische Sortierung reiht alle Knoten eines azyklischen Graphen $G$ in einer Linie auf. $u$ ligt vor $v$ falls es in $G$ eine Kante $(u,v)$ gibt. Alle gerichteten Kanten zeigen nun von links nach rechts.<br>
Topologisch sortierte Knoten eines Graphen $G$ sind in der umkehrten Reihenfolge ihrer Endzeiten in der DFS angeordnet.<br><br>
Topological-Sort($G$)
<ol>
<li> DFS($G$) aufrufen um die Endzeiten $f[u]$ für alle Knoten $u$ zu bekommen</li>
<li> jeden abgearbeiteten Knoten am Kopf einer Liste $L$ einfügen</li>
<li> $L$ ist nun topologisch sortiert</li>
</ol><br>
Die topologische Sortierung wird zur Darstellung der Priorität von Ereignissen verwendet.<br>
'''Das Beispiel:'''<br>
[[Bild:Croxeldyffic_Topo01.PNG|thumb|450px|a) gerichteter Graph der Kleidung, mit Enddeckungs und Endzeiten]]
[[Bild:Croxeldyffic_Topo02.PNG|thumb|900px|b) Graph der Kleidung, topologisch sortiert nach ]]
Professor Bumstead führt eine topologische Sortierung seiner Kleidung durch, wenn er sich anzieht. <br>
Wenn man entwas mit den Startwerten der DFS experimentiert, sieht man, dass sich aufgrund der verschiedenen Suchwälder auch verschiedene Topologische sortierungen einstellen. Es wird aber nie z.B. das Jacket vor der Kravatte angezogen. Die Position von isolierten Knoten(der Uhr) ist hingegen beliebig.
<run id="4fafabc989387" >
sachen = Graph(9,"gerichtet");
sachen.addVertex('A'); //1//Unterhose
sachen.addVertex('B'); //2//Hose
sachen.addVertex('C'); //3//Guertel
sachen.addVertex('D'); //4//Hemd
sachen.addVertex('E'); //5//Kravatte
sachen.addVertex('F'); //6//Jacket
sachen.addVertex('G'); //7//Socken
sachen.addVertex('H'); //8//Schuhe
sachen.addVertex('I'); //9//Uhr
sachen.addEdge(1,2);
sachen.addEdge(1,8);
sachen.addEdge(2,8);
sachen.addEdge(2,3);
sachen.addEdge(3,6);
sachen.addEdge(7,8);
sachen.addEdge(4,3);
sachen.addEdge(4,5);
sachen.addEdge(5,6);
sachen.dfsrek(1,'#');
sachen.displayTopo();
</run>
== Euler und CPP ==
===Eulerpfad/-kreis===
[[Bild:Croxeldyffic_Euler02.PNG|300px|Beschreibung]]
[[Bild:Croxeldyffic_Nikolaus01.PNG|300px|Beschreibung]]
Das Eulerkreis Problem hat seinen Ursprung in dem Vorhaben von Leonhard Eulers, alle fünf Stadtteile von Königsberg zu besuchen, dabei jede Brücke aber nur einmal zu überqueren und am Startpunkt wieder anzukommen.<br>
Siehe dazu:[http://programmingwiki.de/AuK/Graphrepr%C3%A4sentationen_SS12#K.C3.B6nigsberger_Br.C3.BCckenproblem Königsberger Brückenproblem]
<br>
Bevor man versucht einen Eulerkreis zu finden, wird der Graph $G$ geprüft, ob er überhaupt einen zulässt. Dazu ermittelt man den Grad aller Knoten und zählt wieviele geraden/ungeraden Grades sind.
<ul>'''eulersch''' wenn:
<ol>''gerichtet'' und
<li>stark zusammenhängend </li>
<li>bei jedem Knoten ist Eingangsgrad=Ausgangsgrad</li>
</ol>
<ol>''ungerichtet'' und
<li>zusammenhängend</li>
<li>jeder Knoten hat geraden Grad</li>
</ol>
<br>
Wenn zwei oder kein Knoten ungeraden Grad haben, eistiert in einem ungerichteten, zusammenhängenden Graphen ein Eulerweg/pfad.
<br>
Auch wenn schnellere Algorithmen gibt(z.B. der Algorithmus von Hierholzer) wird hier der Algorithmus von Fleury kurz vorgestellt:
<ul>'''Algorithmus von Fleury'''
<ol>
<li> wähle beliebigen Startknoten $u \in V(G)$
<li> wähle eine an $u$ angrenzende Kante, wähle zuerst Kanten die keine Brückenkanten sind
<li> füge die Kante der Liste des Eulerkreises hinzu, Kante markieren
<li> den anderen Knoten der gewählten Kante als neuen aktuellen knoten wählen
<li> existieren noch unmarkierte Kanten wieder zu Schritt 2
</ol><br>
'''Laufzeit:''' $\mathcal{O}(|E|^2)$ $\leftarrow$ (Brückenkante finden $\mathcal{O}(|E|)$, Kanten absuchen $\mathcal{O}(|E|)$, Iterationen $|E|$
</ul>
<run id="4fa6e6115a107">
nikolaus = Graph(5, "ungerichtet");
nikolaus.addVertex('A'); // 1 (start)
nikolaus.addVertex('B'); // 2
nikolaus.addVertex('C'); // 3
nikolaus.addVertex('D'); // 4
nikolaus.addVertex('E'); // 5
nikolaus.addEdge(1, 2); // A-B
nikolaus.addEdge(1, 3); // A-D
nikolaus.addEdge(1, 4); // A-F
nikolaus.addEdge(2, 3); // B-C
nikolaus.addEdge(2, 4); // B-D
nikolaus.addEdge(3, 4); // C-D
nikolaus.addEdge(3, 5); // C-E
nikolaus.addEdge(4, 5); // D-E
nikolaus.zeigeAdjMatrix();
nikolaus.pruefeGrad();
nikolaus.dfsrek(1,'#');
nikolaus.ermittleKantenart();
nikolaus.fleury();
nikolaus.displayEulerliste();
</run>
===CPP===
Das Chinese Postman Problem (dt. ''Briefträgerproblem'') erhielt seinen Namen vom chinesischen Mathematiker Mei Ko Kwan, der das Problem erstmals 1962 untersuchte. <br>
Inhalt des Problems ist die Frage nach dem besten Weg um Briefe zuzustellen. Jede Straße wird hierbei als Kante und jede Straßenkreuzung als Knoten in einem Straßennetzwerk(Graph) modelliert. Der Postbote muss nun jede Straße(Kante) ''genau einmal'' ablaufen, um alle Adressaten zu erreichen und dennoch nicht zu viel zu laufen.<br>
Damit kann man das CPP lösen, wenn man einen Eulerkreis findet.<br>
Leider sind reale Straßennetze nicht immer eulersch, das Thema soll hier jedoch nicht weiter vertieft werden.
== Hamilton und TSP==
== Starke Zusammenhangskomponenten ==
= Java-Test =
<run id="4f9875926c9de">
//G1 von S.145
//zur differenzierung ungeeignet - bfs & dfs liefern gleiche ordnung!
//G aus PDF-09 besser!!
theGraph = Graph(6, "gerichtet");
theGraph.addVertex('A'); // 1 (start)
theGraph.addVertex('B'); // 2
theGraph.addVertex('C'); // 3
theGraph.addVertex('D'); // 4
theGraph.addVertex('E'); // 5
theGraph.addVertex('F'); // 6
theGraph.addEdge(1, 2); // A-B
theGraph.addEdge(1, 4); // A-D
theGraph.addEdge(1, 6); // A-F
theGraph.addEdge(2, 3); // B-C
theGraph.addEdge(2, 4); // B-D
theGraph.addEdge(3, 4); // C-D
theGraph.addEdge(3, 5); // C-E
theGraph.addEdge(3, 6); // C-F
theGraph.addEdge(4, 5); // D-E
theGraph.addEdge(4, 3); // D-C
theGraph.addEdge(5, 6); // E-F
theGraph.zeigeAdjMatrix();
theGraph.dfs();
theGraph.dfsrek(1);
theGraph.bfs();
theGraph.pruefeGrad();
//funktioniert prinzipiell
/* TODO:
* konstruktor mit parameterübergabe (x)
* nutzereingabe optimieren (d.h. edge 1 = array-index 1) (x)
* adjazenzmatrix darstellen (mit rand) (x)
* queue implementieren + bfs (x)
* fallunterscheidung gerichtet-ungerichtet (x)
* YAY~ :D
* eulerprüfung(code) mit pfadangabe(pseudo) (~)
* hamiltonprüfung(code) mit pfadangabe(pseudo) (~)
* DFS von beliebigem startknoten (~)
* SCC ( )
*/
</run>
<run id="4fa6e6115a107">
nikolaus = Graph(5, "ungerichtet");
nikolaus.addVertex('A'); // 1 (start)
nikolaus.addVertex('B'); // 2
nikolaus.addVertex('C'); // 3
nikolaus.addVertex('D'); // 4
nikolaus.addVertex('E'); // 5
nikolaus.addEdge(1, 2); // A-B
nikolaus.addEdge(1, 3); // A-D
nikolaus.addEdge(1, 4); // A-F
nikolaus.addEdge(2, 3); // B-C
nikolaus.addEdge(2, 4); // B-D
nikolaus.addEdge(3, 4); // C-D
nikolaus.addEdge(3, 5); // C-E
nikolaus.addEdge(4, 5); // D-E
nikolaus.zeigeAdjMatrix();
nikolaus.pruefeGrad();
nikolaus.ermittleKantenart();
nikolaus.fleury();
nikolaus.displayEulerliste();
</run>
<run id="4fa9861cdf0d1">
sachen = Graph(9,"gerichtet");
sachen.addVertex('A'); //1//Unterhose
sachen.addVertex('B'); //2//Hose
sachen.addVertex('C'); //3//Guertel
sachen.addVertex('D'); //4//Hemd
sachen.addVertex('E'); //5//Kravatte
sachen.addVertex('F'); //6//Jacket
sachen.addVertex('G'); //7//Socken
sachen.addVertex('H'); //8//Schuhe
sachen.addVertex('I'); //9//Uhr
sachen.addEdge(1,2);
sachen.addEdge(1,8);
sachen.addEdge(2,8);
sachen.addEdge(2,3);
sachen.addEdge(3,6);
sachen.addEdge(7,8);
sachen.addEdge(4,3);
sachen.addEdge(4,5);
sachen.addEdge(5,6);
sachen.dfsrek(1);
sachen.displayTopo();
</run>
<run id="4fad1e5012b57">
kantentest = Graph(6,"gerichtet");
kantentest.addVertex('u');//1
kantentest.addVertex('v');//2
kantentest.addVertex('w');//3
kantentest.addVertex('x');//4
kantentest.addVertex('y');//5
kantentest.addVertex('z');//6
kantentest.addEdge(1,2);
kantentest.addEdge(1,4);
kantentest.addEdge(2,5);
kantentest.addEdge(3,5);
kantentest.addEdge(3,6);
kantentest.addEdge(4,2);
kantentest.addEdge(5,4);
kantentest.addEdge(6,6);
kantentest.dfsrek(1);
kantentest.displayTopo();
kantentest.ermittleKantenart();
kantentest.displayKantenart(0);
</run>