CODEWITHSUNDEEP
algorithmgraphdepth-first-search
6c656c
6c656c

Reputation: 322

Computing level of nodes in a graph

I want to compute the level of each node in a directed graph. I'm currently applying a depth-first search algorithm on vertices that have no incoming edges. Considering the graph below, for instance:

The expected result is:

Vertex | Level
1      | 0
2      | 1
3      | 2
4      | 1
5      | 3
6      | 4

In this particular case, if we start by applying DFS on 4, then all results for vertices 4, 3, 5 and 6 are going to be wrong, since 1 has level 0. I've tried to always consider the greatest result for each one of the nodes, so in this case the results for 3, 5, and 6 are replaced when applying DFS on 1. It works, but I can't find a way to correctly compute the level of vertex 4.

I'm working only with directed acyclic graphs.

I'm not including any code here because it is a pretty straightforward DFS implementation and I'm not struggling implementation-wise.

Any hint would be much appreciated.

Upvotes: 1

Views: 943

Answers (1)

Anit Aggarwal
Anit Aggarwal

Reputation: 105

You can compute the levels starting from each vertex without having an incoming edge. Then you can store the maximum value for each vertex until the end. For eg :- Vertex 3 will have values 1 and 2 when traversed from starting points vertex 1 and vertex 4 respectively. At last, you can update the vertices not having the incoming edge(number on child -1). If there's a situation where there multiple children of such a vertex, then you might want to select the child with maximum number on it for replacement and then run the algorithm from that vertex again to see if changes the numbers assigned to any of the other children.

Upvotes: 1

Related Questions