迭代DFS与recursionDFS和不同的元素顺序

我写了一个recursion的DFSalgorithm来遍历图：

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); } } 

然后我用堆栈写了一个迭代的DFSalgorithm：

 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); } } } 

我的问题是，在一个图中，例如，我用弧（'a'，'b'）和（'a'，'c'）input三个节点'a'，'b'，'c'我的输出是：

'a'，'b'，'c'和recursion的DFS版本，以及：

'a'，'c'，'b'和迭代的DFS。

我怎么能得到相同的订单？ 我做错了什么？

谢谢！

Answer 1

两者都是有效的 DFSalgorithm。 DFS没有指定首先看到哪个节点。 这并不重要，因为边缘之间的顺序没有定义[记住：边缘通常是一个集合]。 不同之处在于你处理每个节点的孩子的方式。

在迭代方法中：首先将所有元素插入到堆栈中 – 然后处理堆栈的头部（这是插入的最后一个节点） – 因此， 您处理的第一个节点是最后一个子节点 。

在recursion方法中 ：当你看到它时处理每个节点。 因此， 您处理的第一个节点是第一个孩子 。

为了使迭代DFS产生与recursion相同的结果 – 您需要以相反的顺序将元素添加到堆栈 [对于每个节点，先插入其最后一个子元素 ，并将其第一个子元素插入到最后一个子元素中 ]

Answer 2

下面是C＃中Adjacency Matrix的示例代码（根据上面的@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); } } } } } }