建设银行客户投诉网站,网站自身维护,山西设计网站公司,重庆网站优化公司1 两种非递归实现
在前面我们解决无向图的单点通性和单点路径问题时#xff0c;都用到了深度优先搜索算法。深度优先搜索算法可以用递归和非递归两种方式。这里讨论非递归实现。
无向图结构使用邻接表实现。 第一种非递归方法#xff08;推荐#xff09;#xff0c;代码如…1 两种非递归实现
在前面我们解决无向图的单点通性和单点路径问题时都用到了深度优先搜索算法。深度优先搜索算法可以用递归和非递归两种方式。这里讨论非递归实现。
无向图结构使用邻接表实现。 第一种非递归方法推荐代码如下 private void dfs() {// 栈记录搜索路径StackIteratorInteger path new Stack();// marked[v] true;if (!marked[s]) {// 起点未标记标记计数加1// 起点默认没标记可以不加是否标记判断marked[s] true;count;IterableInteger iterable graph.adj(s);IteratorInteger it;if (iterable ! null (it iterable.iterator()) ! null){// 顶点对应的邻接表迭代器存入栈path.push(it);}}while (!path.isEmpty()) {IteratorInteger it path.pop();int x;while (it.hasNext()) {// 邻接表迭代器有元素获取元素x it.next();if (!marked[x]) {// 顶点未被标记标记计数1marked[x] true;count;if (it.hasNext()) {// 邻接表迭代器有元素重新入栈path.push(it);}// 深度优先原则当前迭代器入栈新标记顶点的邻接表迭代器入栈下次循环优先访问IterableInteger iterable graph.adj(x);if (iterable ! null (it iterable.iterator()) ! null){path.push(it);}break;}}}}算法分析参考0103深度优先搜索和单点连通-无向图-数据结构和算法(Java) 第二种非递归实现实现如下 private void dfsDel() {// 支持后入先出和任意删除java.util.StackInteger stack new java.util.Stack();stack.push(s);while (!stack.isEmpty()) {int v stack.peek();if (!marked[v]) {marked[v] true;count;for (int w : graph.adj(v)) {// 访问同层顶点if (!marked[w]) {// 没被标记过顶点入栈if (stack.contains(w)) {// 没被标记但是已经入栈说明之前是同层压入需要移除重新压入// 这样符合深度优先原则stack.removeElement(w);}stack.push(w);}}}else {// 顶点v的邻接顶点都已访问完毕弹出顶点v回溯stack.pop();}}}栈除了满足后入先出规则外还必须支持删除任意元素的操作
2 对比分析
栈结构 第一种用到的栈为标准栈实现后入先出结构简单可以到仓库里面搜索栈源码。第二种栈除了满足后入先出规则外还必须支持删除任意元素的操作 深度优先的实现 第一种栈存储邻接表迭代器 用于访问邻接表顶点同层算法会优先访问下一层的顶点而不是同层的后继顶点。第二种存储顶点。优先存储邻接表中所有顶点同层在访问下一层顶点时如果顶点未被标记但是在栈中存在通过先删除在重入入栈保证深度优先。 性能分析 相同点搜索标记与起点连通的所有顶点所需时间和顶点的度数之和成正比无向图顶点多边多某个起点对应的深度很深的情况下第二种结构在没有回溯之前栈中会存储大量的顶点元素那么判断顶点是否在栈中以及删除顶点最坏情况下需要时间复杂度为O(度数之和)第一种栈中存储邻接表迭代器每个顶点对应一个最坏情况下时间复杂度为O顶点数 两种算法在单点连通250个顶点 1273条边情况下时间消耗 第一种2-3ms第二种7-8ms
当然第二种栈我们直接用的java.util.Stack,如果自定义实现后入先出规则任意删除性能会更好些。
后记
如果小伙伴什么问题或者指教欢迎交流。 ❓QQ:806797785 ⭐️源代码仓库地址https://gitee.com/gaogzhen/algorithm 参考链接:
[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法第4版[M].北京人民邮电出版社2012.10.p342-344.
