Two types of DFS ???

Правка en1, от Siriuslight, 2017-09-29 21:11:53

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Siriuslight 2017-09-29 21:11:53 797 Initial revision (published)