《数据结构》-《数据结构》(c语言版)第七章_图

第七章 图,7.1 图的定义和术语,7.2 图的存储结构,7.3 图的遍历,7.4 图的连通性问题,7.5 有向无环图及其应用,7.6 最短路径,学习提要：1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。2. 熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。3. 应用图的遍历算法求解各种简单路径问题。4. 理解教科书中讨论的各种图的算法。重难点内容：图的两种遍历方法和算法、生成树的构造、拓扑排序、AOE网、最短路径,图的抽象数据类型定义: ADT Graph 数据对象V：V是具有相同特性的数据元素的 集合，称为顶点集。 数据关系R：RVR VR| v,wV且P(v,w)， 表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 。 ADT Graph, 7.1 图的定义和术语,基本操作P：,图(Graph)：是由一个顶点集 V 和一个弧集 R构成的数据结构。记为： G = ( V , R ) 其中，R=VR VR| v,wV 且 P(v,w) 表示从 v 到 w 的一条弧，并称 v 为弧尾，w 为弧头。,图的名词和术语:,AB E C D,有向图：由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。,例如:,G1 = ( V1, VR1 ),V1=A, B, C, D, EVR1=, , , , , , ,若VR必有VR, 则称 (v,w) 为顶点v 和顶点w 之间存在一条边。,B CA D F E,无向图：由顶点集和边集构成的图。,例如: G2=( V2,VR2 )V2=A, B, C, D, E, FVR2=, , , , , , ,假设图中有n个顶点，e条边，则,完全图：含有n(n-1)/2 条边的无 向图。,有向完全图：含有n(n-1) 条弧的 有向图。,若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。,15,9,7,21,11,2,有向网：带权的有向图。无向网：带权的无向图。,3,B,子图：设图G=(V,VR) 和 G=(V,VR)，且 VV, VRVR， 则称 G 为 G 的子图。,假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点，,例如:,TD(B) = 3,TD(A) = 2,边(v,w) 和顶点v 和w 相关联。,顶点的度：和顶点v 关联的边的数目， 记为TD(v)。,顶点的出度: 以顶点v为弧尾的弧的数目。,对有向图来说，,顶点的入度: 以顶点v为弧头的弧的数目。,顶点的度(TD)=出度(OD)+入度(ID),例如:,ID(B) = 2,OD(B) = 1,TD(B) = 3,设图G=(V,VR)中的一个顶点序列(u=vi,0,vi,1, , vi,m=w)，其中(vi,j-1,vi,j)VR, 1jm,则称从顶点u 到顶点w 之间存在一条路径。路径上边的数目称作路径长度。,如:长度为3的路径A,B,C,F,简单路径:序列中顶点不重复出现的路径。,简单回路:序列中第一个顶点和最后一个顶点相同的路径。,在无向图G中，如果从顶点v到顶点v有一条路径，则说v和v是连通的；若图G中任意两个顶点之间都有路径相通，则称此图为连通图。,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。,对有向图，,否则，其各个强连通子图称作它的强连通分量。,假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。,结构的建立和销毁,插入或删除顶点,对邻接点的操作,对顶点的访问操作,遍历,插入和删除弧,基本操作：,CreatGraph(&G, V, VR): / 按定义(V, VR) 构造图,DestroyGraph(&G): / 销毁图,结构的建立和销毁,对顶点的访问操作,LocateVex(G, u); / 若G中存在顶点u，则返回该顶点在 / 图中“位置” ；否则返回其它信息。,GetVex(G, v); / 返回 v 的值。,PutVex( / 对 v 赋值value。,对邻接点的操作,FirstAdjVex(G, v); / 返回 v 的“第一个邻接点”。若该顶点 /在 G 中没有邻接点，则返回“空”。,NextAdjVex(G, v, w); / 返回 v 的(相对于 w 的)“下一个邻接点”。 / 若 w 是 v 的最后一个邻接点，则返回“空”。,插入或删除顶点,InsertVex( /在图G中增添新顶点v。,DeleteVex( / 删除G中顶点v及其相关的弧。,插入和删除弧,InsertArc( / 在G中增添弧，若G是无向的， /则还增添对称弧。,DeleteArc( /在G中删除弧，若G是无向的， /则还删除对称弧。,遍 历,DFSTraverse(G, v, Visit( ); /从顶点v起深度优先遍历图G，并对每 /个顶点调用函数Visit一次且仅一次。,BFSTraverse(G, v, Visit( ); /从顶点v起广度优先遍历图G，并对每 /个顶点调用函数Visit一次且仅一次。,7.2 图的存储结构,7.2.1 数组(邻接矩阵) 表示法,7.2.2 邻接表,7.2.3 十字链表,7.2.4 邻接多重表,多重链表:,两个数组：一个数组存储顶点的信息，一个存储顶点之间的关系（边或弧）的信息。邻接矩阵定义：设G=(V,VR)是有n1个顶点的图，G的邻接矩阵是具有以下性质的n阶方阵：,7.2.1 数组（邻接矩阵）表示法,特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2。 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n。 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行(或第i列)元素之和。 有向图中，顶点Vi的出度是A中第i行元素之和。顶点Vi的入度是A中第i列元素之和。,网络的邻接矩阵可定义为：,#define INFINITY INT_MAX / 最大值#define MAX_VERTEX_NUM 20 / 最大顶点个数typedef enum DG, DN, UDG, UDN GraphKind; /有向图,有向网,无向图, 无向网typedef struct ArcCell /弧的定义 VRType adj; / VRType是顶点关系类型。 /对无权图，用1或 0 表示相邻否； /对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;,typedef struct /图的定义 VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph;,Status CreateGraph(Mgraph /CreateGraph,Status CreateUDN(MGraph /CreateUDN,实现： 为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）。,7.2.2 邻接表,typedef struct ArcNode /弧的结点结构 int adjvex; / 该弧所指向的顶点的位置 Struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;,表结点：,adjvex nextarc info,邻接点域链域 数据域,typedef struct VNode /顶点的结点结构 VertexType data; / 顶点信息 ArcNode *firstarc;/ 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;,头结点：,typedef struct /图的结构定义 AdjList vertices; int vexnum, arcnum; int kind; ALGraph;,特点： 若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。 无向图中顶点Vi的度为第i个单链表中的结点数。 有向图中顶点Vi的出度为第i个单链表中的结点个数。顶点Vi的入度为整个单链表中邻接点域值是i的结点个数。逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。,7.2.3 十字链表,弧尾顶点位置 弧头顶点位置 弧的相关信息,typedef struct ArcBox / 弧的结构表示 int tailvex, headvex; struct ArcBox *hlink, *tlink; InfoType *info; ArcBox ;,指向下一个有相同弧尾的结点,指向下一个有相同弧头的结点,有向图,顶点信息数据,typedef struct VexNode VertexType data; ArcBox *firstin, *firstout; VexNode;,指向该顶点的第一条入弧,指向该顶点的第一条出弧,顶点的结构表示,typedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点(表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;,有向图的结构表示(十字链表),边结点：typedef struct Ebox VisitIf mark; /访问标记 int ivex, jvex; /该边依附的两个顶点的位置 struct EBox *ilink, *jlink; /分别指向依附 /这两个顶的下一条边 EBox;,7.2.4 邻接多重表,无向图,顶点结点：typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;,typedef struct / 无向图的邻接多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;,7.3 图的遍历,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,7.3.1 深度优先搜索,7.3.2 广度优先搜索,从图中某个顶点V 出发，访问此顶点，然后依次从V的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V有路径相通的顶点都被访问到。,连通图的深度优先搜索遍历,7.3.1 深度优先搜索(DFS)遍历图,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,V,w1,SG1,SG2,SG3,W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V ：for (W1、W2、W3 ) 若该邻接点W未被访问， 则从它出发进行深度优先搜索遍历。,w2,w3,w2,从上页的图解可见:,1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历；,解决的办法是：为每个顶点设立一个 “访问标志 visitedv”。,2. 如何判别V的邻接点是否被访问？,void DFS(Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS,深度遍历：V0,V2 ,V6 ,V5,V1,V4,V7 ,V3,true,true,true,true,true,true,true,true,首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,非连通图的深度优先搜索遍历,void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图 G 作深度优先遍历 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vw1, V-w2, V-w8 的路径长度为1；,V-w7, V-w3, V-w5 的路径长度为2；,V-w6, V-w4 的路径长度为3。,w1,V,w2,w7,w6,w3,w8,w5,w4,void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问 / BFSTraverse, ,visitedv = TRUE; Visit(v); / 访问vEnQueue(Q, v); / v入队列while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while,广度遍历：V0,V2 ,V1 ,V6,V5,V4,V3,V7,v0,v2,v1,v6,v5,v4,v3,v7,7.4 图的连通性问题,7.4.1 无向图的连通分量和生成树,7.4.3 最小生成树,图的生成树：图中的所有顶点加上遍历过程中经过的边所构成的子图。,7.4.1 无向图的连通分量和生成树,深度优先生成树 广度优先生成树,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,问题提出：,假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？,7.4.3 最小生成树,构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,克鲁斯卡尔算法,该问题等价于：,普里姆算法,取图中任意一个顶点u作为生成树的根，之后往生成树上添加新的v。在添加的顶点 v和已经在生成树上的顶点u 之间必定存在一条边，并且该边的权值在u相关联的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。,普里姆算法的基本思想:,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,普里姆算法实现:,a,b,c,d,e,g,f,例如:,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,所得生成树权值和：,14+8+3+5+16+21 = 67,设N=(V,E)是连通网，T=(U,TE)为N的最小生成树。(1) 初始令U=u,(u V), TE= 。(2) 在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u,v)。(3) 将(u,v)并入集合TE，同时v并入U。(4) 重复上述操作直至U=V为止。,设置一个辅助数组，记录从U到U-V具有最小代价的边。对每个顶点vi U-V，在辅助数组中存在一个相应分量closedgei-1。,struct VertexType adjvex; / U集中的顶点 VRType lowcost; / 边的权值 closedgeMAX_VERTEX_NUM;,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,7,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,a b c d e f g,void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu for (i=1; iG.vexnum; +i) ,继续向生成树上添加顶点;,k = minimum(closedge); / 求出加入生成树的下一个顶点(k) printf(closedgek.adjvex, G.vexsk); / 输出生成树上一条边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) /修改其它顶点的最小边 if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ;,v1 6,v1 1,v1 5,v1,v2v3v4v5v6,2,v3 5,v2 3,0,v1v3,v2v4v5v6,v3 4,v3 6,v1 5,5,0,v1v3v6,v2v4v5,v1v3v6v4v2,v3 6,v6 2,v3 5,0,3,0,v1v3v6v4,v2v5,v3 5,v3 6,0,0,1,0,v1v3v6v4v2v5,v5,0,0,0,0,4,0,0,0,0,具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔算法的基本思想：,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,例如:,7,12,18,19,算法描述:,构造非连通图 ST=( U, ); k = i = 0; / k 计选中的边数 while (kn-1) +i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路， 则 输出边(u,v); 且 k+;,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀疏图,算法名,适应范围,比较两种算法,7.5.1 拓扑排序,7.5.2 关键路径,7.5有向无环图及其应用,7.5.1 拓扑排序,一、问题提出:,假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。,例如：学生选修课程问题。 顶点表示课程，有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧。 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业 拓扑排序。,二、定义 AOV网：用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)，简称AOV网。 若是网中一条弧，则vi是vj的直接前驱；vj是vi的直接后继。 AOV网中不允许有回路，这意味着某项活动以自己为先决条件。,拓扑排序：把AOV网中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫拓扑排序。 由此所得顶点的线性序列称之为拓扑有序序列。,例如：对于下列有向图,B,D,A,C,可求得拓扑有序序列： A B C D 或 A C B D,B,D,A,C,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B, C, D,三、如何进行拓扑排序？,（1）从有向图中选取一个没有前驱 的顶点，并输出之；,重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,（2）从有向图中删去此顶点以及所 有以它为尾的弧；,a,b,c,g,h,d,f,e,a,b,h,c,d,g,f,e,四、算法实现,(1) 把邻接表中所有入度为0的顶点进栈。(2) 栈非空时，输出栈顶元素v并退栈；在邻接表中查找v的直接后继w，把w的入度减1；若w的入度为0则进栈。(3) 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。,Status ToplogicalSort(ALGraph G) /有向图G采用邻接表存储结构。若G无回路，则输出G的 /顶点的一个拓扑序列并返回OK，否则ERROR。 FindInDegree(G, indegree); / 对各顶点 /求入度 indegree0.vernum-1 InitStack(S); for(i=0;inextarc) k=p-adjvex; / 对i号顶点的每个邻接点的入度减1 if (-indegreek)=0) Push(S,k); / 若入度减为0，则入栈 / for / while if(countnextarc) k=p-adjvex; dut=*(p-info); if (vlk-dutnextarc) k=p-adjvex; dut=*(p-info); ee=vej; el=vlk-dut; tag=(ee=el)? * : ; printf (j, k, dut, ee, el, tag); /for / CriticalPath,7.6 最短路径,用带权的有向图表示一个交通运输网，图中：顶点表示城市，弧表示城市间的交通联系，权表示此线路的长度或沿此线路运输所花的时间或费用等。 问题：从某顶点出发，沿图的弧到达另一顶点所经过的路径中，各弧上权值之和最小的一条路径最短路径。,问题提出：,7.6.1 从某个源点到其余各 顶点的最短路径,7.6.2 每一对顶点之间的最 短路径,7.6.1 从某个源点到其余各顶点的最短路径,无,（V0,V2） 10,（V0,V4,V3） 50,（V0,V4） 30,（V0,V4,V3,V5） 60,迪杰斯特拉(Dijkstra)算法思想:,依最短路径的长度递增的次序求得各条路径。,源点,v1,其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。,v2,在这条路径上，必定只含一条弧，并且这条弧的权值最小。,下一条路径长度次短的最短路径的特点：,路径长度最短的最短路径的特点：,它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。,其余最短路径的特点：,再下一条路径长度次短的最短路径的特点:,它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。,它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。,算法实现：,一般情况下， Di = 或者 = + 。,设置辅助数组D，其中每个分量Di 表示 当前所求得的从源点到其余各顶点 Vi的最短路径。,1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。,2）修改其它各顶点的