How to find the minimum set of vertices in a Directed Graph such that all other vertices can be reached
Given a directed graph, I need to find the minimum set of vertices from which all other vertices can be reached.
So the result of the function should be the smallest number of vertices, from which all other vertices can be reached by following the directed edges.
The largest result possible would be if there were no edges, so all nodes would be returned.
If there are cycles in the graph, for each cycle, one node is selected. It does not matter which one, but it should be consistent if the algorithm is run again.
I am not sure that there is an existing algorithm for this? If so does it have a name? I have tried doing my research and the closest thing seems to be finding a mother vertex If it is that algorithm, could the actual algorithm be elaborated as the answer given in that link is kind of vague.
开发者_如何学GoGiven I have to implement this in javascript, the preference would be a .js library or javascript example code.
From my understanding, this is just finding the strongly connected components in a graph. Kosaraju's algorithm is one of the neatest approaches to do this. It uses two depth first searches as against some later algorithms that use just one, but I like it the most for its simple concept.
Edit: Just to expand on that, the minimum set of vertices is found as was suggested in the comments to this post : 1. Find the strongly connected components of the graph - reduce each component to a single vertex. 2. The remaining graph is a DAG (or set of DAGs if there were disconnected components), the root(s) of which form the required set of vertices.
[EDIT #2: As Jason Orendorff mentions in a comment, finding the feedback vertex set is overkill and will produce a vertex set larger than necessary in general. kyun's answer is (or will be, when he/she adds in the important info in the comments) the right way to do it.]
[EDIT: I had the two steps round the wrong way... Now we should guarantee minimality.]
- Call all of the vertices with in-degree zero
Z
. No vertex inZ
can be reached by any other vertex, so it must be included in the final set. - Using a depth-first (or breadth-first) traversal, trace out all the vertices reachable from each vertex in
Z
and delete them -- these are the vertices already "covered" byZ
. - The graph now consists purely of directed cycles. Find a feedback vertex set
F
which gives you a smallest-possible set of vertices whose removal would break every cycle in the graph. Unfortunately as that Wikipedia link shows, this problem is NP-hard for directed graphs. - The set of vertices you're looking for is
Z+F
.
精彩评论