AuK/Durchläufe durch Graphen WS13-14

Wiki-Quelltext dieser Seite.

==Einleitung==

Für einen '''Graphendurchlauf''' bzw. das Durchsuchen eines Graphen gibt es viele Verfahren und Darstellungsmethoden, die vor allem die Basis für Graphenalgorithmen bilden. Beim ''Durchsuchen'' werden systematisch alle Kanten eines Graphen verfolgt und die Knoten aufgesucht. Wird ein Durchsuchungsalgorithmus auf einen Graphen angewandt, kann dieser Aufschluss über die Struktur dessen geben. Beispiele für solche Durchsuchungsalgorithmen sind die '''Tiefen-''' und '''Breitensuche''', die in der Vorlesung zur [http://programmingwiki.de/AuK/Systematische_Suche_WS13-14 Systematischen Suche] schon kurz behandelt worden sind.
Einfach weiterentwickelte Durchsuchungsalgorithmen werden als ''Graphenalgorithmen'' bezeichnet. 

<div style="background-color:#EEE; border: 1px dashed; max-width:75%">
<p style="padding:10px"><b>Hinweis:</b> Obwohl es sich eigentlich um einen Graphendurchlauf handelt, wird der Begriff "Suche" häufiger benutzt, da er sich von den englischen Bezeichnungen '''DFS''' und '''BFS''' (''depth-first search'' und ''breadth-first search'') ableitet.</p>
</div>

==Breitensuche==

Die '''Breitensuche''' beschäftigt sich mit dem systematischen Suchen in einem Graphen. Sie ist einer der einfachsten
Algorithmen dieser Art. <br />
Wir definieren einen Graphen $G = (V,E)$. Dieser hat einen Startknoten $s$, von welchem aus die Breitensuche beginnt.
Es werden alle Knoten erforscht, die von $s$ aus zugänglich sind. So entsteht ein '''Breitensuchbaum''' mit der Wurzel $s$. Außerdem berechnet der Algorithmus die Abstände der von $s$ aus erreichbaren Knoten. Er arbeitet sowohl in gerichteten als auch ungerichteten Graphen.<br />
<br />
Ihren Namen verdankt die Breitensuche der Tatsache, dass die Entdeckung der Knoten sich gleichmäßig über die gesamte Breite erstreckt.
Das bedeutet, dass der Algorithmus erst alle Knoten mit dem Abstand $k$ von $s$ entdeckt bevor ein Knoten mit $k+1$ bekannt wird.<br />
Um die Breitensuche zu verdeutlichen, werden die Farben ''weiß'', ''grau'' und ''schwarz'' verwendet.
An Anfang sind alle Knoten weiß. Wenn ein Knoten entdeckt wird, wird er grau und kann schließlich schwarz werden.
Es gilt, wenn ein Knoten schwarz oder grau ist, dann ist er bereits entdeckt worden.
Schwarze Knoten können mit schwarzen oder grauen benachbart sein. Graue Knoten können auch mit weißen benachbart sein, da sie die Front zwischen bereits erforschten und unerforschten Knoten darstellen.<br />
<br />
Um Prozedur '''BFS''' (Breadth-first search) durchzuführen, muss der eingegebene Graph durch Adjazenzlisten dargestellt werden.

[[Datei:Breitensuche.png|350px|thumb|right|Anwendung von BFS auf einen ungerichteten Graphen]]

<div style="background-color:#EEE; max-width:500px">
'''BFS''' ($G,s$) <br>
1  '''for''' alle Knoten $u \in V[G]$ - {$s$} <br>
2  $\;\;\;\;\;$ '''do''' $farbe[u] \leftarrow$ WEISS <br>
3  $\;\;\;\;\;\;\;\;\;\;$ $d[u] \leftarrow \infty$ <br>
4  $\;\;\;\;\;\;\;\;\;\;$ $\pi[u] \leftarrow$ NIL <br>
5  $farbe[s] \leftarrow$ GRAU <br> 
6  $d[s] \leftarrow$ 0 <br>
7  $\pi[s] \leftarrow$ NIL <br>
8  $Q \leftarrow \empty$ <br>
9  ENQUEUE($Q,s$) <br>
10  '''while''' $Q \ne \empty$ <br>
11  $\;\;\;\;\;$ '''do''' $u \leftarrow$ DEQUEUE($Q$) <br>
12  $\;\;\;\;\;\;\;\;\;\;$ '''for''' alle $v \in Adj[u]$ <br>
13  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ '''do if''' $farbe[v]$ = WEISS <br>
14  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ '''then''' $farbe[v] \leftarrow$ GRAU <br>
15  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ $d[v] \leftarrow d[u] + 1$ <br>
16  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ $\pi[v] \leftarrow u$ <br>
17  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ ENQUEUE($Q,v$) <br>
18  $\;\;\;\;\;\;\;\;\;\;$ $farbe[u] \leftarrow$ SCHWARZ <br>
</div>


==Tiefensuche==

Die Tiefensuche beschreibt, wie der Name bereits andeutet, das systematische Vordringen in die "Tiefe" eines Graphen und wird häufig als Unterroutine in einem anderen Algorithmus verwendet.<br /> Man startet von einem beliebigen Startknoten $u \in V(G)$ aus und folgt einer benachbarten Kante zum nächsten Knoten. Dabei werden die ungeprüften Kanten des zuletzt entdeckten Knotens untersucht und man gelangt zu weiteren unbesuchten Knoten. Ist ein Blattknoten erreicht, endet der Kantenzug und alle bis dahin entdeckten Knoten wurden markiert. "Die Suche kehrt um", d.h. man folgt dem Kantenzug zurück zu einem Knoten, der noch ungeprüfte Kanten und demnach unbesuchte Knoten besitzt.<br />
Dieser Vorgang wiederholt sich, bis alle vom ursprünglichen Startknoten $u$ aus erreichbaren Knoten entdeckt wurden.<br />
Sollten unentdeckte Knoten übrig bleiben, wird einer von ihnen als neuer Startknoten festgelegt und die Suche wiederholt, bis alle Knoten entdeckt sind.<br />
Durch die verschiedenen Startknoten können mehrere Bäume entstehen, die so genannten '''Tiefensuchbäume'''. Mehrere Tiefensuchbäume bilden einen '''Tiefensuchwald'''.<br />
<br />
Wie bei der Breitensuche gelten die folgenden Markierungen für die Zustände der Knoten:
#'''WEISS''' = unentdeckte Knoten
#'''GRAU''' = entdeckte Knoten
#'''SCHWARZ''' = abgearbeitete Knoten

Ein weiteres Merkmal der Tiefensuche ist, dass sie jeden Knoten $u$ mit zwei Zeitstempeln versieht. Die Zeitstempel sind hilfreich bei Überlegungen zum Verhalten der Tiefensuche und werden in vielen Graphenalgorithmen verwendet. <br />Der erste Zeitstempel $d[u]$ vermerkt, wann $u$ entdeckt (und demnach grau gefärbt) wurde. Der zweite Stempel $f[u]$ zeichnet auf, wann $u$ abgearbeitet (und schwarz gefärbt) wurde, folglich wurde das Prüfen der Adjazenzlsite von $u$ beendet.<br />
Für jeden Knoten $u$ gilt:<br />
:$d[u]$ < $f[u]$.
<br />
Die Prozedur '''DFS''' beschreibt den grundlegenden Algorithmus der Tiefensuche. Er kann auf gerichtete sowie ungerichtete Graphen angewendet werden. <br />
'''Anmerkung:''' Die globale Variable $zeit$ wird für die Zeitstempel verwendet. Und (wie bei der Breitensuche) wird das Vorgängerattribut $\pi[v]$ auf $u$ gesetzt, wenn ein Knoten $v$ entdeckt wird beim Durchsuchen der Adjazenzliste eines bereits entdeckten Knotens $u$.<br />

[[Datei:Tiefensuche.png|350px|thumb|right|Anwendung von DFS auf einen gerichteten Graphen]]

<div style="background-color:#EEE; max-width:600px">
'''DFS''' ($G$) <br>
1  '''for''' alle Knoten $u\in V[G]$ <br>
2  $\;\;\;\;\;$ '''do''' $farbe[u]$ $\leftarrow$ WEISS <br>
3  $\;\;\;\;\;\;\;\;\;\;$ $\pi[u]$ $\leftarrow$ NIL <br>
4  $zeit$ $\leftarrow$ 0 <br>
5  '''for''' alle Knoten $u\in V[G]$ <br>
6  $\;\;\;\;\;$ '''do if''' $farbe[u]$ = WEISS <br>
7  $\;\;\;\;\;\;\;\;\;\;$ '''then''' DFS-VISIT($u$) <br>
<br>

'''DFS-VISIT''' ($u$) <br>
1  $farbe[u]$ $\leftarrow$ GRAU $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ weißer Knoten $u$ entdeckt<br>
2  $zeit \leftarrow zeit+1$ <br>
3  $d[u] \leftarrow zeit$ <br>
4  '''for''' alle$ v \in Adj(u)$ $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ verfolge Kante ($u,v$)<br>
5  $\;\;\;\;\;$ '''do if''' $farbe[v]$ = WEISS <br>
6  $\;\;\;\;\;\;\;\;\;\;\;$ '''then''' $\pi[v] \leftarrow u$ <br>
7  $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ DFS-VISIT($v$) <br>
8  $farbe[u] \leftarrow$ SCHWARZ $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ $u$ abgearbeitet<br>
9  $f[u] \leftarrow zeit \leftarrow zeit+1$  <br>
<br>
</div>
<br />
Der Algorithmus überprüft in Zeile 5-7 der Reihe nach alle Knoten aus $V$ und wendet die rekursive Prozedur '''DFS-VISIT''' an, wenn ein weißer Knoten gefunden wurde. Jedes Mal, wenn DFS-VISIT($u$) in Zeile 7 ausgeführt wird, wird der Knoten $u$ Wurzel eines neuen Baumes des Tiefensuchwaldes.<br />
In Zeile 4 von DFS-VISIT werden nun alle benachbarten Knoten $v$ von $u$ untersucht und man sagt, die Kante ($u,v$) wird '''sondiert'''. Nachdem alle austretenden Kanten aus $u$ sondiert wurden, wird der Knoten schwarz gefärbt. Ist der Algorithmus zu Ende, besitzt jeder Knoten eine Entdeckungszeit $d[u]$ und eine Endzeit $f[u]$.<br />
<br />
'''Bemerkung:''' Die Ergebnisse der Tiefensuche hängen von der Reihenfolge der untersuchten Knoten ab, führen aber in der Praxis zu keinerlei Problemen, da jedes Resultat effektiv genutzt kann.

===Klassifikation der Kanten===

==Topologisches Sortieren==

Bei der topologischen Sortierung geht es um Dinge, bei denen die Reihenfolge eine Rolle spielt. Man kann beispielsweise kein Dach ohne tragende Wände bauen und ebenfalls sollte man die Socken vor den Schuhen anziehen.
Mit Hilfe der Tiefensuche lässt sich '''topologisches Sortieren''' bewerkstelligen. Hierfür ist ein gerichteter azyklischer Graph notwendig. Dieser wird auch "DAG" (''directed acyclic graph'') genannt. <br />
Formell lässt sich sagen, dass eine topologische Sortierung dann vorliegt, wenn es einen DAG $G = (V,E)$ gibt, dessen Knoten sich in einer linearen Anordnung befinden.
Weiterhin müssen sie die Eigenschaft haben, dass $u$, in der Anordnung, vor $v$ liegt. Das gilt nur, wenn in $G$ eine Kante ($u,v$) gibt.<br />
In einer topologischen Sortierung kann man den dargestellten Graphen als eine horizontale Anordnung seiner Knoten verstehen, die gerichtet von links nach rechts zeigen.
<br />
<br />
<div style="background-color:#EEE; max-width:600px">
'''TOPOLOGICAL-SORT'''($G$)<br>
1  rufe DFS($G$) zur Berechnung der Endzeiten $f[v]$ für alle Knoten $v$ auf<br>
2  füge jeden abgearbeiteten Knoten an den Kopf einer verketteten Liste ein<br>
3  '''return''' die verkettete Liste der Knoten <br>
</div>

[[Bild:Topo1.jpg|thumb|600px|left|gerichteter Graph für Beispiel Kleidung, mit Entdeckungs- und Endzeiten]]
[[Bild:Topo2.jpg|thumb|800px|left|Graph in topologisch sortierter Form]]

==Starke Zusammenhangskomponenten==

==Übungen==

==Literaturverzeichnis==
* Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung; Oldenbourg Verlag, 2007
*Güting, Ralf Hartmut: Datenstrukturen und Algorithmen; B.G. Teubner Stuttgart, 1992
*http://wwwiti.cs.uni-magdeburg.de/iti_db/lehre/algds0506/handout2-9.pdf
*http://www.stormware-computer.de/script/kapitel_4_1.pdf
*http://whz-cms-10.zw.fh-zwickau.de/sibsc/lehre/ss10/ad/v13.pdf
*http://www.cs.hs-rm.de/~heimrich/Algorithmen%20&%20Datenstrukturen/Vorlesungen/vorlesung10.pdf

==Kontakt==

:[mailto://s3stfeue@stud.hszg.de Stefanie Feuerriegel]
:[mailto://s3dasold@stud.hszg.de Damaris Soldan]