数据结构(长安大学)讲课PPT6

1、数据结构教师教师：杨云 班级班级：24020803/04 学院学院：长安大学信息工程学院 地址地址：WM1506 Email：数据结构 -学习数据结构的方法逻辑结构运算定义存储结构实现运算分析 第七章 图7.1 图的定义和基本概念7.2 图的存储结构 7.2.1 数组表示法 7.2.2 邻接表 7.2.3 十字链表 7.2.4 邻接多重表7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索7.4 图的连通性 7.4.1 无向图的连通分量和生成树 7.4.2 最小生成树7.5 有向五环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径7.6 最短路径 7.6.1 从某个源点到

2、其余各顶点的最短路径 7.6.2 每一对顶点之间的最短路径 7 图 图是另一种非线性结构，它比树更复杂、更一般化，因此可以把树看成是简单的图。 图的应用范围极广，近年来已经渗入到各个领域，如语言学、逻辑学、数学、物理、化学、计算机科学和各种工程学领域。 比树的结构更加复杂 没有严格的层次 结点之间的关系是任意的 回忆：离散数学中关于图的概念7.1 图的定义和基本术语基本概念：什么是图无向图、边、度有向图、弧、出度和入度邻接结点、邻接边路径、连通性、连通分支生成树特殊图：完全图、稀疏图、带权图一、图的定义一、图的定义图图:由顶点集V和连接顶点的边（弧）集E所组成的结构，记作G=(V,E)； V是

3、顶点(元素)的有穷非空集， E是两个顶点之间的关系的集合。12343124V=1,2,3,4E=,V=1,2,3,4E=(1,2),(1,3),(2,4),(1,4),(3,4) 图的数据对象：图的顶点集合 图的数据关系：图中各顶点之间的关系，就是边（或称作弧） 注意：上述关系是非线性的，多对多的关系，即前驱/后继关系都不是唯一的！ 图中的数据元素具有相同特性，称为顶点； 若顶点a,c之间的关系为有序对有序对,且E 则称为从a到c的一条弧弧/有向边有向边； a是的弧尾弧尾， c是的弧头弧头； 此时的图G称为有向图有向图。 例 G1=V1,E1, V1=A,B,C,D,E E1=, 二、基本概念

4、二、基本概念ABCEDG1 图中若顶点之间的关系有则必，即为无序对（a,c）； 则无序对（a,c）表示a和c之间的一条边， 此时的图G称为无向图。 例 G2=V2,E2, V2=A,B,C,D ABCDE2=（A,B）,（A,C）,（A,D）,（B,D）G2 若无向图G中任意两点间都有一条边，则称此图G为无向完全图无向完全图。即n个顶点的无向完全图有n(n-1)/2条边；v1Av2Cv3G1 G2 G3 G4 G5 Bv1v1v2DACBDEe=1(1-1)/2 =0e=2(2-1)/2 =1e=3(3-1)/2 =3e=4(4-1)/2 =6e=5(5-1)/2 =10 若有向图G中任意一个

5、顶点到其余各点间均有一条弧，则称G为有向完全图有向完全图。即n个顶点的有向完全图有n(n-1)条弧；123G1 G2 G3112e=1(1-1) =0e=2(2-1) =2e=3(3-1) =6 图的边或弧具有与其相关的数值，这个数值称为权(weight) 。 网(Network)-边(弧)上加权的图。123无向网G14ABC41559943有向网G2 有很少的边或弧的图称为稀疏图； 反之称为稠密图。若一个图G1=(V1，E1)是从G中选取部分顶点和部分边（或弧）组成，即V1V，E1E，则称G1是G的子图子图。123G412G1341G2341G4123G34G1,G2,G3是G的子图 G4不

