Find depth of all nodes in a graph stored in the form of an adjacency list in a single BFS/DFS run

0
votes

I'm new to graph theory and have been solving a few problems lately. I was looking for a way to find the depth of every node in the graph. Here's how I formalized it on paper:

  1. Run a for loop iterating over every vertex

  2. If the vertex is not visited, run a DFS with that vertex as a source

  3. In the DFS, as long as we have more vertices to go to, we keep going (as in the Depth First Search) and we keep a counter, cnt1, which increments every time
  4. While backtracking in the recursive DFS call, we initialize a new counter starting from the current count at the last vertex, and give the value cnt1-cnt2 to each vertex so on and keep decreasing cnt2.

I'm not sure if this is correct and am not able to implement the same in code. Any suggestions? For the record, my graph is stored in the form of an adjacency list, in the form of an array of vectors like:

vector <int> a[100];

EDIT:The input graph is a collection of directed trees. We have a depth label for each node - denoting the number of nodes on the simple path from the root to it. Hence we need to find the maximum depth of each node

1
c++algorithmgraphdepth-first-search
Is the graph rooted / does it have a particular node with respect to which the "depth" is being calculated? If so, why not floodfill out from that vertex with BFS? If not, what "depth" are you referring to here? – Jerry Federspiel
I'm confused. How is the depth label for each node different form its maximum depth? – beaker
Possible duplicate of How to get the MAX level(depth) of a vertex in a boost graph – underscore_d

1 Answers

0
votes

You may find these links helpful:

http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/

http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

Here classes are used to implement BFS/DFS using an adjacency list representation.Just like the array 'visited' of bool type used here...you have to also create another array 'depth' in wich you can store the depth of each element while computation..and then output that array in the end..