网站建设51jyoo,行业网站建设内容,网页设计代码放图片,流程图制作网站文章目录2 单点路径2.1 API2.2 算法实现后记2 单点路径
单点路径。给定一幅图和一个起点s#xff0c;回答“从s到给定的目的顶点v是否存在一条路径#xff1f;如果有#xff0c;找出这条路径。”等类似问题。
2.1 API
单点路径问题在图的处理邻域中十分重要。根据标准设计…
文章目录2 单点路径2.1 API2.2 算法实现后记2 单点路径
单点路径。给定一幅图和一个起点s回答“从s到给定的目的顶点v是否存在一条路径如果有找出这条路径。”等类似问题。
2.1 API
单点路径问题在图的处理邻域中十分重要。根据标准设计模式给出以下API
public classPathsPaths(Graph g, int s)G中找出所有起点为s的路径booleanhasPathTo(int v)是否存在从s到v的路径IterableIntegerpathTo(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() {StackEntryInteger, IteratorInteger path new Stack();// marked[v] true;if (!marked[s]) {// 键值对起点-起点对应邻接表迭代器压入栈中marked[s] true;IterableInteger iterable graph.adj(s);IteratorInteger it;if (iterable ! null (it iterable.iterator()) ! null){path.push(new Entry(s, it));}}while (!path.isEmpty()) {EntryInteger, IteratorInteger entry path.pop();int x;IteratorInteger 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);}// 按照深度优先原则把新标记顶点对应的键值对压入栈中在下次循环时优先访问IterableInteger 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 IterableInteger pathTo(int x) {// 判断v和起点间是否存在路径if (!hashPathTo(x)) {// 不存在返回nullreturn null;}// 栈记录x到起点的路径StackInteger 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[]是一棵由父链接表示的树,xedgeTo[x]保证向上遍历 命题A使用深度优先搜索得到从给定起点到任意标记顶点的路径所需时间与路径的长度成正比。 证明根据已访问过的订单数量的归纳可得DepthFirstPaths中的edgeTo[]数组表示一棵以起点为根结点的树。pathTo方法构造路径所需时间和路径长度成正比。 后记
如果小伙伴什么问题或者指教欢迎交流。 ❓QQ:806797785 ⭐️源代码仓库地址https://gitee.com/gaogzhen/algorithm 参考链接:
[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法第4版[M].北京人民邮电出版社2012.10.p342-344.
