C++ 迭代 DFS 与递归 DFS 以及不同的元素顺序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9201166/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Iterative DFS vs Recursive DFS and different elements order
提问by JohnQ
I have written a recursive DFS algorithm to traverse a graph:
我写了一个递归 DFS 算法来遍历一个图：
void Graph<E, N>::DFS(Node n)
{
std::cout << ReadNode(n) << " ";
MarkVisited(n);
NodeList adjnodes = Adjacent(n);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
Node adj = adjnodes.ReadList(pos);
if(!IsMarked(adj))
DFS(adj);
pos = adjnodes.NextPosition(pos);
}
}
Then I have written an iterative DFS algorithm using a stack:
然后我写了一个使用堆栈的迭代 DFS 算法：
template <typename E, typename N>
void Graph<E, N>::IterativeDFS(Node n)
{
Stack<Node> stack;
stack.Push(n);
while(!stack.IsEmpty())
{
Node u = stack.Read();
stack.Pop();
if(!IsMarked(u))
{
std::cout << ReadNode(u) << " ";
MarkVisited(u);
NodeList adjnodes = Adjacent(u);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
stack.Push(adjnodes.ReadList(pos));
pos = adjnodes.NextPosition(pos);
}
}
}
My problem is that in a graph in which, for example, I enter the three nodes 'a', 'b', 'c' with arcs ('a', 'b') and ('a', 'c') my output is:
我的问题是，在一个图中，例如，我输入三个节点 'a', 'b', 'c' 与弧 ('a', 'b') 和 ('a', 'c')我的输出是：
'a', 'b', 'c' with the recursive DFS version, and:
'a'、'b'、'c' 与递归 DFS 版本，以及：
'a', 'c', 'b' with the iterative DFS one.
'a', 'c', 'b' 与迭代 DFS 之一。
How could I get the same order? Am I doing something wrong?
我怎么能得到同样的订单？难道我做错了什么？
Thank you!
谢谢！
回答by amit
Both are validDFS algorithms. A DFS does not specify which node you see first. It is not important because the order between edges is not defined [remember: edges are a set usually]. The difference is due to the way you handle each node's children.
两者都是有效的DFS 算法。DFS 不会指定您首先看到哪个节点。这并不重要，因为边之间的顺序没有定义[记住：边通常是一个集合]。不同之处在于您处理每个节点的子节点的方式。
In the iterative approach: You first insert all the elementsinto the stack - and then handle the head of the stack [which is the last node inserted] - thus the first node you handle is the last child.
在迭代方法中：首先将所有元素插入堆栈 - 然后处理堆栈的头部 [这是插入的最后一个节点] - 因此您处理的第一个节点是最后一个子节点。
In the recursive approach: You handle each node when you see it. Thus the first node you handle is the first child.
在递归方法中：当您看到每个节点时，您就对其进行处理。因此，您处理的第一个节点是第一个 child。
To make the iterative DFS yield the same result as the recursive one - you need to add elements to the stack in reverse order[for each node, insert its last child first and its first child last]
为了使迭代 DFS 产生与递归相同的结果 - 您需要以相反的顺序将元素添加到堆栈中[对于每个节点，首先插入其最后一个子项，最后插入其第一个子项]
回答by Chris Michael
Here I leave my solution recursively, very fast to implement. It is only a matter of adjusting it for any problem that requires the use of this algorithm.
在这里，我递归地留下我的解决方案，实施起来非常快。对于需要使用此算法的任何问题，只需对其进行调整即可。
It is very important to mark the current state as visited, defined as ok[u] = true, even having all the states as they have not been visited using memset(ok, 0, sizeof ok)
将当前状态标记为已访问非常重要，定义为ok[u] = true，甚至使用所有未访问状态memset(ok, 0, sizeof ok)
#define forn(i , a , b) for(int i=(a);i<(b);i++)
vector<int> arr[10001];
bool ok[10001];
void addE(int u , int v){
arr[u].push_back(v);
arr[v].push_back(u);
}
void dfs(int u){
ok[u] = true;
forn(v , 0 , (int)arr[u].size()) if(!ok[arr[u][v]]) dfs(arr[u][v]);
}
int main(){
//...
memset(ok , 0 , sizeof ok);
//...
return 0;
}
回答by Sai
Below is the sample code (as per @amit answer above) in C# for Adjacency Matrix.
下面是 C# 中邻接矩阵的示例代码（根据上面的@amit 回答）。
using System;
using System.Collections.Generic;
namespace GraphAdjMatrixDemo
{
public class Program
{
public static void Main(string[] args)
{
// 0 1 2 3 4 5 6
int[,] matrix = { {0, 1, 1, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 1, 0},
{1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0 ,0},
{0, 0, 1, 1, 1, 0, 0} };
bool[] visitMatrix = new bool[matrix.GetLength(0)];
Program ghDemo = new Program();
for (int lpRCnt = 0; lpRCnt < matrix.GetLength(0); lpRCnt++)
{
for (int lpCCnt = 0; lpCCnt < matrix.GetLength(1); lpCCnt++)
{
Console.Write(string.Format(" {0} ", matrix[lpRCnt, lpCCnt]));
}
Console.WriteLine();
}
Console.Write("\nDFS Recursive : ");
ghDemo.DftRecursive(matrix, visitMatrix, 0);
Console.Write("\nDFS Iterative : ");
ghDemo.DftIterative(matrix, 0);
Console.Read();
}
//====================================================================================================================================
public void DftRecursive(int[,] srcMatrix, bool[] visitMatrix, int vertex)
{
visitMatrix[vertex] = true;
Console.Write(vertex + " ");
for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++)
{
if (visitMatrix[neighbour] == false && srcMatrix[vertex, neighbour] == 1)
{
DftRecursive(srcMatrix, visitMatrix, neighbour);
}
}
}
public void DftIterative(int[,] srcMatrix, int srcVertex)
{
bool[] visited = new bool[srcMatrix.GetLength(0)];
Stack<int> vertexStack = new Stack<int>();
vertexStack.Push(srcVertex);
while (vertexStack.Count > 0)
{
int vertex = vertexStack.Pop();
if (visited[vertex])
continue;
Console.Write(vertex + " ");
visited[vertex] = true;
for (int neighbour = srcMatrix.GetLength(0) - 1; neighbour >= 0; neighbour--)
//for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++)
{
if (srcMatrix[vertex, neighbour] == 1 && visited[neighbour] == false)
{
vertexStack.Push(neighbour);
}
}
}
}
}
}
