TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 28

Die Breitensuche ist ein weiteres Verfahren zum Durchlaufen von Graphen. Der Unterschied zur in der Vorlesung behandelten Tiefensuche liegt in der Reihenfolge, in der die Knoten im Graphen besucht werden. Ausgehend von einem Knoten v werden bei der Breitensuche zuerst alle adjazenten Knoten besucht, bevor der Algorithmus von jedem dieser Knoten aus immer weiter in den Graphen vordringt.

Breitensuche lässt sich mit dem abstrakten Datentyp Queue (Warteschlange) realisieren. Eine Queue kann beliebig viele Elemente aufnehemen und gibt sie in derselben Reihenfolge zurück, in der sie eingefügt wurden. Die folgenden Operationen werden von einer Queue Q zur Verfügung gestellt:

• Q.isEmpty(): Liefert wahr zurück, falls die Queue Q keine Elemente enthält, und falsch sonst.
• Q.put(x): Fügt das Element x der Queue Q hinzu.
• Q.get(): Entfernt das älteste Element in der Queue Q und liefert dieses zurück.

Entwerfen Sie einen Algorithmus in detailliertem Pseudocode, der auf der Breitensuche aufbaut und in einem gerichteten, ungewichteten Graphen G = (V,E) mit zwei gegebenen Knoten s,t $\in$ V den kürzesten Pfad (auf Basis der Anzahl der Kanten) von s nach t ausgibt. Falls kein solcher Pfad existiert, soll eine entsprechende Meldung ausgegeben werden.

Welche Laufzeit hat Ihr Algorithmus in $\Theta$-Notation in Abhängigkeit geeigneter Eingabegrößen? Wie müsste Ihr Algorithmus modifiziert werden, damit er auch auf ungerichteten Graphen funktioniert?

Lösung

Pseudocode

Algorithmus BFS-Wegsuche
Eingabe: Graph G = (V,E), Startknoten s, Endknoten t
Ausgabe: Pfad von s nach t oder Fehlermeldung
für alle v aus V {
  markiere v als ungelesen;
  setze vorgänger von v auf NULL;
}
Erzeuge neue Queue q;
q.put(s);
solange nicht q.isEmpty() {
  temp = q.get();
  markiere temp als gelesen;
  wenn temp gesuchter knoten t {
    ausgabe: Fertig
    backtrack(temp);
    Beende Algorithmus;
  } anderenfalls {
    für alle ausgehenden kanten von temp {
      wenn knoten v am ende der ausgehenden kante nicht markiert {
        setze vorgänger von v auf temp;
        q.put(v);
      }
    }
  }
}
Ausgabe: Pfad nicht gefunden
Beende Algorithmus;

Algorithmus backtrack
Eingabe: Knoten x;
Ausgabe: Pfad zum Ursprung des BFS-Algorithmus

neue leere liste l;
solange nicht x == NULL {
  füge x zu l hinzu;
}
kehre l um;
Ausgabe: l;

Laufzeitanalyse

Zuerst den Algorithmus BFS-Wegsuche. Die erste Schleife (Zeile 1 - 4) läuft genau so oft wie es Knoten im Graphen gibt, also $\Theta (|V|)$. Da jeder Knoten nur einmal zu Queue hinzugefügt wird (deswegen das markieren der Knoten in der schleife und die überprüfung ob der knoten schon markiert ist) läuft die zweite Schleife auch höchstens $\Theta (|V|+|E|)$ mal und zwar dann wenn es entweder keinen Pfad gibt oder der letzte Knoten der zu Queue hinzugefügt wird der gesuchte ist (und der ganze Graph somit durchsucht werden muss). Das + |E| kommt deswegen weil in der Schleife die Überprüft ob die Queue leer ist, noch eine Schleife ist, die jede Kante durchgeht.

Modifikation für ungerichteten Graphen

Eine Modifikation ist nicht nötig.