首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >从DAG创建强连接组件

问从DAG创建强连接组件
EN

Stack Overflow用户
提问于 2012-10-02 06:05:40
回答 1查看 4.8K关注 0票数 1

我正在尝试从有向无环图创建强连接组件。

输入是表单中的边的列表

代码语言:javascript
复制
1 2
3 5
etc

我需要创建一个最小边集的外点,将其添加到给定的图中,以生成一个强连接分量图……

有什么想法吗?

下面是我正在寻找的一个示例:

给定输入:

代码语言:javascript
复制
1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9

输出将是创建强连接组件所需的最小边数。

输出:

代码语言:javascript
复制
3 1
4 5
7 6
8 1
9 2
EN

回答 1

Stack Overflow用户

发布于 2012-10-02 07:09:15

如果我没理解错你的问题,你应该用邻接矩阵表示你的图。最初,它将是一个带有1的稀疏矩阵,或者是当前边所在的位置。

使用简单的矩阵遍历,创建SCC所需的所有0元素-> 1,这些转换中的每一个都是您需要添加的边。

还有一个很好的wiki页面,显示了可能用于此的流行算法:

http://en.wikipedia.org/wiki/Strongly_connected_component

它推荐Tarjan's和Path-based算法作为最实用的算法。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/12681785

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档