Breitensuche und kürzester Pfad
Die Breitensuche beginnt bei einem Knoten v, besucht zuerst diesen Knoten und markiert ihn als besucht, besucht dann nacheinander alle unbesuchten Nachbarn {vi,..,vj} von Knoten v und markiert sie als besucht, dann wiederholt sie für jeden Knoten in {vi,...,vj} die Besuchsmethode von Knoten v, bis alle Knoten besucht wurden.
Wir können es in drei Schritte unterteilen:
- (1) Verwenden Sie eine Hilfswarteschlange q. Stellen Sie zuerst den Knoten v in die Warteschlange und markieren Sie ihn als besucht, dann prüfen Sie in einer Schleife, ob die Warteschlange leer ist.
- (2) Wenn die Warteschlange nicht leer ist, entnehmen Sie das erste Element der Warteschlange, reihen Sie alle mit diesem Element verbundenen unbesuchten Knoten ein und markieren Sie diese Knoten als besucht.
- (3) Wenn die Warteschlange leer ist, bedeutet das, dass alle Knoten in Breitensuchreihenfolge durchlaufen wurden.
Wie in der folgenden Abbildung dargestellt, gibt das Blau auf der rechten Seite die Reihenfolge beim Durchlaufen der Knoten beginnend bei 0 an, und der Teil darunter hält die Entfernung von 0 fest. Es ist ersichtlich, dass eine Breitensuche den kürzesten Pfad in einem ungewichteten Graphen finden kann.
Der folgende Code zeigt, wie man einen Durchlauf mit Breitensuche durchführt und den kürzesten Pfad abfragt. Basierend auf dem Code aus dem vorherigen Abschnitt fügen wir eine globale Variable, das ord-Array, hinzu, um die Reihenfolge der Knoten im Pfad aufzuzeichnen. ord[i] repräsentiert die Reihenfolge von Knoten i im Pfad. Gleichzeitig wird der Konstruktor entsprechend angepasst: Beim Durchlaufen benachbarter Knoten wird jedes Mal, wenn ein unbesuchter Knoten besucht wird, die Entfernung als ord[i] = ord[v] + 1 festgehalten. Die Zeitkomplexität der Breitensuche unter Verwendung einer Adjazenzliste beträgt O(V+E), und die Zeitkomplexität unter Verwendung einer Adjazenzmatrix beträgt O(V^2).
// Konstruktor, Pfadfindungsalgorithmus, findet Pfade von Punkt s zu anderen Punkten im Graphen
public ShortestPath(Graph graph, int s){
// Initialisierung des Algorithmus
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// Kürzeste-Wege-Algorithmus für ungerichtete Graphen: beginnend bei s, führe eine Breitensuche des gesamten Graphen durch
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
...
Prüfe die Länge des kürzesten Pfades von Punkt s nach Punkt w; falls w von s aus nicht erreichbar ist, gib -1 zurück.
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
...
Java-Beispielcode
Quellcode-Paket-Download:Herunterladen
Code der Datei src/example/graph/ShortestPath.java:
import example.graph.read.Graph;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Vector;
/**
* Breitensuche und kürzester Pfad
*/
public class ShortestPath {
// Referenz auf den Graphen
private Graph G;
// Startpunkt
private int s;
// Aufzeichnen, ob ein Knoten während DFS besucht wird
private boolean[] visited;
// Den Pfad aufzeichnen; from[i] stellt den vorherigen Knoten von i auf dem Suchpfad dar
private int[] from;
// Die Reihenfolge der Knoten im Pfad aufzeichnen. ord[i] gibt die Reihenfolge von Knoten i im Pfad an.
private int[] ord;
// Konstruktor, Pfadfindungsalgorithmus, findet Pfade von Punkt s zu anderen Punkten im Graphen
public ShortestPath(Graph graph, int s){
// Initialisierung des Algorithmus
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// Kürzeste-Wege-Algorithmus für ungerichtete Graphen: beginnend bei s, führe eine Breitensuche des gesamten Graphen durch
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
// Abfragen, ob es einen Pfad von Knoten s zu Knoten w gibt
public boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
// Den Pfad von Knoten s zu Knoten w abfragen und in vec speichern
public Vector<Integer> path(int w){
assert hasPath(w) ;
Stack<Integer> s = new Stack<Integer>();
// Durch das from-Array den Pfad von s nach w zurückverfolgen und im Stack speichern
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// Elemente nacheinander aus dem Stack entnehmen, um den geordneten Pfad von s nach w zu erhalten
Vector<Integer> res = new Vector<Integer>();
while( !s.empty() )
res.add( s.pop() );
return res;
}
// Den Pfad von Knoten s zu Knoten w ausgeben
public void showPath(int w){
assert hasPath(w) ;
Vector<Integer> vec = path(w);
for( int i = 0 ; i < vec.size() ; i ++ ){
System.out.print(vec.elementAt(i));
if( i == vec.size() - 1 )
System.out.println();
else
System.out.print(" -> ");
}
}
// Die Länge des kürzesten Pfades von Punkt s nach Punkt w prüfen
// Wenn der Pfad von s nach w nicht erreichbar ist, -1 zurückgeben
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
}