Bei dieser Traversierungsart handelt es sich um eine Tiefensuche. D.h. der Algorithmus bearbeitet alle (vom Startknoten erreichbaren Knoten) genau einmal, wobei die Rekursion als erstes möglichst tief absteigt.
algorithm search
input G = (V, E) - ein ungerichteter Graph
T, B - Kantenmenge
v - Startknoten
visit(v) ; Knoten markieren
forall (v,u)
E do
if visited(u) then ; Knoten u wurde schon besucht
B := B
(v,u)
else ; Knoten ist unbesucht
T := T
(v,u)
search(u)
algorithm dfs
input G = (V, E) - ein ungerichteter Graph
T :=
B :=
count := 0
for v := 1 to
V
do
if !visited(v) then
count := count + 1
search(G, T, B, v)
Die Kanten, die search
benutzt, um einen weiteren unmarkierten
Knoten zu erreichen, werden zu T
hinzugefügt. Nach Ablauf
des Algorithmus enthält T
die Kanten eines aufspannenden
Baumes (für jede Komponente) des Graphen. search
markiert
alle Knoten der selben Zusammenhangskomponente wie v
. Findet
dfs
in der Schleife einen weiteren unmarkierten Knoten,
gehört dieser zu einer anderen Komponente, welche dann ebenfalls
vollständig markiert wird. count
zählt die Anzahl
dieser Komponenten.
G
ist ein ungerichteter Graph und E
, T
und B
sind Mengen von ungeordneten Paaren von Knoten und es gilt
E = T
. Trifft
B
search
auf eine Kante zu einem markierten Knoten
(if visited(u)
), würde das Hinzufügen dieser Kante zu
T
einen Kreis erzeugen. Ist B
am Ende von
dfs
immer noch leer, dann ist G
kreisfrei.
Der Algorithmus lässt sich mit Hilfe eines Stacks auch iterativ implementieren.
algorithm search
input G = (V, E) - ein ungerichteter Graph
T, B - Kantenmenge
v - Startknoten
S := new Stack
S.push(v)
while !S.isEmpty() do
v := S.pop()
if !visited(v) then
visit(v)
forall (v,u)
E do
if visited(u) then
B := B
(v,u)
else
T := T
(v,u)
S.push(u)
Bei einem Baum entspricht dfs
in etwa einer Preorder
Traversierung. Eine andere Möglichkeit ist die ebenenweise Traversierung.
Ein entsprechender Algorithmus bei Graphen ist breadth first search. Dazu muss
einfach der Stack durch eine Queue (FIFO) ersetzt werden. Dann werden erst
alle von v
aus erreichbaren Knoten markiert, bevor der
Algorithmus weiter entfernte Kanten besucht. BFS sortiert die Knoten nach dem
Abstand vom Startknoten (mit Kantengewicht 1).
Programm | Beschreibung |
dfs.c | der DFS Algorithmus, spechert den aufspannenden Baum oder liefert einen Kreis |
graphio.h | die Bibliothek zum Einlesen un Speichern von Graphen |
graphio.c |
Zurück zur Hauptseite Computerorientierte Mathematik.