《数据结构课件、代码》第5章图.ppt

《《数据结构课件、代码》第5章图.ppt》由会员分享，可在线阅读，更多相关《《数据结构课件、代码》第5章图.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章 图张成文张成文北京邮电大学计算机学院北京邮电大学计算机学院数据结构-第5章 图25.1 图的基本概念图的基本概念 非线性结构，数据元素之间呈多对多的关系。5.1.1 图的定义图的定义Graph=(V,VR)V：顶点(数据元素)的有穷非空集合。VR：弧(关系)的有穷集合。数据结构-第5章 图3例例1 1：G G1 1=(V=(V1 1,VR,VR1 1)V1=A,B,C,D,EVR1=,EACBD例例2 2：G G2 2=(V=(V2 2,VR,VR2 2)V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)BCAFED数

2、据结构-第5章 图45.1.2 图的相关术语图的相关术语顶点顶点 数据元素所构成的结点。有向图有向图 弧的顶点偶对是有序的。对弧而言，vi是弧尾弧尾/初始点；vj是弧头弧头/终端点。无向图无向图 弧的顶点偶对是无序的。(vi,vj)和(vj,vi)代表同一条边边(ij)。(无向无向)完全图完全图 每个顶点与其余顶点都有边的无向图。顶点数为n时，边数 e=n(n-1)/2有向完全图有向完全图 每个顶点与其余顶点都有弧的有向图。顶点数为n时，弧数 e=n(n-1)稀疏图稀疏图 有很少边或弧的图。（enlogn）稠密图稠密图 有较多边或弧的图。vi vjvi vj数据结构-第5章 图5权权 图中的边

3、或弧具有一定的大小的概念。网网 边/弧带权的图。邻接邻接 有边/弧相连的两个顶点两个顶点之间的关系。存在(vi,vj)，则称vi和vj互为邻接点邻接点；存在，则称vi邻接到邻接到vj，vj邻接于邻接于vi 关联关联(依附依附)边边/弧与顶点弧与顶点之间的关系。存在(vi,vj)/，则称该边/弧关联于vi和vj顶点的度顶点的度 与该顶点相关联的边的数目，记为D(v)。入度入度ID(v)：有向图中，以该顶点为弧头的弧数目。出度出度OD(v)：有向图中，以该顶点为弧尾的弧数目。vivjvivjABECF1597211132数据结构-第5章 图6路径路径 接续的边构成的顶点序列。路径长度路径长度 路径

4、上边或弧的数目/权值之和。回路回路(环环)第一个顶点和最后一个顶点相同的路径。简单路径简单路径 序列中顶点均不相同的路径。简单回路简单回路(简单环简单环)除路径起点和终点相同外，其余顶 点均不相同的路径。从从A A到到F F长度为长度为3 3的路径的路径 A,B,C,FA,B,C,FABECF数据结构-第5章 图7连通图连通图 无向图中，任何一对顶点间都存在路径。连通分量连通分量 无向图中的极大连通子图。强连通图强连通图 有向图中，任何一对顶点间都存在路径。强连通分量强连通分量 有向图中的极大连通子图。数据结构-第5章 图8生成有向树生成森林子图子图 对于图G=(V,E)和G=(V,E)，如果

5、V V，E E，且E关联的顶点都在V中，则称G是G的子图。生成子图生成子图 由图的全部顶点全部顶点和部分边部分边组成的子图称为原图的生成子图。生成树生成树 包含图中全部顶点全部顶点的极小极小连通子图。有向树有向树 图中恰有一个顶点入度为0，其余顶点入度均为1。生成森林生成森林 有向图中，包含所有顶点的若干棵有向树构成的子图。e=n-1数据结构-第5章 图95.2 图的存储结构图的存储结构5.2.1 数组数组/邻接矩阵邻接矩阵 表示法表示法(顺序存储方式顺序存储方式)例例1 无向图无向图 顶点数组vexs 邻接矩阵(边表)arcs 0 A 0 1 1 0 1 B 1 0 1 1 2 C 1 1

6、0 1 3 D 0 1 1 0 0 A B 1 2 C D 3 G1无向图的邻接矩阵具有对称性例例2 有向网有向网顶点数组vexs 邻接矩阵(边表)arcs 0 A 0 3 2 1 B 0 4 2 C 5 0 3 D 2 032 5 42G20 A B 12 C D 3数据结构-第5章 图105.2.2 邻接表邻接表 顺序存储+链式存储 顶点顺序表顶点顺序表 邻接顶点的单链表邻接顶点的单链表(边表边表)G1:0 A 1 2 1 B 0 2 3 2 C 0 1 3 3 D 1 2 G2:0 A 1 3 2 2 1 B 3 4 2 C 1 5 3 D 2 2 出边表出边表(逆邻接表时用入边表入边表

7、)nextarcadjvexnextarcweightadjvex无向图有向网0 AB 12 CD 30 AB 12 CD 332 5 42datafirstarcvertices数据结构-第5章 图115.3 图的遍历图的遍历深度优先遍历(树的先根遍历的推广)广度优先遍历(树的按层次遍历的推广)例例v1v2v3v4v5v6v7v8深度：v1 v2 v4 v8 v5 v6 v3 v7广度：v1 v2 v3 v4 v5 v6 v7 v8设从v1出发遍历数据结构：主图的存储结构 辅数组 visited0.n-1数据结构-第5章 图125.3.1 深度优先搜索深度优先搜索递归的算法思想递归的算法思想

8、 (1)访问顶点v，并记录v已被访问 (2)依次从v的未访问的邻接点出发，深度优先搜索图G。算法描述算法描述typedef enumFALSE,TRUE Boolean;/FALSE为0，TRUE为1Boolean visitedMAX_VERTEX_NUM;/辅助访问标志向量void DFSTraverse(Graph G)for(v=0;vG.vexnum;+v)visitedv=FALSE;/标志向量初始化 for(v=0;v-1;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/DFSvoid DFS(MGraph G,int v)/深度优先遍历邻接矩

9、阵邻接矩阵表示的图 visit(G.vexsv);visitedv=TRUE;for(j=0;jadjvex)DFS(G,p-adjvex);p=p-nextarc;/DFS例数据结构-第5章 图14abchdekfg812345670F F F F F F F F F0 1 2 3 4 5 6 7 8T T T T T T T T Tach d kfe bgachkfedbg访问标志访问标志:访问次序访问次序:例例achdkfe数据结构-第5章 图155.3.2 广度广度(宽度宽度)优先遍历优先遍历算法思想算法思想 (1)访问顶点v，并记录它已被访问；顶点v入队列；(2)如果队列空，则退出；

10、否则，从队中取出一顶点；(3)求该顶点的一个邻接点；如果此邻接点未被访问，则访问它，并记录它已被访问，将其入队列；(4)如果该顶点还有下一个邻接点，则转(3)；否则，转(2)123456 数据结构-第5章 图16算法描述算法描述void BFSTraverse(Graph G)for(v=0;vG.vexnum;+v)visitedv=FALSE;/标志向量初始化 InitQueue(Q);/辅助队列初始化 for(v=0;v-1;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;visit(w);EnQueue(Q,w);/BFSTraverse数据

11、结构-第5章 图17算法时间复杂度分析算法时间复杂度分析 与深度优先遍历过程相同 5.3.3 图的遍历小结图的遍历小结深度优先遍历算法借助于栈结构实现；广度优先遍历算法借助于队列结构实现图的遍历序列与算法和存储方式有关数据结构-第5章 图185.3.4 图的遍历应用举例图的遍历应用举例 例例11 求一条从顶点求一条从顶点 i i 到顶点到顶点 s s 的简单路径的简单路径abchdekfgb b -k k 从b b出发深度优先搜索遍历：假设找到的第一个邻接点是a,a,且且得到的结点访问序列为:b b a d h c e k k f g假设找到的第一个邻接点是c,c,则得到的结点访问序列为:b

12、c h d a e k f g结论结论:1.从顶点 i 到顶点 s,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点 s。2.遍历过程中搜索到的顶点不一定是路径上的顶点。3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。数据结构-第5章 图19 例例22 求两个顶点之间的一条路径长度最短的路径求两个顶点之间的一条路径长度最短的路径因此，求路径长度最短的路径可以基于广度优先搜求路径长度最短的路径可以基于广度优先搜索遍历进行索遍历进行，但需要修改链队列的结点结构及其入修改链队列的结点结构及其入队列和出队列的算法队列和出队列的算法。abchdekfg深度优先搜索访问顶点的次序次序取决于图的存储结构存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。数据结构-第5章 图20求右图中顶点 3 至顶点 5 的一条最短路径。链队列的状态如下所示链队列的状态如下所示:Q.front 3 1 2 4 7 5 321475689Q.rear