IFS iterativos vs DFS recursivo y orden de elementos diferentes

He escrito un algoritmo DFS recursivo para recorrer un gráfico:

void Graph::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); } } 

Luego escribí un algoritmo DFS iterativo usando una stack:

 template  void Graph::IterativeDFS(Node n) { Stack 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); } } } 

Mi problema es que en un gráfico en el que, por ejemplo, ingreso los tres nodos ‘a’, ‘b’, ‘c’ con arcos (‘a’, ‘b’) y (‘a’, ‘c’) mi salida es:

‘a’, ‘b’, ‘c’ con la versión recursiva DFS, y:

‘a’, ‘c’, ‘b’ con el iterativo DFS uno.

¿Cómo podría obtener el mismo pedido? ¿Estoy haciendo algo mal?

¡Gracias!

Ambos son algoritmos DFS válidos . Un DFS no especifica qué nodo verá primero. No es importante porque el orden entre los bordes no está definido [recuerde: los bordes son un conjunto generalmente]. La diferencia se debe a la forma en que manejas los hijos de cada nodo.

En el enfoque iterativo: Primero inserta todos los elementos en la stack y luego maneja la cabeza de la stack [que es el último nodo insertado], por lo tanto, el primer nodo que maneja es el último hijo .

En el enfoque recursivo : manejas cada nodo cuando lo ves. Por lo tanto, el primer nodo que maneja es el primer hijo .

Para hacer que el DFS iterativo produzca el mismo resultado que el recursivo, debe agregar elementos a la stack en orden inverso [para cada nodo, inserte su último hijo primero y su primer hijo último]

A continuación se muestra el código de muestra (según @amit answer anterior) en C # para Adjacency Matrix.

 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 vertexStack = new Stack(); 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); } } } } } }