现在的位置: 首页 > 面试题 > 正文

寻路算法

2022年01月10日 面试题 ⁄ 共 2064字 ⁄ 字号 暂无评论
博客主机

图的寻路算法也可以通过深度优先遍历 dfs 实现,寻找图 graph 从起始 s 点到其他点的路径,在上一小节的实现类中添加全局变量 from数组记录路径,from[i] 表示查找的路径上i的上一个节点。

 

首先构造函数初始化寻路算法的初始条件,from = new int[G.V()] 和 from = new int[G.V()],并在循环中设置默认值,visited 数组全部为false,from 数组全部为 -1 值,后面对起始节点进行 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);

}

...

那么判断 s 点到 w 点是否有路径,只要查询 visited 对应数组值即可。

 

...

boolean hasPath(int w){

assert w >= 0 && w < G.V();

return visited[w];

}

...

获取 s 点到 w 点的具体路径,我们用 path 方法来实现,先判断是否连通,可调用 hasPath 方法,由构造函数可知只需通过 from 数组往上追溯就能找到所有的路径。

 

...

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;

}

...

Java 实例代码

源码包下载:Download

 

src/runoob/graph/Path.java 文件代码:

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(" -> ");

}

}

}

Wopus问答

Wopus问答

给我留言

留言无头像?


×