如何使用非递归方法实现图的深度优先搜索 [英] How to implement depth first search for graph with a non-recursive approach

问题描述

我在这个问题上花了很多时间.但是，我只能找到树的非递归方法的解决方案:Non recursive for tree，或图的递归方法，递归图.

I have spent lots of time on this issue. However, I can only find solutions with non-recursive methods for a tree: Non recursive for tree, or a recursive method for the graph, Recursive for graph.

而且很多教程(我不在这里提供这些链接)也没有提供方法.或者教程完全不正确.请帮帮我.

And lots of tutorials (I don't provide those links here) don't provide the approaches as well. Or the tutorial is totally incorrect. Please help me.

更新:

真的很难描述:

如果我有一个无向图:

   1
 / |  
4  |   2
    3 /

1-- 2-- 3 --1 是一个循环.

在步骤:'将弹出顶点的邻居推入堆栈'，顶点应该被推入的顺序是什么?

At the step: 'push the neighbors of the popped vertex into the stack', what's the order in which the vertices should be pushed?

如果压入的顺序是2、4、3，则栈中的顶点为:

If the pushed order is 2, 4, 3, the vertices in the stack are:

| |
|3|
|4|
|2|    
 _

弹出节点后，我们得到结果:1 ->3 ->4 ->2 而不是 1-->3 -->2 --> 4.

After popping the nodes, we get the result: 1 -> 3 -> 4 -> 2 instead of 1--> 3 --> 2 -->4.

这是错误的.我应该添加什么条件来阻止这种情况?

It's incorrect. What condition should I add to stop this scenario?

推荐答案

一个没有递归的 DFS 基本上和 BFS - 但使用 stack 而不是队列作为数据结构.

A DFS without recursion is basically the same as BFS - but use a stack instead of a queue as the data structure.

线程迭代 DFS 与递归 DFS 以及不同的元素顺序处理这两种方法以及它们之间的区别(还有是！你不会以相同的顺序遍历节点！)

The thread Iterative DFS vs Recursive DFS and different elements order handles with both approaches and the difference between them (and there is! you will not traverse the nodes in the same order!)

迭代方法的算法基本上是:

The algorithm for the iterative approach is basically:

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

这篇关于如何使用非递归方法实现图的深度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！