0104路径搜索和单点路径-无向图-数据结构和算法(Java)

2 单点路径

单点路径。给定一幅图和一个起点s，回答“从s到给定的目的顶点v是否存在一条路径？如果有，找出这条路径。”等类似问题。

2.1 API

单点路径问题在图的处理邻域中十分重要。根据标准设计模式，给出以下API：

public class	Paths
	Paths(Graph g, int s)	G中找出所有起点为s的路径
boolean	hasPathTo(int v)	是否存在从s到v的路径
Iterable<Integer>	pathTo(int v)	s到v的路径，如果不存在返回null

2.2 算法实现

使用深度优先搜索搜索图中的路径非递归算法实现，源代码2.2-1如下所示：

package com.gaogzhen.datastructure.graph.undirected;import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.In;import java.util.Iterator;
import java.util.Map;/*** 单点连通性* @author: Administrator* @createTime: 2023/03/03 19:58*/
public class DepthFirstPaths {/*** 顶点是否标记*/private boolean[] marked;/*** 从起点到一个顶点的已知路径上的最后一个顶点*/private int[] edgeTo;/*** 图*/private Graph graph;/*** 起点*/private int s;public DepthFirstPaths(Graph graph, int s) {this.graph = graph;this.s = s;int v = graph.V();check(s);marked = new boolean[v];edgeTo = new int[v];dfs();}/*** 搜索图g以v为起点的路径*/private void dfs() {Stack<Entry<Integer, Iterator<Integer>>> path = new Stack<>();// marked[v] = true;if (!marked[s]) {// 键值对起点-起点对应邻接表迭代器压入栈中marked[s] = true;Iterable<Integer> iterable = graph.adj(s);Iterator<Integer> it;if (iterable != null && (it = iterable.iterator()) != null){path.push(new Entry<>(s, it));}}while (!path.isEmpty()) {Entry<Integer, Iterator<Integer>> entry = path.pop();int x;Iterator<Integer> it = entry.getValue();Integer f = entry.getKey();while (it.hasNext()) {// 当前顶点对应的邻接表迭代器还有元素，获取下一个元素x = it.next();if (!marked[x]) {// 顶点未被标记，标记顶点且标记路径x->f// f是x所在邻接表对应的顶点marked[x] = true;edgeTo[x] = f;if (it.hasNext()) {// 邻接表迭代器还有元素，重新压入栈path.push(entry);}// 按照深度优先原则，把新标记顶点对应的键值对压入栈中，在下次循环时优先访问Iterable<Integer> iterable = graph.adj(x);if (iterable != null && (it = iterable.iterator()) != null){path.push(new Entry<>(x, it));}break;}}}}/*** 检测索引是否在范围之内* @param i 给定索引*/private void check(int i) {if (i < 0 || i > graph.V() - 1) {throw new IndexOutOfBoundsException("索引越界异常");}}/*** 判断是否存在起点s到v的路径* @param x 给定顶点* @return*/public boolean hashPathTo(int x) {check(x);return marked[x];}/*** s到v的路径，如果不存在返回null* @param x 指定的顶点* @return  起点到指定顶点的路径*/public Iterable<Integer> pathTo(int x) {// 判断v和起点间是否存在路径if (!hashPathTo(x)) {// 不存在返回nullreturn null;}// 栈记录x到起点的路径Stack<Integer> path = new Stack<>();// edge[]是一棵父链接表示的树，所以从已知路径的最后一个顶点开始沿父链接遍历，直到起点for (int p = x; p != s; p = edgeTo[p]) {path.push(p);}// 加入起点path.push(s);return path;}}

测试：

    public static void testPaths() {String path = "H:\\gaogzhen\\java\\projects\\algorithm\\asserts\\maze.txt";In in = new In(path);Graph graph = new Graph(in);int s = 0;DepthFirstPaths depthFirstPaths = new DepthFirstPaths(graph, s);int v = 4;System.out.println(depthFirstPaths.hashPathTo(v));System.out.println(depthFirstPaths.pathTo(v));}// 测试结果true
[0, 2, 3, 5]

算法分析：

• 该算法基于深度优先搜索实现的，可以参考上一篇 0103深度优先搜索和单点连通-无向图-数据结构和算法(Java)

• 这里添加了一个实例变量edgeTo[]整形数组，用来记录从每个与s连通的顶点回到起点s的路径。

• 在由边v-w第一次访问任意顶点w时，将edgeTo[w]设置为v来记住这条路径。换句话说，v-w是从s到w的路径上的最后一条已知的便。

• 搜索的结果是一棵以起点为根结点的树，edgeTo[]是一棵由父链接表示的树。如下图所示：

• pathTo()通过x自下沿路径向上遍历整棵树，x设为edgeTo[x]，将经过的顶点压入栈中，返回Iterable对象帮助用例遍历s到v的路径。

  • edgeTo[]是一棵由父链接表示的树,x=edgeTo[x]保证向上遍历

命题A：使用深度优先搜索得到从给定起点到任意标记顶点的路径所需时间与路径的长度成正比。

证明：根据已访问过的订单数量的归纳可得，DepthFirstPaths中的edgeTo[]数组表示一棵以起点为根结点的树。pathTo方法构造路径所需时间和路径长度成正比。

后记

如果小伙伴什么问题或者指教，欢迎交流。

❓QQ:806797785

⭐️源代码仓库地址：https://gitee.com/gaogzhen/algorithm

参考链接:

[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法：第4版[M].北京：人民邮电出版社，2012.10.p342-344.