0105深度优先搜索算法非递归2种实现对比-无向图-数据结构和算法(Java)

1 两种非递归实现

在前面我们解决无向图的单点通性和单点路径问题时，都用到了深度优先搜索算法。深度优先搜索算法可以用递归和非递归两种方式。这里讨论非递归实现。

无向图结构使用邻接表实现。

• 第一种非递归方法（推荐），代码如下：

  •       private void dfs() {// 栈记录搜索路径Stack<Iterator<Integer>> path = new Stack<>();// marked[v] = true;if (!marked[s]) {// 起点未标记，标记计数加1// 起点默认没标记，可以不加是否标记判断marked[s] = true;count++;Iterable<Integer> iterable = graph.adj(s);Iterator<Integer> it;if (iterable != null && (it = iterable.iterator()) != null){// 顶点对应的邻接表迭代器存入栈path.push(it);}}while (!path.isEmpty()) {Iterator<Integer> it = path.pop();int x;while (it.hasNext()) {// 邻接表迭代器有元素，获取元素x = it.next();if (!marked[x]) {// 顶点未被标记，标记计数+1marked[x] = true;count++;if (it.hasNext()) {// 邻接表迭代器有元素重新入栈path.push(it);}// 深度优先原则，当前迭代器入栈，新标记顶点的邻接表迭代器入栈，下次循环优先访问Iterable<Integer> iterable = graph.adj(x);if (iterable != null && (it = iterable.iterator()) != null){path.push(it);}break;}}}}
    

  • 算法分析参考0103深度优先搜索和单点连通-无向图-数据结构和算法(Java)

• 第二种非递归实现，实现如下

  •   private void  dfsDel() {// 支持后入先出和任意删除java.util.Stack<Integer> 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.