CODEWITHSUNDEEP
c++algorithmgraph-theory
Philip Moreira
Philip Moreira

Reputation: 311

Directed Graph - How to count the number of vertices from which each other vertex in graph is reachable?

In a directed graph how to efficiently count the number of vertices from which each other vertex in graph is reachable?

Upvotes: 4

Views: 2578

Answers (2)

ciamej
ciamej

Reputation: 7068

If there is no cycle in the graph, there can be only one such vertex and it has an in-degree zero, and there are no other vertices with an in-degree zero. You then have to run a DFS to check if all other vertices are reachable from it. So the answer is either one or zero, depending on the result of DFS.

If there is a cycle, then all the vertices in the cycle have this property or none of them have it.

If you detect a cycle, replace all the vertices in the cycle with one vertex and keep a label for that vertex of how many vertices it represents. Use the same procedure as above. I.e., check in-degrees and run DFS from the new node. The answer will be zero or the label.

Detecting a cycle can be accomplished using a DFS.

There might be several cycles in the graph. In that case you have to eliminate all of them. You can eliminate all of them in one linear pass of DFS, but that's tricky. You could also use Tarjan's algorithm as suggested by btilly in his answer.

Upvotes: 2

btilly
btilly

Reputation: 46417

Use Tarjan's strongly connected components algorithm to detect all loops then construct a graph with each strongly connected component collapsed to a single node.

Now in this new graph, it is sufficient to look for a vertex with no in edges. If that vertex connects to every other one (verifiable with a breadth first linear search), then everything in the strongly connected component that it came from is in your set, otherwise no vertex is in your set.

Upvotes: 1

Related Questions