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$.

[[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>

==Topologisches Sortieren==
==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]