In a directed graph i want to call bfs on some of the vertices so that all of th
ID: 654531 • Letter: I
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?
Explanation / Answer
The problem can be reduced to finding "sources" (opposite of "sinks", nodes with in-degree zero) in the graph. Suppose there is an optimal solution in which B is one of the chosen nodes and there is an edge A?B. Then we can put A instead of B in the solution and still cover the whole graph (A can reach B, so it can reach all the nodes reachable from B). On the other hand, "sources" have to be chosen because they are not reachable from any other node. Then we should repeatedly find "source" nodes, chose them and mark all the vertices reachable from them as covered.
If there are no "source" nodes, then the graph must have cycles. All the nodes in a cycle are equivalent in terms of the nodes they can reach. Thus, they can be simplified into a "supernode". If eventually the supernode becomes a "source" and hence chosen by the algorithm, that means an arbitrary node of the cycle can be chosen.
So the algorithm repeatedly performs iterations of "finding source nodes" and "simplification" until the whole graph is covered.