我正在尝试从有向无环图创建强连接组件。
输入是表单中的边的列表
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发布于 2012-10-02 07:09:15
如果我没理解错你的问题,你应该用邻接矩阵表示你的图。最初,它将是一个带有1的稀疏矩阵,或者是当前边所在的位置。
使用简单的矩阵遍历,创建SCC所需的所有0元素-> 1,这些转换中的每一个都是您需要添加的边。
还有一个很好的wiki页面,显示了可能用于此的流行算法:
http://en.wikipedia.org/wiki/Strongly_connected_component
它推荐Tarjan's和Path-based算法作为最实用的算法。
https://stackoverflow.com/questions/12681785
复制相似问题