如何在有向图中找到最小的顶点集，以便可以到达所有其他顶点 [英] 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.

鉴于我必须在javascript中实现此功能，因此首选项将是.js库或javascript示例代码.

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

推荐答案

据我了解，这只是在图中找到强连接的组件. Kosaraju的算法是最简单的方法之一.它使用两次深度优先搜索，而不是后来的仅使用一次深度搜索的算法，但是我最喜欢它的简单概念.

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.

对此进行扩展，找到了最小的一组顶点，正如对这篇文章的评论中所建议的那样:1.找到图的强连接组件-将每个组件简化为单个顶点.2.其余图是DAG(如果存在断开连接的组件，则为DAG组)，其根形成所需的顶点组.

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.

这篇关于如何在有向图中找到最小的顶点集，以便可以到达所有其他顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！