Durchläufe durch Graphen WS13-14

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2014-01-05T14:47:07+00:00. Aktuelle Version

Inhaltsverzeichnis

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 Systematischen Suche schon kurz behandelt worden sind. Einfach weiterentwickelte Durchsuchungsalgorithmen werden als Graphenalgorithmen bezeichnet.

Hinweis: 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.

Breitensuche

Die Breitensuche beschäftigt sich mit dem systematischen Suchen in einem Graphen. Sie ist einer der einfachsten Algorithmen dieser Art.
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.

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

Um Prozedur BFS (Breadth-first search) durchzuführen, muss der eingegebene Graph durch Adjazenzlisten dargestellt werden.

BFS (G,s)
1 for alle Knoten u \in V[G] - {s}
2 \;\;\;\;\; do farbe[u] \leftarrow WEISS
3 \;\;\;\;\;\;\;\;\;\; d[u] \leftarrow \infty
4 \;\;\;\;\;\;\;\;\;\; \pi[u] \leftarrow NIL
5 farbe[s] \leftarrow GRAU
6 d[s] \leftarrow 0
7 \pi[s] \leftarrow NIL
8 Q \leftarrow \empty
9 ENQUEUE(Q,s)
10 while Q \ne \empty
11 \;\;\;\;\; do u \leftarrow DEQUEUE(Q)
12 \;\;\;\;\;\;\;\;\;\; for alle v \in Adj[u]
13 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; do if farbe[v] = WEISS
14 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; then farbe[v] \leftarrow GRAU
15 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; d[v] \leftarrow d[u] + 1
16 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \pi[v] \leftarrow u
17 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; ENQUEUE(Q,v)
18 \;\;\;\;\;\;\;\;\;\; farbe[u] \leftarrow SCHWARZ

Tiefensuche

DFS (G)
1 for alle Knoten u\in V[G]
2 \;\;\;\;\; do farbe[u] \leftarrow WEISS
3 \;\;\;\;\;\;\;\;\;\; \pi[u] \leftarrow NIL
4 zeit \leftarrow 0
5 for alle Knoten u\in V[G]
6 \;\;\;\;\; do if farbe[u] = WEISS
7 \;\;\;\;\;\;\;\;\;\; then DFS-VISIT(u)

DFS-VISIT (u)
1 farbe[u] \leftarrow GRAU \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; weißer Knoten u entdeckt
2 zeit \leftarrow zeit+1
3 d[u] \leftarrow zeit
4 for alle v \in Adj(u) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; verfolge Kante (u,v)
5 \;\;\;\;\; do if farbe[v] = WEISS
6 \;\;\;\;\;\;\;\;\;\;\; then \pi[v] \leftarrow u
7 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; DFS-VISIT(v)
8 farbe[u] \leftarrow SCHWARZ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; u abgearbeitet
9 f[u] \leftarrow zeit \leftarrow zeit+1

Topologisches Sortieren

Starke Zusammenhangskomponenten

Übungen

Literaturverzeichnis

Kontakt

Stefanie Feuerriegel
Damaris Soldan