广州网站建设鞍山,简单微信小程序开发首页,中国建设行业峰会官方网站,做网站公司宁波文章目录1.1 走迷宫1.2 图的深度优先搜索实现1.3 算法分析及性能1. 4 单点连通性后记1.1 走迷宫
简单的迷宫#xff0c;如下图1.1-1所示#xff1a; 探索迷宫而不迷路#xff0c;我们需要#xff1a;
选择一条没有标记过的通道#xff0c;在你走过的路上铺一条绳子…
文章目录1.1 走迷宫1.2 图的深度优先搜索实现1.3 算法分析及性能1. 4 单点连通性后记1.1 走迷宫
简单的迷宫如下图1.1-1所示 探索迷宫而不迷路我们需要
选择一条没有标记过的通道在你走过的路上铺一条绳子标记所有你第一次路过的路口和通道当来到一个标记过的路口时用绳子回退到上一个路口当回退的路口已没有可走的通道时继续回退。
绳子可以保证总能找到一条出路标记能保证你不会两次经过同一条通道或者路口。我们把上迷宫用等价的图来代替如下图1.1-2所示
1.2 图的深度优先搜索实现
图的遍历算法非递归代码如下
import java.util.Map;/*** key-value pair 类* author: Administrator* createTime: 2023/03/04 21:49*/
public final class EntryK, V implements Map.EntryK, V{private K key;private V value;public Entry(K key, V value) {this.key key;this.value value;}Overridepublic K getKey() {return key;}Overridepublic V getValue() {return value;}Overridepublic V setValue(V value) {V oldValue value;this.value value;return oldValue;}
}/***/import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Graph;import java.util.Iterator;/*** 单点连通性* author: Administrator* createTime: 2023/03/03 19:58*/
public class DepthFirstSearch {/*** 顶点是否标记*/private boolean[] marked;/*** 与指定顶点连通的顶点总数*/private int count;/*** 图*/private Graph graph;/*** 起点*/private int s;public DepthFirstSearch(Graph graph, int s) {this.graph graph;this.s s;check(s);marked new boolean[graph.V()];dfs();}/*** 搜索图g中与起点v连通的所有顶点*/private void dfs() {StackEntryInteger, IteratorInteger path new Stack();// marked[v] true;if (!marked[s]) {marked[s] true;count;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]) {marked[x] true;count;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(索引越界异常);}}/*** 判断起点是否与给定顶点x连通* param x 给定顶点* return*/public boolean marked(int x) {check(x);return marked[x];}/*** 返回图中与顶点想连通的顶点数* return*/public int count() {return count;}}
测试代码
public static void testDepth() {String path H:\\gaogzhen\\java\\projects\\algorithm\\asserts\\maze.txt;In in new In(path);Graph graph new Graph(in);int s 0;DepthFirstSearch depthFirstSearch new DepthFirstSearch(graph, s);int t 5;System.out.println(depthFirstSearch.marked(t));System.out.println(depthFirstSearch.count());
}
// 测试结果
true
61.3 算法分析及性能
知识点
Entry类就是一个键值对类存在一对键值在DepthFirstSearch中key用于存储顶点序号value存储该顶点对应邻接顶点迭代器。深度优先搜索非递归实现主要借助栈来代替递归调用栈帧结构已节省内存占用和提高运行效率。
算法分析dfs()方法为该算法实现的主要方法方法源代码以给出这里不再赘述整体流程着重分析下以下一个关键问题。
该非递归dfs方法如何保证深度优先 首先我把键值对Entry起点和起点对应的邻接连通顶点集合迭代器压入栈中外层循环开始 弹出栈顶元素获取Entry的顶点及对应的邻接顶点集合迭代器内层循环判断该迭代器有下一个元素即还有邻接顶点取出一个邻接顶点。 判断改邻接顶点没有被标记过 标记数组对应顶点索引标记连通顶点计数1判断迭代器还有元素重新压入栈中break跳出内层循环 总结只要邻接顶点更深一层的顶点没被标记过标记之后同层迭代器压入栈中去访问更深一层的顶点而不是继续访问同层的顶点。 该dfs方法如果保证同层同一个顶点的邻接顶点访问全部访问完毕且只访问一次 每个顶点只访问一次是标记数组marked[]索引和顶点一一对应默认都是false未标记标记之后不会在压入栈中自然不会在标记一次访问同层元素是通过迭代器完成的while配合迭代hasNext,next()方法保证全部访问一边且不会重复访问。 深度优先算法性能如何见下面的命题及证明。 这里根据上面的算法简单分析完成循环判断栈不为空那么只有未被标记的顶点及其邻接表迭代器会放入栈中也就是说所有的顶点及其邻接表都会被放入栈中且不会重复内层判断迭代器有元素那么所有的邻接表会被遍历一边邻接表代表对应顶点的度数结论深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比 命题A。深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。 证明首先我们要证明这个算法能标记所有与起点s连通的所有顶点且不会标记其他顶点。算法仅通过边来寻找顶点所以每个被标记的顶点都与s连通反证法证明标记了所有与s连通的顶点假设某个没有被标记的顶点w与s连通。因为s作为起点是被标记的由s到w的任意一条路径中至少有一条边连接的两个顶点分别被标记过河没有被标记过例如v-x。根据算法在标记了v后比如发现x因此这样的边不存在。 每个顶点都只会被标记一次保证了时间上限检查标记的耗时和度数成正比。 详细搜索轨迹可参考算法第四版341页。
1. 4 单点连通性
连通性。给定一幅图回答“两个给定的顶点是否连通”或者图中有多少个连通子图等类似问题。
问题“两个给定的顶点是否连通”等价于“两个给定的顶点间是否存在一条路径”也可以叫做路经检测问题。深度优先搜索解决了这个问题。
递归方法参考《算法第四版或者书提供的jar包。
后记
如果小伙伴什么问题或者指教欢迎交流。 ❓QQ:806797785 ⭐️源代码仓库地址https://gitee.com/gaogzhen/algorithm 参考链接:
[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法第4版[M].北京人民邮电出版社2012.10.P338-P342.
