[求助]关于判别图中两个顶点之间的简单路径的程序设计
采用邻接表作为存储结构。编写程序判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径
高手可以指导一下吗?如果有源代码的话最好,没有的话指导一下该怎么做,从什么地方入手?谢谢
采用邻接表作为存储结构。编写程序判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径
高手可以指导一下吗?如果有源代码的话最好,没有的话指导一下该怎么做,从什么地方入手?谢谢
如果图中没有负权路径的话,那就可以用最佳优先搜索的变种:
设搜索树为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。
由于是简单路径,所以能够减掉大量的分支,算法应该够快了,
有不对请指出。