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.
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.