Итеративная DFS против рекурсивной DFS и другой порядок элементов

Question

Я написал рекурсивный алгоритм 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);
    }
}

Затем я написал итерационный алгоритм 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);
            }
        }
    }

Моя проблема в том, что вграфик, на котором, например, я ввожу три узла 'a', 'b', 'c' с дугами ('a', 'b') и ('a', 'c') мой вывод:

'a', 'b', 'c' с рекурсивной версией DFS и:

'a', 'c', 'b' с итеративной версией DFS.

Как я могу получить такой же заказ?Я что-то не так делаю?

Спасибо!

Answer 1

Оба действительны алгоритмы DFS. DFS не указывает, какой узел вы видите первым. Это не важно, потому что порядок между ребрами не определен [помните: ребра обычно являются множеством]. Разница заключается в том, как вы обрабатываете дочерние элементы каждого узла.

В итеративном подходе : сначала вы вставляете все элементы в стек, а затем обрабатываете заголовок стека [который является последним вставленным узлом] - таким образом, первый узел, который вы обрабатываете последний ребенок .

В рекурсивном подходе : вы обрабатываете каждый узел, когда видите его. Таким образом, первый обрабатываемый вами узел - это первый дочерний элемент .

Чтобы итеративная DFS давала тот же результат, что и рекурсивный - вам нужно добавить элементы в стек в обратном порядке [для каждого узла сначала вставьте его последний дочерний элемент, а его первый дочерний последний]

Answer 2

Здесь я оставляю свое решение рекурсивно, очень быстро для реализации. Это только вопрос настройки его для любой проблемы, которая требует использования этого алгоритма.

Очень важно пометить текущее состояние как посещенное, определенное как 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;
}

Answer 3

Ниже приведен пример кода (в соответствии с ответом @amit выше) на C # для матрицы смежности.

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