How to find the minimum set of vertices in a Directed Graph so that all other vertices can be reached

Question

For a given graph, I need to find the minimum set of vertices from which all other vertices can be reached.

Thus, the result of the function should be the smallest number of vertices from which all other vertices can be reached by following oriented edges.

The biggest result would be if there were no edges, so all nodes will be returned.

If there are cycles on the chart, one node is selected for each cycle. It doesn't matter which one, but it should be consistent if the algorithm starts again.

I'm not sure if there is an existing algorithm for this? If he has a name? I tried to do my research, and the closest thing seemed to find the poppy peak. If this is that algorithm, the actual algorithm could be developed, since the answer provided in this link is rather vague.

Given that I have to implement this in javascript, the preference would be a .js library or sample javascript code.

Answer 1

In my opinion, it's easy to find highly related components in a graph. Kosaraju's algorithm is one of the easiest approaches for this. It uses the first two searches, and not some later algorithms that use only one, but I like its simple concept most of all.

Edit: just to expand this, a minimal set of vertices is found, as suggested in the comments on this post: 1. Find strongly connected components of the graph - reduce each component to one vertex. 2. The remaining graph is the DAG (or the DAG set if the components were disabled), the root of which is the required set of vertices.

Answer 2

[EDIT # 2: As Jason Orendorf mentions in a comment, finding a vertex feedback set is redundant and will lead to creating a vertex set larger than necessary in the general case. kyun's answer is (or will be when it adds to the important information in the comments) the correct way to do this.]

[EDIT: I had two steps in the wrong way ... Now we have to guarantee the minimum.]

• Call all vertices with zero level Z No vertex in Z can be reached with any other vertex, so it must be included in the final set.
• Using the first step (or width), draw all the vertices accessible from each vertex in Z and delete them — these are vertices already “covered” by Z
• The graph now consists solely of directional cycles. Find the set of feedback vertices F that gives you the smallest possible set of vertices, the removal of which would break each cycle on the graph. Unfortunately, as can be seen from this link on Wikipedia, this problem is NP-hard for directed graphs.
• The vertex set you are looking for is Z+F