24小时热门版块排行榜    

查看: 1160  |  回复: 6

gue2

木虫 (著名写手)

[求助] 求无向图中顶点对之间的所有路径 已有2人参与

不是求最短路径,是所有不重叠的路径(任意两个路径之间没有共同的边)。请给出基本思想或容易读懂的算法步骤,先谢过!
回复此楼
落霞与孤鹜齐飞
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

gue2

木虫 (著名写手)

有求出所有路径的算法,从所有路径中选出彼此不相交的路径貌似NP问题
落霞与孤鹜齐飞
2楼2014-05-21 16:41:32
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

nlyang

禁虫 (著名写手)

★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感谢参与,应助指数 +1
gue2: 金币+10, ★★★很有帮助 2014-05-22 15:41:24
本帖内容被屏蔽

3楼2014-05-22 09:07:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

gue2

木虫 (著名写手)

引用回帖:
3楼: Originally posted by nlyang at 2014-05-22 09:07:26
建议采用广度优先和剪枝法,采用树来做为数据结构。
基本的idea如下:
输入:顶点A,B,以及图内所有有连接关系的顶点对
算法:
1)根结点为A,高度为1
2)对于每个叶节点,进行判断:
如果是B,则输出从根节 ...

是一个办法。感觉结果不是唯一的。
落霞与孤鹜齐飞
4楼2014-05-22 15:41:07
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

nlyang

禁虫 (著名写手)

本帖内容被屏蔽

5楼2014-05-22 18:09:55
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

cvml

新虫 (初入文坛)

【答案】应助回帖

感谢参与,应助指数 +1
你可以看看佛洛伊德算法。说的就是这个问题。
6楼2014-05-23 12:33:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

康师傅1

铜虫 (小有名气)

不相交路径,非交叉路径研究的就是这个问题,是个np难问题

[ 发自手机版 http://muchong.com/3g ]
7楼2014-05-23 15:25:56
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 gue2 的主题更新
信息提示
请填处理意见