我正在尝试从有向无环图创建强连接组件。
输入是表单中的边列表
1 2
3 5
etc
我需要创建要添加到给定图中的最小边集的出点，以制作强连通分量图......
有任何想法吗？
这是我正在寻找的示例：
给定输入：
1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9
输出将是添加创建强连接组件所需的最小边数。
输出：
3 1
4 5
7 6
8 1
9 2
问问题
5101 次
2 回答
4
假设图中没有孤立的顶点，您只需添加 max(|sources|,|sinks|) 边即可使其强连接。
令 T={t 1 ,…,t n } 为汇，{s 1 ,…,s m } 为 DAG 的源。假设 n <= m。（另一种情况非常相似）。考虑如下定义的两个集合之间的二分图 G(T,S)。G(T,S) 有一条边 (t i ,s j ) 当且仅当 t i可以从 s j到达。
令 M 为 G(T,S) 中的最大匹配。不失一般性假设 M 由 k 条边组成：{(t 1 ,s 1 ),(t 2 ,s 2 ),...,(t k ,s k )}。在原始图 DAG G 中，添加有向边 {(t 1 ->s 2 ),(t 2 ->s 3 ),...,(t k−1 ->s k ),(t k ->s 1 )}。很容易看出，通过添加这些边，由 M 诱导的顶点在 G 中是强连接的。
现在考虑 G(T,S) 中的剩余顶点。因为 M 最大，所以 S−M 中的每个顶点（分别是 T−M）应该连接到 T 中的一个顶点（分别是 S−M）。所以我们将剩余的顶点任意配对，例如 {(t k+1 ,s k+1 ),…,(t n ,s n )} 并在 G 中添加相应的有向边。对于每个剩余的源顶点 source s i (i 属于 {n+1,…,m} 我们在 G 中添加边 (t 1 ->s i )。因此添加的边总数为 max(|sources|,|sinks|)。
编辑：添加几个例子
对于您输入的示例。我们首先计算一个最大匹配，比如说：
3--1
4--2
7--5
8--6
所以我们添加边缘：
3->2
4->5
7->6
8->1
匹配中不存在的剩余（汇）顶点是 9，因此我们将弧从 9 添加到匹配中的任何源顶点，例如9->1。
这是另一个示例，说明了算法的所有步骤：
输入图：
12 3 5 9 10 (sources)
\|/ /|\ \/
4 6 7 8 11 (sinks)
最大匹配：
4--1
6--5
11--9
所以我们添加边缘：
4->5
6->9
11->1
现在剩余的汇是{7, 8}，剩余的源是{2, 3, 10}。我们将 7 与 2 和 8 与 3 任意配对并添加：
7->2
8->3
最后，剩余（源）顶点为 10，我们添加：
4->10
于 2012-10-03T12:57:46.327 回答
0
如果我正确理解了您的问题，您应该使用图形的邻接矩阵表示。最初，它将是一个稀疏矩阵，其中包含 1 或当前边缘所在的位置。
使用矩阵的简单遍历，创建 SCC 所需的所有 0 元素 -> 1，并且这些转换中的每一个都将是您需要添加的边。
还有一个很好的 wiki 页面显示了可能用于此的流行算法：
于 2012-10-01T23:09:15.283 回答