| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4550 人关注过本帖
标题:求有向图中所有最小简单环
只看楼主 加入收藏
dwadejames
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2017-9-1
结帖率:0
收藏
已结贴  问题点数:20 回复次数:4 
求有向图中所有最小简单环
求有向图中所有最小简单环就是要求那些顶点没有被其他环包含的环,而不论顶点的排列顺序如何。已经找到一个环:1->2->9,接着找到环:1->3->4->2->9,则这个环就要舍去,因为它包含了环1->2->9的所有节点,故舍去;
假设还有一个环:9->1->7->8->2,则这个环也要舍弃,因为它包含环1->2->9的所有节点,即不论节点排序如何,只要这个环包含了另一个环的所有节点,则这个环就要舍弃。
问题详细描述请见附件,有偿写代码,重金酬谢,qq:2970824391。
问题描述.pdf (185.69 KB)


[此贴子已经被作者于2017-9-1 15:00编辑过]

搜索更多相关主题的帖子: 最小 包含 节点 代码 qq 
2017-09-01 14:53
dwadejames
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2017-9-1
收藏
得分:0 
问题描述.pdf (185.69 KB)
2017-09-01 14:59
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9031
专家分:54061
注 册:2011-1-18
收藏
得分:20 
从其pdf中拷贝出来的
例子:图 1 是一个有向图,10 个顶点、16 条边,求得所有简单环如下:

1->2->9

1->3

1->3->4->2->9

1->3->5->6->4->2->9

2->4

3->5

现在要求所有最小简单环,结果如下:

1->2->9

1->3

2->4

3->5

求最小简单环就是要求那些顶点没有被其他环包含的环,而不论顶点的排列顺序如何。比如
上面环:1->3->4->2->9 包含了环 1->2->9 的所有节点,故舍去;环 1->3->5->6->4->2->9 同理。

假设现在还有一个环:9->1->7->8->2(实际上对于图 1 不存在),则这个环也要舍弃,因为它
包含环 1->2->9 的所有节点,即不论节点排序如何,只要这个环包含了另一个环的所有节点,
则这个环就要舍弃。



目前工作:现在能够求出所有简单环,只是效率太低,当有向图有 1000 个顶点左右,原来
算法就跑得很慢,所以现在想只求所有最小简单环,看看能否对后续工作提供帮助。



要求:给出一个有向图,要能在短时间内求出所有最小的简单环。

2017-09-01 16:51
dwadejames
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2017-9-1
收藏
得分:0 
回复 3楼 rjsp
谢谢你。
2017-09-01 17:06
dwadejames
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2017-9-1
收藏
得分:0 
其实就是求:那些环内的顶点集合的子集不再构成其他环的环
2017-09-04 09:55
快速回复:求有向图中所有最小简单环
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031777 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved