Iterative DFS vs Recursive DFS and different elements order

Question

I have written a recursive DFS algorithm to traverse a graph:

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

Then I have written an iterative DFS algorithm using a stack:

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

My problem is that in a graph in which, for example, I enter the three nodes 'a', 'b', 'c' with arcs ('a', 'b') and ('a', 'c') my output is:

'a', 'b', 'c' with the recursive DFS version, and:

'a', 'c', 'b' with the iterative DFS one.

How could I get the same order? Am I doing something wrong?

Thank you!

Answer 1

Both are valid DFS algorithms. A DFS does not specify which node you see first. It is not important because the order between edges is not defined [remember: edges are a set usually]. The difference is due to the way you handle each node's children.

In the iterative approach: You first insert all the elements into the stack - and then handle the head of the stack [which is the last node inserted] - thus the first node you handle is the last child.

In the recursive approach: You handle each node when you see it. Thus the first node you handle is the first child.

To make the iterative DFS yield the same result as the recursive one - you need to add elements to the stack in reverse order [for each node, insert its last child first and its first child last]

Answer 2

The most obvious diff is the order you utilize the children.

In the Recursive method: You take the first child and run with it as soon as it comes

while in iterative approach: You push all the children in the stack and then take the top of the stack i.e the last child

To produce the same result just do the insertion of children in reverse order.

The other diff would be memory usage as one would use call stack while the other would use a stack that you make or one the STL elements:

You can read about this here: https://codeforces.com/blog/entry/17307

Answer 3

Here I leave my solution recursively, very fast to implement. It is only a matter of adjusting it for any problem that requires the use of this algorithm.

It is very important to mark the current state as visited, defined as ok[u] = true, even having all the states as they have not been visited using 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 4

Below is the sample code (as per @amit answer above) in C# for 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);
                    }
                }
            }
        }
    }
}