The first DFS path using a itertaive DFS rather than a recursive one

Question

I am trying to implement a simple Dfs path finding for a problem in which I have to print the very first path I encountered and nothing if no path is found. I was able to do it with Recursion but i am having trouble with the iterative version.

here is my code :

#include <iostream>
#include <stack>
#include <map>
using namespace std;

void PrintDFSpath(int **a, int *visited, int start, int end, int v)
{
    map<int, int> parentMap;
    stack<int> s;
    s.push(start);

    while (!s.empty())
    {
        int currEle = s.top();
        visited[currEle]=1;
        s.pop();
        if (currEle == end)
        {
            break;
        }

        for (int i = v - 1; i >= 0; i--)
        {
            if (a[currEle][i] == 1 && !visited[i] && i != currEle)
            {
                if( !parentMap.count(i) )
                    parentMap[i] = currEle;
                s.push(i);
                visited[i] = 1;
            }
        }
        if (s.empty())
        {
            return;
        }
    }
    int i = end;
    cout<<end<<" ";
    while (i != start)
    {
        cout<<parentMap[i]<<" ";
        i = parentMap[i];
    }
}

int main()
{
    int v, e;
    cin >> v >> e;
    int **a = new int *[v];

    for (int i = 0; i < v; i++)
    {
        a[i] = new int[v];
        for (int j = 0; j < v; j++)
            a[i][j] = 0;
    }
    int x, y;
    for (int i = 0; i < e; i++)
    {
        cin >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1;
    }

    int v1, v2;
    cin >> v1 >> v2;

    int *visited = new int[v];
    for (int j = 0; j < v; j++)
        visited[j] = 0;

    PrintDFSpath(a, visited, v1, v2, v);
    return 0;
}

I am using an adjacency matrix here.

I have already implemented some of the things that I found on StackOverflow such as the map

Also, the get the same path as that in recursive order I am inserting the children into the stack in rev order.

Here is the Problem statement

Given an undirected graph G(V, E) and two vertices v1 and v2(as integers),
find and print the path from v1 to v2 (if exists).
Print nothing if there is no path between v1 and v2.
Find the path using DFS and print the first path that you encountered.

V is the number of vertices present in graph G and vertices are numbered from 0 to V-1.
E is the number of edges present in graph G.

Print the path in reverse order. That is, print v2 first, then intermediate vertices and v1 at last.

Input schema :

Line 1: Two Integers V and E (separated by space)
Next E lines: Two integers a and b, denoting that there exists an edge between vertex a and vertex b (separated by space)
Line (E+2): Two integers v1 and v2 (separated by space)

I am thinking the issue is coming from the following statement.

if (currEle == end)
{
    break;
}

but I can't figure out how to go about correcting it. Plz suggest something

The test case :
7 8
0 1
1 2
4 5
6 5
1 6
1 2
2 3
0 3
0 3

output : 3 2 1 0

Answer 1

Basically, you get a code that solves your testcase example, by removing the following code lines from your inner for loop:

if( !parentMap.count(i) )

and

visited[i] = 1;

In your code, the parentMap registers the first occurrence of a path from the currently processed element to its children. In order to mimic the recursive DFS behavior, parentMap should register the path from the current element to its parent. By overriding an existing map element when you encounter a new path that was not yet visited, you get the desired data.

The visited collection should contain the elements that you already processed. If you add children to visited within the inner for loop, you mark them as processed, when they are only enqueued for processing at some point in the future. Operating on a collection that doesn't fulfil its contract is almost always a bad idea.