《数据结构第十四课(2011年11月7日)》由会员分享，可在线阅读，更多相关《数据结构第十四课(2011年11月7日)（58页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构 数据结构与算法数据结构与算法 Data Structure and Algorithms 第十四课 西安交通大学自动化系西安交通大学自动化系 蔡忠闽蔡忠闽 杜友田杜友田 数据结构数据结构 7.1 图的定义和术语图的定义和术语 7.2 图的存储结构图的存储结构 7.3 图的遍历图的遍历 7.4 图的连通性问题图的连通性问题 7.5 最短路径最短路径 第七章第七章 图图 2 数据结构数据结构 7.2 7.2 图的存储结构图的存储结构 在图的邻接矩阵表示中，有一个记录各个顶点信息的在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表顶点表，还有，还有一个表示各个顶点之间关系的一个表
2、示各个顶点之间关系的邻接矩阵邻接矩阵。 设图设图 A = (V, E)是一个有是一个有 n 个顶点的图，则图的邻接矩阵是一个二个顶点的图，则图的邻接矩阵是一个二维数组维数组 A.edgenn，定义：，定义： i，j表示存放在表示存放在顶点表顶点表中第中第i个和第个和第j个顶点。个顶点。 无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。 7.2.1 7.2.1 邻接矩阵邻接矩阵 (Adjacency Matrix)(Adjacency Matrix) ,),( , , .否则否则如果如果 00 min = closedge j
3、.lowcost; printf(closedge k . adjvex, G.vexs k ); / 输出该边 closedge k .lowcost = 0; / 顶点k并入U for( j= 1; j=G.vexnum; j+ ) / 修改V-U中每个顶点到U的最小边 if( G.Edge k j closedge j .lowcost) closedge j = G.vexs k , G.Edge k j ; 34 7.4 7.4 图的连通性问题图的连通性问题 数据结构数据结构 Kruscal算法的基本思想：算法的基本思想： 设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络
4、N = V, E ,最初先最初先构造一个只有构造一个只有 n 个顶点，没有边的非连通图个顶点，没有边的非连通图 T = V, , 图中每个顶点自成一个连通分量。当在图中每个顶点自成一个连通分量。当在 E 中选到中选到一条具有最小权值的边时一条具有最小权值的边时,若该边的两个顶点落在不同若该边的两个顶点落在不同的连通分量上的连通分量上（没有构成回路）（没有构成回路），则将此边加入到则将此边加入到 T 中；中；否则将此边舍去，重新选择一条权值最小的边。如此重否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。复下去，直到所有顶点在同一个连通分量上为止。 2
5、Kruscal 2 Kruscal 算法算法 35 7.4 7.4 图的连通性问题图的连通性问题 数据结构数据结构 Kruscal 算法的基本描述算法的基本描述 设设G(V，E)是个有权无向连通图：是个有权无向连通图： T V, ; while( T 的边数的边数 n - 1) 在在 E 中选择代价最小的边中选择代价最小的边 ( u,v ); EE ( u,v ); if( ( u,v )不和不和 T 中已有的边构成回路中已有的边构成回路 ) / 或或 if( u,v分属分属T的不同的连通分量的不同的连通分量 ) TT + ( u,v ); 36 7.4 7.4 图的连通性问题图的连通性问题
6、数据结构数据结构 1 2 3 4 6 5 5 6 5 1 7 3 2 5 4 6 1 2 3 4 6 5 5 1 3 2 4 7.4 7.4 图的连通性问题图的连通性问题 数据结构数据结构 应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程 38 数据结构数据结构 路径路径：在图在图 G(V, E) 中中, 若从顶点若从顶点 vi 出发出发, 沿一些边经过一些沿一些边经过一些顶点顶点 vp1, vp2, , v vpmpm，到达顶点，到达顶点vj。则称顶点序列。则称顶点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点为从顶点vi 到顶点到顶点 vj 的路
7、径的路径。它经过的边。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应是属于应是属于E的边。的边。 带权图的路径长度：带权图的路径长度：是指路径上各边的权之和。是指路径上各边的权之和。 最短路径：最短路径：从图中某一顶点从图中某一顶点u(称为源点称为源点)到达另一顶点到达另一顶点v(称为终称为终点点)的路径中路径长度最短的一条路径称为顶点的路径中路径长度最短的一条路径称为顶点u到顶点到顶点v的最短的最短路径。路径。 最短路径问题的应用最短路径问题的应用： 计算机交通咨询计算机交通咨询 互连网中的路由算法互连网中的路由算法 7.6 7.6 最短路径最短路径 39 数据
8、结构数据结构 V1 V3 V2 V5 V4 6060 100100 V0 2020 3030 1010 5050 1010 5 5 源点源点 源点源点 终点终点 最短路径最短路径 路径长度路径长度 V0 V1 无无 V2 （V0,V2） 10 V3 （V0,V4,V3） 50 V4 （V0,V4） 30 V5 （V0,V4,V3,V5） 60 10 30 100 5 50 10 20 60 0 1 2 3 4 5 0 1 2 3 4 5 7.6.1 单源最短路径问题：单源最短路径问题： 给定带权有向图给定带权有向图G和源和源点点v，求从源点，求从源点v到到G中其余中其余各顶点的最短路径。各顶点
9、的最短路径。 40 7.6 7.6 最短路径最短路径 数据结构数据结构 Dijkstra 算法求单源最短路径：算法求单源最短路径： 设设 V 是该有向图的顶点的集合，是该有向图的顶点的集合， S 是已求得最短路径的顶点的集是已求得最短路径的顶点的集合。引进一个辅助数组合。引进一个辅助数组D，Di表示当前所找到的从表示当前所找到的从v0 至其余各顶点至其余各顶点vi的最短路径长度。的最短路径长度。 S = v0 ； /初始时初始时S中只有中只有顶点顶点v0 for ( i=1; in; i+ ) Di = Edge0i；/ v0至至vi的边长的边长 for ( i=1; in; i+ ) 选择顶
10、点选择顶点vj，满足条件，满足条件 Dj = Min Di | vi V-S ； S = S + vj； /将将vj 加入集合加入集合 S for ( 每一个顶点每一个顶点vk V-S ) Dk = Min( Dk, Dj + Edgejk ) ; / 注：顶点注：顶点v0到顶点到顶点vk的最短路径或者是弧的最短路径或者是弧(v0,vk)，或者是或者是 / (v0,vp1.vpm,vk)，其中，其中vp1.vpm S。 41 7.6 7.6 最短路径最短路径 数据结构数据结构 V1 V3 V2 V5 V4 6060 100100 V0 2020 3030 1010 5050 1010 5 5
11、终点终点i=1i=2i=3i=4i=5v1v210 (v0,v2)v3v430 (v0,v4)v5100 (v0,v5)vjSStep0：初始化，初始化，Dk为源点为源点V0到到 Vk的边长。的边长。 42 7.6 7.6 最短路径最短路径 数据结构数据结构 V1 V3 V2 V5 V4 6060 100100 V0 2020 3030 1010 5050 1010 5 5 终点终点i=1i=2i=3i=4i=5v1v210 (v0,v2)v3v430 (v0,v4)v5100 (v0,v5)vjV2Sv0,v2Step1：选择当前的最短路径选择当前的最短路径(v0,v2)， 将将v2加入加入
12、S。 43 7.6 7.6 最短路径最短路径 数据结构数据结构 V1 V3 V2 V5 V4 6060 100100 V0 2020 3030 1010 5050 1010 5 5 终点终点i=1i=2i=3i=4i=5v1v210 (v0,v2)v360 (v0,v2,v3)v430 (v0,v4)30 (v0,v4)v5100 (v0,v5)100 (v0,v5)vjV2Sv0,v2Step2：更新从更新从v0到到v1、v3、v4、v5 的最短路径。的最短路径。 44 7.6 7.6 最短路径最短路径 数据结构数据结构 V1 V3 V2 V5 V4 6060 100100 V0 2020
13、3030 1010 5050 1010 5 5 终点终点i=1i=2i=3i=4i=5v1v210 (v0,v2)v360 (v0,v2,v3)v430 (v0,v4)30 (v0,v4)v5100 (v0,v5)100 (v0,v5)vjV2V4Sv0,v2v0,v2,v4Step3：选择当前的最短路径选择当前的最短路径(v0,v4)， 将将v4加入加入S。 45 7.6 7.6 最短路径最短路径 数据结构数据结构 V1 V3 V2 V5 V4 6060 100100 V0 2020 3030 1010 5050 1010 5 5 终点终点i=1i=2i=3i=4i=5v1v210 (v0,
14、v2)v360 (v0,v2,v3)50 (v0,v4,v3)v430 (v0,v4)30 (v0,v4)v5100 (v0,v5)100 (v0,v5)90 (v0,v4,v5)vjV2V4Sv0,v2v0,v2,v4Step4：更新从更新从v0到到v1、v3、v5的最的最 短路径短路径 46 7.6 7.6 最短路径最短路径 数据结构数据结构 V1 V3 V2 V5 V4 6060 100100 V0 2020 3030 1010 5050 1010 5 5 终点终点i=1i=2i=3i=4i=5v1v210 (v0,v2)v360 (v0,v2,v3)50 (v0,v4,v3)v430 (v0,v4)30 (v0,v4)v5100 (v0,v5)100 (v0,v5)90 (v0,v4,v5)vjV2V4V3Sv0,v2v0,v2,v4v0,v2,v3, v4Step5：选择当前的最短路径选择当前的最短路径(v0,v4,v3)， 将将v3加入加入S。 47 7.6 7.6 最短路径最短路径 数据结构数据结构 V1 V3 V2 V5 V4 6060 100100 V0 2020 3030 1010 5050 1010 5 5 终点终点i=1i=2i=3i=4i=5v1v210
