find the minimum number of vertices in a directed graph from which the other vertices are reachable [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

In a directed graph i want to call bfs on some of the vertices so that all of the vertices will be met.

(in other words all of the other vertices are reachable from these chosen vertices.)

I want to find the minimum number of such vertices.

Actually this problem arises in social networks when we want to find the minimum number of people to which if we send a message then all of the network members will get that.(suppose that we know when someone gets the message he/she will send that to all of his/her followers.)

Can anyone help?

Answer 1

For the graph without cycle(i.e acyclic graph), it will be easy. All the nodes without incoming edges will be an optimal solution. Since all other nodes should be reachable from one of the nodes.

For the graph with cycle, find strongly connected component first, then you get a acyclic graph. The method above works again.