depth first search

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 B. Trifft 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).

Zurück zur Hauptseite Computerorientierte Mathematik.