如何实现深度优先搜索图与非递归aprroach [英] How to implement depth first search for graph with non-recursive aprroach

问题描述

唉，我花了很多时间针对此问题。但是，我只能找到非递归的方法，树的解决方案：非递归的树<对于图形，递归的图，或递归方法>。

Well, I have spent lots of time for this issue. However, I only can find solutions with non-recursive methods for tree: Non recursive for tree, or recursive method for 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 是一个循环。

在步：推弹出顶点的邻居入堆栈

什么是顶点的顺序应该推？

如果所按下的顺序是2 4 3，在堆栈中的顶点是：

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

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

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

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

IT'S不正确。什么情况下我是否应添加要停止这种情况？

IT'S INCORRECT. WHAT CONDITION SHOULD I ADD TO STOP THIS SCENARIO?

推荐答案

一个DFS没有递归是基本相同的 BFS - 但使用栈，而不是一个队列作为数据结构

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

线程迭代的DFS VS递推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)

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