| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2366 人关注过本帖
标题:[求助]关于判别图中两个顶点之间的简单路径的程序设计
只看楼主 加入收藏
jay393727443
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2007-7-6
收藏
 问题点数:0 回复次数:2 
[求助]关于判别图中两个顶点之间的简单路径的程序设计

采用邻接表作为存储结构。编写程序判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径
高手可以指导一下吗?如果有源代码的话最好,没有的话指导一下该怎么做,从什么地方入手?谢谢

搜索更多相关主题的帖子: 图中 程序设计 顶点 路径 源代码 
2007-07-06 16:47
mjh_abc
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2007-7-7
收藏
得分:0 

如果图中没有负权路径的话,那就可以用最佳优先搜索的变种:
设搜索树为T,起点为s,
开始时T={(s,0)},序偶(s,0)表示一个搜索结点,0表示代价,即从起点到该点的最短路径长。
设集合U={},表示算法已确定最短路经的节点集合。
然后
1。从T中找出一个代价最小的节点N.
2。判断N的代价如果等于要寻找的代价A,则存在一条长度为A的简单路径。算法结束。
3。如果大于A,则不存在长度为A的简单路径,算法结束。
4。判断N是否在U中,如果在U中,则这不是一条简单路径,转1继续执行。
5。T=T-N,将N从T中删除。
6。U=U+N,将N并入U中。
7。设N=(a,b),从点a开始,扩展所有和a领接的顶点。
即对于任意和a领接的顶点x,
将(x,b+从a到x的路径长)加入T中。
8。转1。

由于是简单路径,所以能够减掉大量的分支,算法应该够快了,

有不对请指出。

2007-07-07 09:09
jay393727443
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2007-7-6
收藏
得分:0 
回复:(mjh_abc)如果图中没有负权路径的话,那就可以...
您好,能加一下我QQ吗?      530080937
2007-07-07 10:08
快速回复:[求助]关于判别图中两个顶点之间的简单路径的程序设计
数据加载中...
 
   



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

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