CODEWITHSUNDEEP
c++data-structuresgraph-theory
WhoCares
WhoCares

Reputation: 225

minimum number of nodes that traverse entire graph

Note: The question is entirely changed.

In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover problem nor dominating-set problem since we don't need to select node 3. We say that, if we select node 0, we can go to node 1 from there and if we select node 2, we can go to node 3 and then node 4 from there.

If I run a SCC algorithm on it, it finds all vertices as a different SCC and I can't go from there to anywhere:

C:\>project2 ../../input.txt o.txt
Following are strongly connected components in given graph (Each line is a different SCC)
2
4
3
0
1

enter image description here

Upvotes: 0

Views: 1336

Answers (1)

Mohaimin66
Mohaimin66

Reputation: 113

If there is no cycle in the graph i.e. the graph is a Directed Acyclic Graph (DAG), then we just need to count the indegrees for each node. The set of nodes with indegree 0 is the required set.

In case you are not familiar with indegree, if there is an edge a->b then indegree of b increases by 1.

This works because, if there is an edge a->b i.e. b has an indegree it means there is a node a from which b is reachable. So it is always better to include node a to the set instead of b. A node with indegree 0 has no other way to get visited unless we start with the node itself. So it will be included in the set.

In case there is a cycle in the graph, we search for Strongly Connected Components(SCC). Then we have build a new graph considering a SCC as one node and add edges from initial graph which connect two different SCC's. The new graph will be a DAG. Then we can apply the above procedure to find the required set of nodes.

Upvotes: 2

Related Questions