algorithm - 为使有向图从根连接而创建的最小边数

Question

要使所有节点从根可达，需要构建的新边的最小数量是多少？

给定有向图和根的索引。

我试着找到所有的组件(如果图是无向的)，然后找到没有父节点的节点数，我称这个数字为 sol。我遍历每个组件并询问孤立节点的数量。如果它没有并且不包含根，那么我将 1 添加到 sol，因为我应该将该组件连接到根。当组件是一个循环时，这是可能的。特例是包含根的组件。如果它没有父节点为 0 的节点，则 sol 保持不变，如果有，则 sol 变为 sol + number_of_those_nodes(如果 root 有父节点)或 sol + number_of_those_nodes - 1(否则)

你能帮我解决这个问题并创建一个有效的伪代码吗？

Answer 1

思路一:查找condensation图的(强连通分量图)。现在该图是非循环的，但答案是相同的:在强连通分量内添加边没有任何意义，并且不同的强连通分量究竟如何连接并不重要。我们的问题现在是一样的，但是在无环图上(根成为它的强连通分量)。

想法 2:请注意，对于除根之外的所有源顶点(入站度数为零的顶点)，我们应该添加至少一条边(入站边)。这给了我们答案的下限。

想法 3:如果该下限为零，则可以实现该下限，因为图形已经很好。

反证法:看一下从根未到达的任意顶点 X。它至少有一个入站边，否则我们的下界不会为零。假设它有一个来自任意顶点 Y 的入站边。如果达到 Y，则 X 也将达到，因此 Y 未达到。对 Y 重复相同的参数，现在我们得到了无限的顶点路径。但是它不能有两次相同的顶点，否则我们的图中会有一个循环，但它已经被压缩了。另一方面，顶点的数量是有限的。 Q.E.D.

想法 4:如果该下限大于零，我们可以绘制从根到每个源顶点的边，将下限降低到零并应用想法 3，从而实现精确的下限.