DFS itératifs vs DFS récursifs et ordre des différents éléments

j'ai écrit un algorithme récursif DFS pour traverser un graphe: 

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

alors j'ai écrit un algorithme DFS itératif en utilisant une pile: 

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

Mon problème est que, dans un graphe dans lequel, par exemple, j'entre dans les trois nœuds 'a', 'b', 'c' avec des arcs ('a', 'b') et ('a', 'c') mon résultat est:

'a', 'b', 'c' avec le récursive DFS version, et:

'a', 'c', 'b' avec la DFS 1 itératif.

Comment obtenir la même commande? Suis-je en train de faire quelque chose de mal?

Merci!

34
demandé sur dsolimano 2012-02-09 00:48:34

2 réponses

les deux sont des algorithmes DFS valides . A DFS ne spécifie pas quel noeud vous voyez en premier. Il n'est pas important parce que l'ordre entre les bords n'est pas défini [rappelez-vous: les bords sont un ensemble d'habitude]. La différence est due à la façon dont vous traitez chaque nœud enfants.

dans l'approche itérative : vous insérez d'abord tous les éléments dans la pile - et puis gérer la tête de la pile [qui est le dernier noeud inséré] - ainsi le premier noeud que vous manipulez est le dernier enfant .

Dans le récursive "approche de 151920920" : Vous manipulez chaque nœud quand vous le voyez. Ainsi le premier noeud que vous manipulez est le premier enfant .

pour que le DFS itératif donne le même résultat que le DFS récursif - vous devez ajouter des éléments à la pile dans l'ordre inverse [pour chaque noeud, insérez son dernier enfant en premier et son premier enfant dernier]

59
répondu amit 2017-08-23 12:44:07

ci-dessous est le code de l'échantillon (selon la réponse de @amit ci-dessus) dans C# pour la matrice de contiguïté. 

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);
                    }
                }
            }
        }
    }
}
1
répondu Sai 2017-03-19 17:25:30