6、是G的子图2相邻相邻：若无向图中（i，j）E i，j相邻，若有向图中 E i，j相邻； i与j互为邻接点，或者称i与j相关联。123456度度与顶点x相关联的边(x,y)的数目,称为x的度度，记作TD(x) 或D(x)；25413G1 TD(1)=1 TD(2)=3 TD(3)=0出度出度以顶点x为弧尾的弧的数目,称为x的出出度度，记作OD(x)。入度入度以顶点x为弧头的弧的数目, 称为x的入度入度，记作ID(x)。ABCG2OD(A)=1OD(B)=2OD(C)=0ID(A)=1 ID(B)=1ID(C)=1TD(A)=OD(A)+ID(A)=2 TD(B)=OD(B)+ID(B)=3TD(

7、C)=OD(C)+ID(C)=1注意： 无向图：度 有向图：入度，出度。 有向图中某结点的度入度出度。路径路径：图中从顶点x到达顶点y的顶点序列称为路径；有向图中路径也是有向的，路径上的边或弧的数目称为路径的长度； （1）序列中顶点无重复出现简单路径； （2）若首尾顶点相同回路； （3）若首尾相同且序列中间顶点无重复出现简单回路 ；12341234 对无向图G： 若从顶点vi到vj有路径,则称vi和vj是连通连通的。 若图G中任意两顶点是连通的,则称G是连通图连通图。123456GAFECBGDAFECBG1DG2G3 连通分量连通分量- -是无向图中的是无向图中的极大连通子图极大连通子图。G

8、GG有三个连通分量有三个连通分量否则不连通不连通，就存在若干连通分量连通分量。如：G为连通图，而G为非连通图。 对有向图G 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从vj 到vi都存在路径,则称G是强连通图强连通图。 若图G是G的一个极大强连通子图极大强连通子图,则称G是G的一个 强连通分量强连通分量。BCG1ADBC G11 是是G1的强连通分量强连通分量ADBC G12不是不是G1的强连通分量强连通分量ADBCG2ADBCG21ADG22G2有两个强连通分量有两个强连通分量 设G=(V,E),G=(V,E),V=V,若G是连通图, G是G的一个极小连通子图极小连通子图, ,

9、则G是G的一棵生成树生成树。 注：生成树包含图中全部顶点，但只有足以构成一颗树的n-1条边。EDGBCAEDT1BCAEDT4BCAEDT3BCAEDT2BCAG的多棵生成树 若有向图G有且仅有一个顶点的入度为0，其余顶点的入度为1,则G是一棵有向树有向树。 注意：一个有向图的有向森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。EDT1BCAEDT2BCAEBT3ACEEDT4BCAEDT5BCAEDT6BCAT1,T2,T3,T4是有向树有向树T5,T6不是有向树有向树 有向图的生成树/生成森林。EDGBCAEBFADFFC三、图的基本操作（1） Creat

