Siriuslight's blog

By Siriuslight, history, 7 years ago, In English

I have seen two implentation of DFS that people generally use.

bool visit[N];
int par[N];
vector<int> g[N];
void dfs1(int v)
{
    visit[v] = true;
    for(auto child : g[v])
    {
         if(!visit[child])
              dfs1(child);
    }

}

void dfs2(int v, int p)
{
    par[v] = p;
    for(auto child : g[v])
    {
          if(child == par[v])
                continue;
          dfs(child,v);
    }

}

What is the difference between these two implementations? Is the second implementation only used when we need parent or some other cases also. I always maintain visit array, but some people don't does it affect. I think it should cause infinite recursion but it doesn't.

Can someone please explain it in details.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

First type can be applied on trees as well as graphs but second can be applied only on trees. Second one works because in tree there is only one path between root to any node.

if(child == par[v]) continue; ensures that we don't go back to the parent because it will cause infinite loop.