Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Tiefendurchlauf

Tiefendurchlauf

Auf dieser Seite wird der Tiefendurchlauf behandelt. Der Tiefendurchlauf wird auch Depth-First-Search, oder abgekürzt DFS, genannt. Die Knoten werden aufgezählt indem vom Startknoten aus ein Pfad so weit wie möglich verfolgt wird und bei Bedarf ein Backtracking durchgeführt wird. Bei Tiefendurchlauf werden die Knoten ebenfalls farblich markiert. Weiß bedeutet der Knoten ist noch nicht bearbeitet, grau bedeutet der Knoten ist in Bearbeitung und schwarz bedeutet der Knoten ist bereits fertig abgearbeitet.

Ergänzung zum Graph Interface:

public interface Graph{
   public int addNode();
   public boolean addEdge(int orig, int dest);
   public Collection<Integer> getChildren(int node);
   public Collection<Integer> getNodes();
}

Algorithmus

enum Color {WHITE, GRAY, BLACK};

Map<Integer,Color> color = new HashMap<Integer,Color>();
Map<Integer,Integer> pi = new HashMap<Integer,Integer>();
Map<Integer,Integer> f = new HashMap<Integer,Integer>();
Map<Integer,Integer> d = new HashMap<Integer,Integer>();

int time = 0;

color speichert die Farbe, bzw. den Bearbeitungszustand eines Knotens.

pi speichert den Vorgänger eines Knotens beim Durchlauf.

f speichert den Zeitpunkt des Bearbeitungsbeginns eines Knotens.

d speichert den Zeitpunkt des Bearbeitungsendes eines Knotens.

public void dfs(Graph g){ 
   for(Integer n: g.getNodes())
      color.put(n, Color.WHITE); 
   for(Integer n: g.getNodes())
      if(color.get(n).equals(Color.WHITE))
          dfsVisit(g,n); 
}

public void dfsVisit(Graph g, Integer n){
   color.put(n, Color.GRAY);
   time++;
   d.put(n, time);
   for(Integer m: g.getChildren(n)){
      if(color.get(m).equals(Color.WHITE)){
         pi.put(m, n);
         dfsVisit(g,m);
      } 
   }
   color.put(n, Color.BLACK);
   time++;
   f.put(n, time);
}

Vorgehen

Der Tiefendurchlauf ist ein rekursiver Abstieg. Pro Knoten haben wir zwei Werte und deren Farbwerte. Beginn der Bearbeitung ist d und Ende der Bearbeitung ist f. Der rekursive Aufruf erfolgt nur bei weißen Knoten, die Terminierung der Rekursion ist hier garantiert. Die Ausführung von DFS resultiert in einer Folge von DFS-Bäumen. Der erste Baum wird aufgebaut bis keine Knoten mehr hinzugefügt werden können. Anschließend wird ein unbesuchter Knoten gewählt und fortgefahren. Bei den Kanten des aufgespannten Baumes ist der Zielknoten beim Test weiß. An den B-Kanten ist der Zielknoten beim Test grau. Hierbei handelt es sich um Back Edges oder Rückkanten im aufgespannten Baum. Eine mit B markierte Kante zeigt einen Zyklus an. Bei F Kanten werden beim Test schwarze Knoten gefunden, dessen Bearbeitungsintervall ins Intervall des aktuellen bearbeiteten Knotens passt. Es handelt sich hierbei um Forward Edges bzw. Vorwärtskanen in dem aufgespannten Baum. Bei C Kanten haben wir schwarze Zielknoten v, dessen Intervalle nicht in das aktuelle Intervall passen (d[u]>f[v]). Hierbei handelt es sich um Cross Edges, eine Kante die zwei aufgespannte Bäume verbindet.

Beispiel

Die Notation an den Knoten ist dabei durch <Beginn der Bearbeitung d> / <Ende der Bearbeitung f> gegeben.

Analyse

Theorem der Terminierung

Die Tiefensuche terminiert nach endlicher Zeit.

Theorem der Korrektheit

Es werden alle Knoten von G genau einmal besucht.

Theorem der Laufzeit

Ist sowohl die Laufzeit von getChidlren linear in der Anzahl der Kinder als auch getNodes linear in der Anzahl der Knoten, so hat die Tiefensuche eine Laufzeit von O(|V|+|E|).

Anwendung

Der Tiefendurchlauf wird beispielsweise bei dem Test auf Zyklenfreiheit verwendet. Damit ein Graph zyklenfrei ist, darf kein Kreis K in dem Graph G vorhanden sein. Deshalb basiert dieser Test auf dem Erkennen von Back Edges. Er ist effizienter als beispielsweise die Konstruktion einer transitiven Hülle. Die Tiefensuche wird aber auch beim topologischen Sortieren verwendet. Topologisch bedeutet sortieren nach Nachbarschaft, nicht nach totaler Ordnung.