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

Question

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

因此，函数的结果应该是最小数量的顶点，通过遵循有向边可以到达所有其他顶点。

如果没有边，返回所有节点，则可能的最大结果为所有节点。

如果图中存在循环，对于每个循环，选择一个节点。无论哪个节点被选中都无所谓，但如果再次运行算法，则应保持一致。

我不确定是否存在现有的算法？如果有，它有名称吗？我已经尝试过研究，最接近的东西似乎是找到母顶点 如果是那个算法，能否详细说明实际算法，因为给出的链接答案有点模糊。

考虑到我必须在javascript中实现这一点，首选是.js库或javascript示例代码。

- Ryan Ramage

---

标题中提到了DAG（有向无环图），但随后又提到“如果图中存在循环...” 你是不是只是指一个有向图？ - Davy8

不是你的问题和那个问题不同。 - Saeed Amiri

抱歉，是有向图，而不是 DAG，因为可能存在环。我已经更新了标题。 - Ryan Ramage

我们讨论的是多少个节点和多少条边？ - MAK

我猜如果问题是NP完全的话，那就很重要了...在这个应用程序中，我无法想象会有超过10k个节点，每个节点大约有10条边。 - Ryan Ramage

Answer 1

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

编辑：仅为扩展说明，在此帖子的评论中建议找到顶点的最小集合： 1. 找到图的强连通分量-将每个分量缩减为单个顶点。 2. 剩余的图是DAG（如果存在不连通的组件，则为DAG集），其根形成所需的顶点集。

- kyun

---

稍微详细解释一下：1. 找到强连通分量。2. 对于每个强连通分量，任意选择一个顶点，并将强连通分量缩成该顶点。这样就得到了一个有向无环图（DAG）。3. 选择所有剩余的入度为零的顶点。完成。（如果我翻译有误，请见谅！） - Jason Orendorff

如果我查看http://en.wikipedia.org/wiki/Strongly_connected_component上的示例图，我希望结果是[a]、[b]或[e]之一。因为你可以从这些起始节点到达所有其他节点（通过多次跳跃）。但是，您建议的算法是否会产生[a,c,g]？ - Ryan Ramage

我应该表述得更清楚。正如Jason Orendorff所建议的那样，您需要找到强连通分量（在示例中为[abef]、[fg]和[cdh]），将每个分量任意缩减为一个顶点（例如[a] [g]和[c]）。现在，找到这些组件之间的连接（产生一个DAG，因为所有循环都已收缩为单个顶点）- 这将是[ac] [cg]，然后选择剩余图的“根”（没有入节点）作为您的解集。 - kyun

@kyun：思路不错，请将该评论添加到您的答案中，我会点赞。 - j_random_hacker

你能澄清一下“现在，找到这些组件之间的连接”的步骤吗？你是指1.仅使用所选顶点的原始连接还是2.查找从“组件”中一组顶点到所有其他“组件”的所有连接？ - Ryan Ramage

@Ryan Ramage - 第二件事情是组件之间的连接。你可以将其视为第二个图，通过仅将每个强连通分量缩减为单个顶点而获得。 - kyun

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]

- Jose Saraiva

---

你的回答可以通过提供更多的支持性信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的回答是否正确。你可以在帮助中心找到关于如何撰写好回答的更多信息。 - undefined

Answer 3

[编辑 #2：正如Jason Orendorff在评论中提到的那样，查找反馈顶点集是过度的，并且通常会产生比必要更大的顶点集。kyun's answer是（或将成为）正确的方法，当他/她添加评论中的重要信息时。]

[编辑：我把两个步骤搞错了...现在我们应该保证最小化。]

1. 调用所有入度为零的顶点Z。没有任何一个顶点能到达Z中的任何其他顶点，因此它们一定被包含在最终集合中。
2. 使用深度优先（或广度优先）遍历，跟踪每个Z中顶点可以到达的所有顶点，并删除它们--这些是由Z已经“覆盖”的顶点。
3. 图现在完全由有向循环组成。找到一个反馈顶点集F，它给出了一组最小的顶点，去除它们会打破图中的每一个循环。不幸的是，正如维基百科链接所示，对于有向图来说，这个问题是NP难问题。
4. 你要寻找的顶点集是Z+F。

- j_random_hacker

---

为什么要找反馈顶点集，而不是kyun建议的方法？这似乎是不必要的额外工作。 - Jason Orendorff

@Jason：想想看，你是对的。并不需要在每个循环中找到一个顶点。 - j_random_hacker