iterativo DFS vs Recursive DFS y diferentes elementos de pedido

Question

He escrito un algoritmo DFS recursiva para atravesar un gráfico:

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

Entonces he escrito un algoritmo DFS iterativo utilizando una pila:

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

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 DFS recursiva y:

'a', 'c', 'b' con el iterativo DFS uno.

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

¡Gracias!

Answer 1

Ambos son algoritmos válidos DFS. 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 : Se inserta por primera vez todos los elementos en la pila - y luego manejar la cabeza de la pila [que es el último nodo insertado] - así el primer nodo que maneja es el último hijo .

En el aproximación recursiva: Usted maneja cada nodo cuando lo ve. Por lo tanto, el primer nodo que maneja es el primer hijo.

Para hacer el iterativa DFS producir el mismo resultado que el recursiva uno - es necesario añadir elementos a la pila en orden inverso [para cada nodo, introduzca su último hijo primero y su primer hijo el pasado]

Answer 2

A continuación se muestra el código de ejemplo (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<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); 
        } 
       } 
      } 
     } 
    } 
}