Pfadfindungsalgorithmus
Der Graph-Pfadfindungsalgorithmus kann auch mit Tiefensuche (DFS) implementiert werden, wobei Pfade von einem Startpunkt s zu anderen Punkten im Graphen gefunden werden. Fügen Sie in der Implementierungsklasse aus dem vorherigen Unterabschnitt ein globales Array `from` hinzu, um Pfade aufzuzeichnen; `from[i]` stellt den vorherigen Knoten von `i` auf dem gefundenen Pfad dar.
Zuerst initialisiert der Konstruktor die Anfangsbedingungen des Pfadfindungsalgorithmus,from = new int[G.V()]undfrom = new int[G.V()]und legt in einer Schleife Standardwerte fest: Alle Werte im `visited`-Array sind `false`, und alle Werte im `from`-Array sind `-1`. Dann wird eine rekursive DFS-Verarbeitung auf dem Startknoten durchgeführt.
// Konstruktor, Pfadfindungsalgorithmus, findet Pfade von Punkt s zu anderen Punkten im Graphen
public Path(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()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
}
this.s = s;
// Pfadfindungsalgorithmus
dfs(s);
}
...
Um festzustellen, ob es einen Pfad von Punkt s zu Punkt w gibt, prüfen Sie einfach den entsprechenden Wert im `visited`-Array.
boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
...
Um den spezifischen Pfad von s nach w zu erhalten, implementieren wir ihn mit der `path`-Methode. Zuerst wird durch Aufruf der `hasPath`-Methode festgestellt, ob sie verbunden sind. Wie aus dem Konstruktor ersichtlich ist, lassen sich alle Pfade einfach finden, indem man im `from`-Array nach oben zurückverfolgt.
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;
}
...
Java-Beispielcode
Quellcode-Paket-Download:Herunterladen
Code in src/example/graph/Path.java:
import example.graph.read.Graph;
import java.util.Stack;
import java.util.Vector;
/**
* Pfadfindung
*/
public class Path {
// 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;
// Tiefensuche im Graphen
private void dfs( int v ){
visited[v] = true;
for( int i : G.adj(v) )
if( !visited[i] ){
from[i] = v;
dfs(i);
}
}
// Konstruktor, Pfadfindungsalgorithmus, findet Pfade von Punkt s zu anderen Punkten im Graphen
public Path(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()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
}
this.s = s;
// Pfadfindungsalgorithmus
dfs(s);
}
// Abfragen, ob es einen Pfad von Knoten s zu Knoten w gibt
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
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
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(" -> ");
}
}
}