10、eGraph(&G, V, VR); DestroyGraph(&G); LocateVex(G, u); GetVex(G, v); PutVex(&G, v, value); FirstAdjVex(G, v); NextAdjVex(G, v, w);图的基本操作（2） InsertVex(&G, v); DeleteVex(&G, v); InsertArc(&G, v, w); DeleteArc(&G, v, w); DFSTraverse(G, v, Visit(); BFSTraverse(G, v, Visit();图的

11、存储结构考虑 比树更加复杂的非线性结构 无法直接用顺序结构表示结点之间的关系（但是可以间接表示） 自然的链式结构：需要一个良好的链式结构7.2 图的存储结构一、 数组表示法/邻接矩阵顶点数组顶点数组-用一维数组存储顶点(元素)邻接矩阵邻接矩阵-用二维数组存储顶点(元素)之间的关系(边或弧) 143G2 1 2 3 41 0 0 1 12 0 0 0 03 1 0 0 14 1 0 1 0 M=例1邻接矩阵邻接矩阵 1 2 3 41 2 3 4顶点数组顶点数组V1.41.1 1.1 邻接矩阵邻接矩阵1、不带权值设图中有n个顶点：Ann aij 1 E 0或 否则对称123411110110111

12、10000非0元素个数12341 2 3 444不对称12341110000010100000第i非0元素个数=对应顶点的度第i非0元素个数=对应顶点的度12341 2 3 4442、带权值 aij Vij E 0或 否则123453650230462400002536412341 2 3 4441.2 图的数组表示法数据结构定义/图的类型和弧的定义#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最大顶点数typedef enum DG, DN, AG, AN GraphKind;/有向图，有向网，无向图，无向网typedef s

13、truct ArcCellVRType adj; /顶点关系，无权图0或1，带权图为权InfoType *info; /该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/图的数组定义typedef structVertexType vexsMAX_VERTEX_NUM; /顶点向量AdjMatrix arcs; /邻接矩阵int vexnum, arcnum; /图的当前顶点数和弧数GraphKind kind; /图的种类标志MGraph;图的数组表示的应用 邻接矩阵中的含义 无向图与对称性 顶点的度 权 建立在邻接矩阵上的算法举

14、例： P162的算法7.1和算法7.2，用于构造图和构造无向网二、邻接表二、邻接表12341234data firstadj逆邻接表：1234data firstadj图的邻接表存储数据结构定义#define MAX_VERTEX_NUM 20 typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针InfoType *info; /该弧相关信息的指针ArcNode;typedef struct VNodeVertexType data; /顶点信息ArcNode *firstarc; /

15、指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum; /图的当前顶点数和弧数int kind; /图的种类标志ALGraph;有向图的十字链表十字链表- 将邻接表和逆邻接表合并而成的链接表。 CBADABCD 1 2 3 41 GG的逆逆邻接表邻接表134 ABCD 1 2 3 44 3 G的邻接表邻接表2 2ABCD1234G的十字链表十字链表3 21 24 2 14 4 3 24 4 1 1 4 三、有向图的十字链表三、有向图的十字链表四、 无向图的邻接多

16、重表邻接多重表-另一种链式存储结构EDFBACGABCDEF012023013024034056序号序号 data firstedgedata firstedge(A,B)(A,C)(B,C)(B,D)(C,D)(E,F)隐含的链接表：隐含的链接表： A (1,2) (1,3) B (1,2) (2,3) (2,4) C (1,3) (2,3) (3,4) D (2,4) (3,4) E (5,6) F (5,6)ma vi vj vil vjlma vi vj vil vjl123456 图的一条边或弧用一个“头结点头结点”表示，其中： markmark-标志域，可用以标记该条边是否被搜索过

17、； vivi和和vjvj-该条边依附的两个顶点在图中的位置； vilvilinkink-指向下一条依附于顶点vi的边； vjlvjlinkink-指向下一条依附于顶点vj的边。 0 1 2mark vi vj vilink vjlinkmark vi vj vilink vjlinkdata firstedgedata firstedgeA表示顶点A的头结点头结点表示边或弧(v1,v2)的表表结点结点 图的一个顶点用一个“头结点头结点”表示，其中： datadata域域存储和该顶点相关的信息， firstedgefirstedge域域存储第一条依附于该顶点的边。表表结点结点7.3 图的遍历一、

18、定义：从图的某顶点出发，访问图中每个顶点一次且仅一次。 图的遍历算法：l深度优先搜索（ Depth-First Search ）DFSl广度优先搜索（ Breadth-First Search ）BFS一、深度优先搜索遍历（一、深度优先搜索遍历（dfsdfs） DFS（Depth-First Search）算法是图论中最重要的算法之一，它的思路可以用来表述。下图是1690年独裁者威廉王修筑的迷宫示意图，现遗址在奥地利。xbdefclghijak迷宫法则 任务是从事先未知结构的迷宫入口出发，每个走廊都要搜索，再从入口退出。为了不兜圈子尽快退出，要记住哪些走廊已经走过，沿着未走过的走廊尽可能地走下

19、去，走到已无未走过的走廊可走时，沿来路返回，到某一路口，发现可通往一条未走过的走廊时，沿此走廊搜索，依次类推，直至完成任务。迷宫法则一直往前走碰壁就回头换条路走沿途要记录走过的路线老鼠走迷宫dfs1、基本遍历算法的描述： 1973年，用上述迷宫思想，Hopcroft和Tarjan设计了下面有效的DFS算法。 dfs(v0)从v0出发深度遍历1、访问v0visit(v0)；2、依次从v0未被访问未被访问的邻接点出发深度遍历。深度优先搜索过程：v0v1v3v5v4v2v6v7搜索回溯dfs(v0)v0v1v3v5v4v2v7v6序列：序列：v0- v1 -v3- v5 -v4- v2 v6- v7

20、dfs(v1)dfs(v3)dfs(v5)dfs(v4)dfs(v6)dfs(v7)dfs(v2)DFS生成树搜索过程形成DFS生成树，如下图：v0v1v3v5v4v2v7v62、DFS算法的实现： dfs(v0)从v0出发深度遍历1、访问v0visit(v0)；2、依次从v0未被访问未被访问的邻接点出发深度遍历。 未被访问：visitedi=1（访问）/0（未访问）； 求邻接点：firstadj，nextadj； nodes(G)返回图G的结点数。 求邻接点： firstadj(i)返回顶点i的第一个邻接点，找不到返回0；如：w=firstadj(1);/w2; nextadj(i,j)返回

21、顶点i位于结点j后的邻接点，找不到返回0；如：w=nextadj(1,2);/w=3;1234基于以上讨论，得dfs算法如下：void dfs(Graph G,int v0) visit(v0); visitedv0=ture; w=firstadj(G, v0); while(w!=0) if(visitedw=false) dfs(G,w); w=nextadj(G,v0,w); 123458679遍历整个图的算法如下：void dfs-travel(Graph G) for (i=1;i=nodes(G);i+) visiedi=false; for (i=1;i=nodes(G);i+

22、) if(visitedi=false) dfs(G,i);1234586793、DFS算法的应用：1、设计算法判断图G是否连通。2、设计算法求图G的连通分量数。思考题：设计算法求图G的dfs生成树；相邻数相加质数问题；求路径问题； 可以看出，用dfs对迷宫进行搜索，可以找出穿过迷宫的路，但是不一定是最短的。如果要找出最短的，则对迷宫进行bfs搜索。二、广度优先搜索（BFS） BFS（Breadth-First Search）算法的描述bfs(v0)从v0出发广度遍历1、访问v0visit(v0)；2、依次访问v0的邻接点；3、假设最近一层访问的结点次序为vk1，vk2，vkm，依次访问vk1

23、，vk2，vkm的邻接点；广度优先搜索过程：v0v1v3v5v4v2v6v7bfs(v0)v0v1v3v5v4v2v7v6序列：序列：v0-v1-v2-v3-v4- v6- v7-v5搜索BFS生成树搜索过程形成BFS生成树，如下图：v0v1v3v5v4v2v7v6BFS算法的一个显著特点是：层次性。所以可以用来求两点间最短路径。01入口出口0117.4 图的连通性 深度优先遍历（DFS)生成树 广度优先遍历（BFS）生成树 DFS生成森林 BFS生成森林一、DFS生成树：假定从A A出发DFSDFS遍历图G：FDBCAGHEI图GABABABADCDFDBCAFDBCAIFDBCAIGDFS

24、生成树T1FDBCAGHEI图GFDBCAIGHFDBCAIGHEFDBCAIGHEDFS生成树T2ECBDAIGFH二、 BFSBFS生成树生成树FDBCAGHEI图G假定从A A出发BFSBFS遍历图G：AABABFABEFABEFCABEFCDABEFCDIFDBCAGHEI图GABEFCDIHGABEFCDIHABEFCDIHGABEFCDIHGBFS生成树T1BFS生成树T2三、 DFSDFS生成森林生成森林CKIJADEBFGH从A A出发，得树T1：T2CADEBF图GT3T1从G G出发,得树T2：CADEBFT1GHT2CADEBFT1GHKIJ从I I出发,得树T3：四、

25、BFSBFS生成森林生成森林CKIJADEBFGH从A A出发，得树T1：T2图GT3T1从G G出发,得树T2：AT1GHT2T1GHKIJ从I I出发,得树T3：CDEBFACDEBFACDEBF7.5 有向无环图及其应用 最小生成树 拓扑排序 最短路径 关键路径一、 最小生成树最小生成树 假设在n个城市之间建立一个通信网络，最少需要n-1条边（最多为n(n-1)/2）。 边上赋予相应的代价。 可以有多棵生成树，那么选择一棵代价最小的生成树！ 要在 n 个小区间建立能源网，现在要考虑的问题如何在保证 n 个小区连通的前提下最节省经费?上述问题即要使得生成树各边权值之和，即：)(),()(T

26、EvuuvwTW12354435323136 问题描述： 在有n个顶点的带权连通图G中，选取条边以构成一棵树，要求所选边权值之和最小。这样的树称为图G的。最小生成树的性质 假设N=（V，E）是一个连通网，U是V的一个非空子集。若（u,v）是一条具有最小权值的边，那么必存在一棵包含边（u,v）的最小生成树，其中u是U中的一个顶点，v是V-U中的一个顶点。( (一一)prim)prim算法算法( (普里姆普里姆) )1、基本思想： 在满足如下条件选择权值最小权值最小的边一端已入选，另一端未入选。 N=（V，E），TE是N上最小生成树的边的集合。（1）初始化：U=u0, TE=；（2）在所有uU,

27、vV-U的边（u,v）E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U；（3）重复（2），直至U=V。2、求解实例求下图的最小生成树：123541235443532313612354最小生成树不唯一，但权值之和相同。 例：求例：求G G的最小生成树的最小生成树 CADEBF图G3718745561.普里姆普里姆( (prim)prim)算法 以选顶点为主以选顶点为主DTCD5TCAD15CADB3156CADEB3156TTT图G的最小生成树 CADEBF图G3718745561.普里姆普里姆( (prim)prim)算法 以选顶点为主以选顶点为主6CADEB3156TF4另一

28、最小生成树CADEBF图G3718745561.普里姆普里姆( (prim)prim)算法 以选顶点为主以选顶点为主DTDT6TTTB5ADB35ADB35C1ADB35C1E6另一最小生成树 CADEBF图G3718745561.普里姆普里姆( (prim)prim)算法 以选顶点为主以选顶点为主6CADEB316TF45Prim算法的关键 按照最小生成树的性质进行顶点扩张。 每扩展一个顶点，在两个顶点集合中都要更新当前的最小边。 以邻接矩阵为存储结构，时间复杂度为O（n2），与边数无关！( (二二)Kruskal)Kruskal算法算法( (克鲁斯卡尔克鲁斯卡尔) )1、基本思想： 在满足

29、如下条件选择权值最小权值最小的边和已选边不构成回路。 N=（V，E），TE是N上最小生成树的边的集合。（1）初始化：T=（V，），即TE=；（2）在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到TE中，否则选择下一条代价最小的边；（3）重复（2），直至所有顶点都在同一连通分量上为止。2、求解实例求下图的最小生成树：1235443532313612354最小生成树不唯一，但权值之和相同。克鲁斯卡尔（克鲁斯卡尔（KruskaiKruskai) )算法，以选边为主以选边为主CADEBF图G371874556TT6TTTCACAB113CAB13EF4CAB13EF4D

