频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
邻接表有向图DFS
2016-08-18 09:35:44         来源:S1xe的博客  
收藏   我要投稿

DFS简介

对一个通用有向图,从一个给定起始顶点开始的一个深度优先遍历。首先访问起始顶点,接着顺着有向弧尽可能深的访问从起始顶点可以到达并且没有被访问过的顶点

DFS算法

/* 对一个有向图进行深度优先遍历,找出从一个给定的出事顶点开始,能够到达的所有顶点 */
(1)访问初始顶点v。
(2)对于每个邻接于v的顶点w做以下工作:
如果w未被访问,将w作为初始顶点,应用深度优先遍历算法
EndFor


最短路径

最短路径简介

寻找一个有向图中从一个起始顶点start到一个目的顶点destination之间一条最短路径。
显示从start到destination的一条最短路径上的所有顶点,如果无法从start到达destination,则给出一条提示信息

最短路径算法

访问start,并将其标签置为0 初始化distance为0 初始化一个队列为仅包含start 当destination还未被访问且顶点队列非空,做以下工作
1.从队列中删除一个顶点v
2.如果v的标签大于distance,将distance增1
3.对于邻接于v的米一个顶点w:
如果w还未被访问,则
访问w,并将其标签置为distance+1 将w添加到队列中 如果destination还未被访问,则
显示”Destination not reachable from start vertex”
否则,如下查找最短路径中的p[0],…,p[distance]
1.初始化p[distance]为destination
2.对于distance-1 ~ 0的每一个值k
找到邻接于p[k+1]并标签为k的一个顶点p[k]

完整代码如下

所用IDE:VS2015
如果所用编译器不支持C+11,可以将部分需要C++11特性的代码替换

Digraph.h

Enter name of network file : NetworkFile.dat

The digraph'sAdjacency-List Representation:
1:Los_Angeles           - 3     4       6
2:San_Francisco         - 1     3       4
3:Denver                - 1     2       5
4:Chicago               - 3     8
5:Boston                - 4     6
6:New_York              - 4     7       8
7:Miami                 - 8     3       5
8:New_Orleans           - 1     7

Number of start  city ? 5
Number of destination ? 1
Shortest path is :
5   Boston
       |
       v
4   Chicago
       |
       v
3   Denver
       |
       v
1   Los_Angeles

More(Y or N) ?

测试所用数据

Network.dat

Los_Angeles
3 3 4 6
San_Francisco
3 1 3 4
Denver
3 1 2 5
Chicago
2 3 8
Boston
2 4 6
New_York
3 4  7 8
Miami
3 8 3 5
New_Orleans
2 1 7
点击复制链接 与好友分享!回本站首页
相关TAG标签 有向图
上一篇:httpclient 4.X 异步 async util
下一篇:正则表达式基础
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站