如何在有向图中找到最小顶点集，以便可以到达所有其他顶点

Question

给定一个有向图，我需要找到可以到达所有其他顶点的最小顶点集。

所以函数的结果应该是最小数量的顶点，从这个顶点沿着有向边可以到达所有其他顶点。

如果没有边，可能的最大结果将是，因此将返回所有节点。

如果图中存在环，则对于每个环，选择一个节点。哪一个并不重要，但如果再次运行算法，它应该是一致的。

我不确定是否有现有的算法？如果有的话它有名字吗？我尝试过进行研究，最接近的似乎是找到一个母顶点 如果是那个算法，是否可以详细说明实际的算法，因为该链接中给出的答案有点模糊。

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

Answer 1

根据我的理解，这只是找到图中的强连通分量。 Kosaraju 的算法 是实现此目的的最巧妙的方法之一。它使用两个深度优先搜索，而后来的一些算法只使用一个，但我最喜欢它的简单概念。

编辑：为了扩展这一点，按照本文评论中的建议找到了最小顶点集： 1. 找到图的强连通分量 - 将每个分量简化为单个顶点。 2. 剩余的图是一个 DAG（如果存在断开的组件，则为 DAG 集），其根形成所需的顶点集。

Answer 2

这个怎么样：

class Graph:
    def __init__(self, n):
        self.n = n
        self.adj_list = [[] for _ in range(n)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)

    def find_min_ancestor_set(self):
        visited = set()
        post_order_stack = []
        for u in range(self.n):
            if u not in visited:
                self._dfs(u, visited, post_order_stack)

        visited = set()
        stack = []
        res = []
        while post_order_stack:
            u = post_order_stack.pop()
            if u not in visited:
                res.append(u)
                self._dfs(u, visited, stack)
        return res
    
    def _dfs(self, u, visited, stack):
        visited.add(u)
        for v in self.adj_list[u]:
            if v not in visited:
                self._dfs(v, visited, stack)
        stack.append(u)

def main():
    g = Graph(11)
    g.add_edge(0,1)
    g.add_edge(1,2)
    g.add_edge(2,0)
    g.add_edge(2,1)
    g.add_edge(2,4)
    g.add_edge(3,1)
    g.add_edge(5,4)
    g.add_edge(6,7)
    g.add_edge(9,10)
    g.add_edge(10,9)

    res = g.find_min_ancestor_set()
    print(res)

if __name__ == '__main__':
    main()

输出：[9,8,6,5,3]

Answer 3

[编辑 #2：正如 Jason Orendorff 在评论中提到的那样，找到反馈顶点集是多余的，并且会产生比一般需要更大的顶点集。 kyun 的回答是（或者将会是，当他/她在评论中添加重要信息时）正确的方法。]

[编辑：我有两个步骤以错误的方式进行...现在我们应该保证最小化。]

1. 将所有入度为零的顶点称为

   Z

   。

   Z

   中的任何顶点都不能被任何其他顶点到达，因此它必须包含在最终集合中。
2. 使用深度优先（或广度优先）遍历，找出从

   Z

   中每个顶点可到达的所有顶点并删除它们——这些是已经被

   Z

   “覆盖”的顶点。
3. 该图现在纯粹由有向循环组成。找到一个 反馈顶点集

   F

   ，它为您提供尽可能小的顶点集，删除这些顶点将破坏图中的每个循环。不幸的是，正如维基百科链接所示，这个问题对于有向图来说是 NP 困难的。
4. 您要查找的顶点集是

   Z+F

   。