30、5CADEBF31456克鲁斯卡尔（克鲁斯卡尔（KruskaiKruskai) )算法，以选边为主以选边为主CADEBF图G371874556TT6TTTCACAB113CAB13EF4CAB13EF4DCADEBF314655删除权最大的边，保留删除权最大的边，保留n-1n-1条条CADEBF图G3718745566CADEBF371745566CADEBF37145566图G图GCADEBF图G3718745566删除权最大的边，保留删除权最大的边，保留n-1n-1条条CADEBF图G3718745566CADEBF314556TCADEBF31456图GCADEBF3145566图GKr

31、uskal算法的特征 按照最小生成树的性质进行边的扩展 每扩展一条边，都需要判断有无形成回路 以邻接矩阵为存储结构时，时间复杂度可以达到O（eloge)，与顶点数无关！二、 拓扑排序拓扑排序拓扑排序 偏序关系的一个序列 拓扑排序的应用：选课次序 工程施工流程图：AOV网（一）问题描述：（一）问题描述：由多项子工程（活动）组成，子工程（活动）之间存在制约关系。用图表示工程，顶点表示子工程（活动），弧表示活动间的制约关系。(1)工程是否能顺利完成？ 图中是否存在回路？(2)工程需要多少时间完成？(3)哪些是关键性工程？（二）拓扑排序方法及实现（二）拓扑排序方法及实现(AOV(AOV网网) )1、如

32、何判断AOV网中是否存在有向回路？解决方法：(1)用深度遍历要做许多试探性工作；(2)用产生顶点序列的方法拓扑排序；如果能产生包含的拓扑序列则说明AOV网中无回路，否则有回路。2、拓扑排序步骤： (1)选择一个没有前驱的顶点(入度为0)的顶点v；(2)此顶点排序后即删除之，并删除所有以它为尾的弧（将此弧的头的顶点的入度减1）；(3)重复(1)、(2)，直到重复上述过程，直至所有顶点都被排序(找不到入度为0的顶点)为止。123456求下图的拓扑序列：3、求解实例12345653124563465123456312345612354624565123456465312345612345664512345646245653123456123456三、 最短路径问题引入：问题引入： 两类问题：(1)从单点到其余顶点的最短路径；(2)各点间的最短路径。123456