Java数据结构之图的路径查找算法详解

前言

在实际生活中，地图是我们经常使用的一种工具，通常我们会用它进行导航，输入一个出发城市，输入一个目的地

城市，就可以把路线规划好，而在规划好的这个路线上，会路过很多中间的城市。这类问题翻译成专业问题就是：

从s顶点到v顶点是否存在一条路径？如果存在，请找出这条路径。

例如在上图上查找顶点0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4。

如果对图的前置知识不了解，请查看系列文章：

【数据结构与算法】图的基础概念和数据模型

【数据结构与算法】图的两种搜索算法

算法详解

我们实现路径查找，最基本的操作还是得遍历并搜索图，所以，我们的实现暂且基于深度优先搜索来完成。其搜索

的过程是比较简单的。我们添加了edgeTo[]整型数组，这个整型数组会记录从每个顶点回到起点s的路径。

如果我们把顶点设定为0，那么它的搜索可以表示为下图：

总结来说，就是edgeTo数组的下标表示当前顶点，内容存放上一个节点的数据，根据最终edgeTo的结果，我们很容易能够找到从起点0到任意顶点的路径。

实现

API设计

代码实现

/**
* 路径查找
*
* @author alvin
* @date 2022/10/31
* @since 1.0
**/
public class DepthFirstPaths {
   //索引代表顶点，值表示当前顶点是否已经被搜索
   private boolean[] marked;
   //起点
   private int s;
   //索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
   private int[] edgeTo;

//构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径
   public DepthFirstPaths(Graph G, int s){
       //初始化marked数组
       this.marked = new boolean[G.V()];
       //初始化起点
       this.s = s;
       //初始化edgeTo数组
       this.edgeTo = new int[G.V()];

dfs(G,s);
   }

//使用深度优先搜索找出G图中v顶点的所有相邻顶点
   private void dfs(Graph G, int v){
       //把v表示为已搜索
       marked[v] = true;

//遍历顶点v的邻接表，拿到每一个相邻的顶点，继续递归搜索
       for (Integer w : G.adj(v)) {
           //如果顶点w没有被搜索，则继续递归搜索

if (!marked[w]){
               edgeTo[w] = v;//到达顶点w的路径上的最后一个顶点是v
               dfs(G,w);
           }

}
   }

//判断w顶点与s顶点是否存在路径
   public boolean hasPathTo(int v){
       return marked[v];
   }

//找出从起点s到顶点v的路径(就是该路径经过的顶点)
   public Stack<Integer> pathTo(int v){
       if (!hasPathTo(v)){
           return null;
       }

//创建栈对象，保存路径中的所有顶点
       Stack<Integer> path = new Stack<>();

//通过循环，从顶点v开始，一直往前找，到找到起点为止
       for (int x = v; x!=s;x = edgeTo[x]){
           path.push(x);
       }

//把起点s放到栈中
       path.push(s);

return path;
   }
}

测试：

public class DepthFirstPathsTest {

@Test
   public void test() {
       //城市数量
       int totalNumber =  20;
       Graph G = new Graph(totalNumber);
       //添加城市的交通路线
       G.addEdge(0,1);
       G.addEdge(6,9);
       G.addEdge(1,8);
       G.addEdge(1,12);
       G.addEdge(8,12);
       G.addEdge(6,10);
       G.addEdge(4,8);

DepthFirstPaths depthFirstPaths = new DepthFirstPaths(G, 0);
       Stack<Integer> path = depthFirstPaths.pathTo(12);
       StringBuilder sb = new StringBuilder();
       //遍历栈对象
       for (Integer v : path) {
           sb.append(v+"->");
       }

sb.deleteCharAt(sb.length()-1);
       sb.deleteCharAt(sb.length()-1);
       System.out.println(sb);
   }
}

来源：https://juejin.cn/post/7160669091970154510