CODEWITHSUNDEEP
c++algorithmgraphdepth-first-search
Vadim Chernetsov
Vadim Chernetsov

Reputation: 390

Various variations of the implementation of dfs

Suppose I have the concrete undirected graph: "1----2----3----4".

What is the difference between the next implementations of the algorithm "dfs":

#include <iostream>
#include <vector>
using namespace std;
const int maxSize=4000;
vector<int> graph[maxSize];
bool visited0[maxSize];
void dfs0(int firstPoint, int previousPoint)
{
    visited0[firstPoint]=true;
    for(int secondPoint : graph[firstPoint])
    {
        if(visited0[secondPoint]==false)
        {
            dfs0(secondPoint, firstPoint);
        }
    }
    return;
}
bool visited1[maxSize];
void dfs1(int firstPoint, int previousPoint)
{
    visited1[maxSize]=true;
    for(int secondPoint : graph[firstPoint])
    {
        if(secondPoint==previousPoint)
        {
            continue;
        }
        dfs1(secondPoint, firstPoint);
    }
    return;
}
bool visited2[maxSize];
void dfs2(int firstPoint, int previousPoint)
{
    visited2[firstPoint]=true;
    for(int secondPoint : graph[firstPoint])
    {
        if(secondPoint==previousPoint)
        {
            continue;
        }
        if(visited2[secondPoint]==false)
        {
            dfs2(secondPoint, firstPoint);
        }
    }
    return;
}
int main()
{
    dfs0(1, -1);
    dfs1(1, -1);
    dfs2(1, -1);
    return 0;
}

If it is more precisely I want to know when (in which cases) I should use the commands-branchings:

if(visited0[secondPoint]==false)
{
    dfs0(secondPoint, firstPoint);        (Variation #1)
}

and

if(secondPoint==previousPoint)
{
    continue;
}
dfs1(secondPoint, firstPoint);        (Variation #2)

and

if(secondPoint==previousPoint)
{
    continue;
}
if(visited2[secondPoint]==false)
{
    dfs2(secondPoint, firstPoint);        (Variation #3)
}

Please, describe each variation (Variation #1, Variation #2, Variation #3).

In which cases must I use Variation #1?

In which cases must I use Variation #2?

In which cases must I use Variation #3?

How will the appearence of the next command-branching (it is placed below) influence on the various implementations of the algorithm "dfs" (dfs0(1, -1), dfs1(1, -1), dfs2(1, -1)):

Use the parameter "visited" in dependence of the version of the algorithm "dfs": either "visited0", or "visited1", or "visited2".

How is it important to use this command-branching at the beginning of the various implementations of the algorithm "dfs" (dfs0(1, -1), dfs1(1, -1), dfs2(1, -1))?

if(visited0[firstPoint]==true)
{
    return;
}

Thank You.

Upvotes: 0

Views: 167

Answers (1)

Deepak Tatyaji Ahire
Deepak Tatyaji Ahire

Reputation: 5309

There is no logical difference between Variation 1 and Variation 3, but Variation 3 is optimised version as it will avoid unwanted recursive calls which might be a great deal if large test cases are involved. This might consume more memory unnecessarily.

The Variation 2 differs logically from the other two variations, becuase, it allows a node to be visited multiple times during DFS.

The number of times the node gets visited in the Variation 2 will depend on the adjacency matrix/list of the graph.

Using the command-branching in Variation 1 and Variation 3, will have no effect, as we are already checking if the node has been visited before, but it will surely make the Variation 2 work correctly (as per the definition of DFS: visit every node almost once.)

Upvotes: 1

Related Questions