DFS template

1

Can you share your default DFS function that you use?
i.e. DFS ( vertex , parent, depth) or DFS(vertex , parent ) only etc.

1 Like
2

Simple DFS with vis for tracking visited : Call in main as dfs(1)

 void dfs(int u)
{
    vis[u]=true;
    for(auto v:V[u])
    {
        //Do Something;
        if(!vis[v]) dfs(v);
        //Do Something Else; 
    }
}

DFS with parent : Call in main as dfs(1,-1):

 void dfs(int u, int p)
{
    for(auto v:V[u])
    {
        //Do Something;
         if(v!=p) dfs(v,u);
        //Do Something Else; 
    }
}

DFS for height : Call in main as dfs(1,0)

 void dfs(int u, int h)
{
    vis[u]=true;
    dis[u]=h;
    for(auto v:V[u])
    {
        //Do Something;
        if(!vis[v]) dfs(v,h+1);
        //Do Something Else;             

    }
}

As you can probably see, All are quite Identical. I mostly prefer dfs with visited array, though I know many who use the Parent one.

1 Like
3 
void dfs(int s = 1, int p = -1){
    for(int &i: g[s]){
       if(i == p)continue;
       lev[i] = lev[s]+1;
       parent[i] = s;
       dfs(s,i);
    } 
}

Same for graph but using visited array

4

only for undirected graph , not for directed one

5

Yeah. He asked template, I won’t writing all different types of dfs snippets here. :laughing:

1 Like
6 
void dfs(int s)
{
	vis[s] = 1;
	
	for(int i = 0 ; i < adj[s].size() ; i++)
	{
		if(!vis[adj[s][i]])
		{
			dfs(adj[s][i]);
		}
	}
}
7

Are you suggesting that Using visited array might not work for Directed Graphs!?

8

it is only for ay2306 ,not for your , your code woks fine