The pathfinding algorithm of a graph can also be realized by depth-first traversing the dfs to find the path of the graph graph from the starting s point to other points. In the implementation class of the previous section, add global variables from array to record the path, from [i] Represents the last node of I on the path to be looked up.
First, construct a function to initialize the initial condition of the pathfinding algorithm, from = new int [G.V()] And from = new int [G.V()] And set the default value in the loop, the visited array is all false,from, the array is all-1, and then the starting node is recursively processed by dfs.
...
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public Path(Graph graph, int s){
// 算法初始化
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;
// 寻路算法
dfs(s);
}
...
Then to determine whether there is a path from point s to point w, just query the corresponding array values of visited.
...
boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
...
To get the specific path from s point to w point, we use the path method to realize it. We can first judge whether it is connected or not. We can call the hasPath method. From the constructor, we can know that all the paths can be found only by tracing up through the from array.
...
Vector<Integer> path(int w){
assert hasPath(w) ;
Stack<Integer> s = new Stack<Integer>();
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Integer> res = new Vector<Integer>();
while( !s.empty() )
res.add( s.pop() );
return res;
}
...
5.31.1. Java instance code ¶
源码包下载： Download Src/runoob/graph/Path.java file code: ¶
package runoob.graph;
import runoob.graph.read.Graph;
import java.util.Stack;
import java.util.Vector;
/*\*
\* 寻路
*/
public class Path {
// 图的引用
private Graph G;
// 起始点
private int s;
// 记录dfs的过程中节点是否被访问
private boolean[] visited;
// 记录路径, from[i]表示查找的路径上i的上一个节点
private int[] from;
// 图的深度优先遍历
private void dfs( int v ){
visited[v] = true;
for( int i : G.adj(v) )
if( !visited[i] ){
from[i] = v;
dfs(i);
}
}
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public Path(Graph graph, int s){
// 算法初始化
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;
// 寻路算法
dfs(s);
}
// 查询从s点到w点是否有路径
boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
// 查询从s点到w点的路径, 存放在vec中
Vector<Integer> path(int w){
assert hasPath(w) ;
Stack<Integer> s = new Stack<Integer>();
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Integer> res = new Vector<Integer>();
while( !s.empty() )
res.add( s.pop() );
return res;
}
// 打印出从s点到w点的路径
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(" -> ");
}
}
}