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.

<div style="background-color:#EEE; max-width:600px">
'''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==

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