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