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

给定一个有向图，我需要找到可以到达所有其他顶点的最小顶点集合。如何在有向图中找到最小的一组顶点，以便可以达到所有其他顶点

所以函数的结果应该是最小的顶点数，通过跟随有向边可以达到所有其他顶点。

可能的最大结果是如果没有边缘，所有节点都会返回。

如果图中有周期，则为每个周期选择一个节点。哪一个并不重要，但如果算法再次运行，它应该是一致的。

我不确定这是否存在现有算法？如果是这样，它有一个名字？我试图做我的研究，最接近的东西似乎是找到mother vertex 如果是这种算法，是否可以详细阐述实际算法，因为在该链接中给出的答案有点模糊。

鉴于我必须在JavaScript中实现此，首选项将是一个.js库或JavaScript示例代码。

来源

2010-12-20 Ryan Ramage

您在标题中提到了一个DAG（有向无环图），但随后提到“如果图中有周期......”您是否只是指有向图？ – Davy8 2010-12-20 18:59:07

没有你的问题是不同的 – 2010-12-20 19:09:24

对不起，是的，它只是一个有向图，而不是DAG，因为可以有循环。我已经更新了标题。 – 2010-12-20 19:11:58

根据我的理解，这只是在图中找到强连通的组件。 Kosaraju's algorithm是这样做的最新方法之一。它使用两次深度优先搜索来对付一些仅使用一次的算法，但我最喜欢它的简单概念。

编辑：为了扩大这一点，最小的一组顶点被发现，正如在这篇文章的评论中建议的那样： 1.找到图的强连通组件 - 将每个组件缩减为单个顶点。 2.剩余的图是一个DAG（或者如果存在不连贯的组件，则是一组DAG），其中的根形成所需的一组顶点。

来源

2010-12-21 18:05:33 kyun

为了扩大这一点：1.找到强连接的组件。 2.对于每个顶点，任意选择其中一个顶点，并将强连通的组件收缩到该顶点。这留下了一个DAG。 3.选择边缘为零的所有剩余顶点。完成。（道歉为我所介绍的任何错误！） – 2010-12-21 18:17:09

如果我看看http://en.wikipedia.org/wiki/Strongly_connected_component上的示例图，我想要的结果是[a]，[b]或[E]。正如你可以从那些起始节点到所有其他节点（通过多跳）。但是，你建议的算法会产生[a，c，g]吗？ – 2010-12-21 18:37:39

我应该更清楚。正如Jason Orendorff所建议的那样，您必须找到强连通的组件（例如 - [abef]，[fg]和[cdh]），将每个任意减少到一个顶点（比如[a] [g]和[c] ）。现在，找到这些组件之间的连接（生成一个DAG，因为所有的周期都收缩到一个顶点） - 这将是[ac] [cg]并选择剩余图中的“根”（节点中没有）成为你的解决方案。 – kyun 2010-12-21 19:24:18

[编辑＃2：正如Jason Orendorff在评论中提到的那样，发现反馈顶点集是过度杀伤性的，并且会产生一个比通常所需更大的顶点集。 kyun's answer（或将是，当他/她在评论中的重要信息增加了）做正确的方式]

[编辑：我有两个步骤南辕北辙......现在我们应该保证极小。]

呼叫所有顶点在度零Z。 Z中没有顶点可以通过任何其他顶点到达，因此它必须包含在最终集合中，其中必须包含在中。
使用深度优先（或宽度优先）遍历，追踪从Z中每个顶点可到达的所有顶点并删除它们 - 这些顶点已被Z“覆盖”。
该图现在纯粹由定向循环组成。找到一个feedback vertex setF它给你一个最小的可能的顶点集，它的去除会破坏图中的每个循环。不幸的是，如维基百科链接所示，这个问题对有向图而言是NP难的。
您正在寻找的顶点集是Z+F。

来源

2010-12-20 19:30:16

为什么找到一个反馈顶点集，而不是kyun建议的？这似乎是不必要的额外工作。 – 2010-12-21 18:14:59

@Jason：想一想，你是对的。没有必要在每个循环中找到一个顶点。 – 2010-12-22 00:02:56

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

回答

相关问题