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

问题描述

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

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与堆栈而不是队列作为数据结构.

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屋！