Let's say in my directed graph G = (V, E), I have nodes which have certain numbers assigned to it, n[v]. I want to find the highest n[v] for each vertex, that is max(n[v]) means the maximum n[v] of the node reachable from each vertex in G.
What would we the efficient to solve this?
I am thinking on the lines of DFS on each node without backtracking and comparing the n[v] for all the 'visited' nodes and storing the maximum n[v] value for that path.
However, I am afraid that this might not be the efficient solution.
0
votes
1 Answers
0
votes
Why do you think this is inefficient?
If you run DFS on all source nodes (nodes that only out edges and no edges coming in) you are guaranteed to visit all nodes.
You can easily store the max(n[v]) on a node only after you visit all of its children.
And then if you reach a node that already has a max(n[v]) after starting from another source, you know you don't have to continue exploring that nodes children because the value is only assigned once you've visited all the children.
You're doing this in ~|E| steps (unless you have isolated nodes with no in our out edges) since you'll travel each edge exactly once.
I guess if you want to be super accurate you'll be doing this in |E| + |S| steps where |S| is the number of source nodes in your graph.
This seems to be pretty efficient to me. I'm not sure if it's possible to get a deterministic answer without checking every edge at least once.
Edit:
Also, I guess if you want to be extra complete, you may need to run a pre-step of checking all V nodes to determine which are source nodes. AND THEN running DFS on only source nodes.
So overall if would be |V| + |E| + |S| steps which is O(|V| + |E|)
