How can we find maximum depth of given graph from each node?

How can we find maximum depth of given graph from each node ?
Example : - If we have vertices = 4 ( i.e 0 ,1,2,3) and the given edges = [ [ 0 , 1 ] , [ 1 , 2 ] , [ 2 , 3 ] ]
Now output should be the maximum depth from each node .
For above case ,
Output :
node height
0 => 3
1 => 2
2 => 2
3 => 3
How can we do this problem ? Please help me .

First thing is there a vertex numbered 4 or not?you have initially numbered the vertices as 0,1,2,3 and then included an edge from 3 to 4…
Secondly,I think we need a simple recursive depth first search.Use an adjacency list and store the edges corresponding to vertices.However store each edge exactly one time.Run depth first search for each of the vertices.
Please consider the depth first search article based on recursion in geeks for geeks.You will get the idea.

You have to do BFS for max-depth, not DFS (see here)

1 Like

I saw the post…it is talking of finding shortest path and the fallacy of dfs in that case…we are speaking of maximum height here which does not needs weight.I do not see why dfs cannot find max depth from each node,Can you provide a counterexample kindly??

0k , I have corrected it , it has vertex from 0 to 3 only .

DFS visits nodes arbitrarily, so it’s possible you may visit the green node before the red nodes and reach the other black node with sub-maximal distance. You may think you can just re-visit the black node by going through the red path later, but this can cause an exponential runtime with certain graphs.

See I have written the code for it but it is not giving correct output :-

 int calHeight(int n , int start , vector<vector<int>>& edges){
        queue<int> q;
        q.push(start);
        int ht=0;
        bool* visited = new bool[n];
        for(int i=0;i<n;i++){
            visited[i]= false;
        }
        while(!q.empty()){
            int val = q.front();
            q.pop();
            visited[val] = true;
            bool flag = false;
          for(int i=0;i<edges.size();i++){
               if(edges[i][0]==val && visited[edges[i][1]] == false){
                   q.push(edges[i][1]);
                   visited[edges[i][1]] = true;
                   flag=true;
               }
           }
            if(flag){
                ht++;
            }
           
        }
        return ht;
    }

I am calling calHeight( ) for every vertex to get the max height . But it is not giving correct output . Please help .

Wait, actually, what is the definition of “maximum depth”? Is it the maximum-length shortest path or just the maximum-length path in general? Because the second type of problem is equivalent to the longest path problem, which is NP-complete. The first is solvable with BFS.

With maximum depth here i simply mean that : - the longest distance between two vertices from a given vertex . I have already shared the example above .

This is the problem link : https://leetcode.com/problems/minimum-height-trees/

We can do this by finding the maximum depth from each node .
And then return the list of nodes with the minimum values .

Wait, it’s a tree? Okay, then, everything makes sense now. In that case, DFS will work (BFS also still works), but you have to additionally store the distance to each node, rather than having a global flag. For example, in your code, you should have a queue<pair<int, int> > where the first int is the node and the second is the distance from the current root.

I am not getting this . How should i maintain the distance ?

Let d_i represent the distance from the root to node i. If you’re at a node x with an edge to an unvisited node y, then d_y = d_x + 1. Initially, d_{root} = 0, so you can “push” d_x + 1 to d_y starting from the root as x.

Sorry, it’s late here. I can give you a more coherent explanation after sleeping lol.

Can you kindly google and read the depth first search from geeks for geeks website?I also read from there and the implementation is lovely…Read it and then we can again discuss…

//The code is as follows…
#include<bits/stdc++.h>
using namespace std;
int dfs(vector<vector> &adj,vector &visited,int vertex,int count)
{
int temp=0,tempe;
visited[vertex]=true;
for(int i=0;i<adj.size();i++)
{
if(adj[vertex][i]==1 && visited[i]==false)
{
tempe=dfs(adj,visited,i,temp)+1;
count=max(count,tempe);
}
}
visited[vertex]=0;
return count;
}
int main()
{
int n,first,second;
cin>>n;
vector<vector> adj(n,vector(n,0));
int edges;
vector finalRes(n);
cin>>edges;
for(int i=0;i<edges;i++)
{
cin>>first>>second;
adj[first][second]=1;
adj[second][first]=1;
}
vector visited(n,0);
for(int i=0;i<n;i++)
{
cout<<i<<" "<<dfs(adj,visited,i,0)<<endl;
}
return 0;
}