[理学]课件c语言：数据结构第七章 图.ppt

线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。,(a1, , ai-1, ai, , an),知识回顾 (2009-11-27 week 10 fri),在树形结构中，数据元素之间有着层次关系，每一层上的数据元素可能和下一层中多个元素相关，只能和上一层中一个元素相关。,2019/5/3,2,七桥问题,2019/5/3,3,网络路由问题,2019/5/3,4,一笔画问题,2019/5/3,5,第7章 图(Graph),2019/5/3,6,要求,掌握图的各种存储结构及其构造算法。 熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。 应用图的遍历算法求解各种简单路径问题。,7.1 图的定义和术语,7.2 图的存储结构（*）,7.3 图的遍历（*）,7.4 图的连通性问题,7.5 有向无环图及其应用,拓扑排序,关键路径,最小生成树（*）,主要内容,7.6 最短路径,7.1 图的定义和术语,图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V , R ) 其中，VR| v,wV 且 P(v,w) 表示从 v 到 w 的一条弧，并称 v 为弧头，w 为弧尾。 谓词 P(v,w) 定义了弧 的意义或信息。,图的结构定义:,由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图(Digraph)。,例如:,G1 = (V1, VR1),其中 V1=A, B, C, D, E VR1=, , , , , , ,A,B,C,D,E,顶点(Vertex)：图中的数据元素。,若 VR,则表示从v到w的一条弧(Arc)，v为弧尾（初始点），w为弧头（终端点）,若VR 必有VR, 即VR是对称的，则以无序对（v,w)代替这两个有序对，表示v 和 w 之间的一条边。,B C A D F E,由顶点集和边集构成的图称作无向图Undigraph。,例如: G2=(V2,VR2) V2=A, B, C, D, E, F VR2=(A,B), (A,E), (B,E), (C,D), (D,F), (B,F), (C,F) ,2019/5/3,11,名词和术语,权、网、子图,完全图、稀疏图、稠密图,邻接点、度、入度、出度,路径、路径长度、简单路径、简单回路,连通图、连通分量、 强连通图、强连通分量,生成树、生成森林,2019/5/3,12,假设图中有 n 个顶点，e 条边或弧，不考虑顶点到自身的边或弧。,问题：e的取值范围？,2019/5/3,13,假设图中有 n 个顶点，e 条边或弧，,含有 e=n(n-1)/2 条边的无向图称作完全图；,含有 e=n(n-1) 条弧的有向图称作 有向完全图；,若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。,无向完全图 有向完全图,A,B,E,C,F,有两个图G=(V,E) 和图 G=(V,E), 且 VV, EE, 则称 G 为 G 的子图。,15,9,7,21,11,3,2,权：与图的边或弧相关的数。,网:带权的图。,图G 图G,A,C,D,F,E,例如:,TD(B) = 3,TD(A) = 2,边(v, v) 依附于顶点v 和v，边(v, v)和顶点v 和v 相关联。顶点v的度TD(v)是和顶点v 相关联的边的数目。,B,对于无向图G（V,E)，如果边（v, v）E，则称v 和v互为邻接点，即v和v相邻接,顶点的出度OD(v): 以顶点v为尾的弧的数目，,A,B,E,C,F,对有向图来说，,顶点的入度ID(v): 以顶点v为头的弧的数目。,例如:,ID(B) = 2,OD(B) = 1,TD(B) = 3,对于有向图G(V,A)，如果弧 A,则称顶点v邻接到顶点v,顶点v邻接自顶点v。,顶点的度(TD)=出度(OD)+入度(ID),2019/5/3,18,设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm, 则称从顶点u 到顶点w 之间存在一条路径。 路径上边的数目称作路径长度。,A,B,E,C,F,如:长度为3的路径A,B,C,F,回路:第一个顶点和最后一个顶点相同的路径。,2019/5/3,19,简单路径:序列中顶点不重复出现的路径。,简单回路:除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。,若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图；,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,B,A,C,D,F,E,B,A,C,D,F,E,A,B,M,L,C,F,J,D,E,H,K,G,I,A,B,M,L,C,F,J,D,E,H,K,G,I,无向图G3 G3的三个连通分量,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。,A,B,E,C,F,A,B,E,C,F,对有向图，,否则，其各个强连通子图称作它的强连通分量。,一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边,A,B,M,L,C,F,J,A,B,M,L,C,F,J,一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧,A,B,F,E,D,C,有向图及其生成森林,路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1,连通图,强连通图,非连通图 连通分量,2019/5/3,28,图的抽象数据类型定义,ADT Graph 数据对象v：v是具有相同特性的数据元素的集合，称为顶点。 数据关系R=VR VR| v,wV 且 P(v,w) 表示从 v 到 w弧， 谓词 P(v,w) 定义了弧 的意义或信息。,2019/5/3,29,结构的建立和销毁,插入或删除顶点,对邻接点的操作,对顶点的访问操作,遍历,插入和删除弧,基本操作,CreatGraph(&G, V, VR)； / 按V和VR的定义构造图,DestroyGraph(&G)； / 销毁图,结构的建立和销毁,对顶点的访问操作,LocateVex(G, u); /若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, Visit(); /深度优先遍历图G，并对每个顶点调用/函数Visit一次且仅一次。一旦visit()失败，则操作失败,BFSTraverse(G, Visit(); /广度优先遍历图G，并对每个顶点调 /用函数Visit一次且仅一次。一旦visit() /失败，则操作失败,2019/5/3,36,7.2 图的存储结构,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,三、有向图的十字链表存储表示,四、无向图的邻接多重表存储表示,2019/5/3,37,Aij=,0 (i,j)VR,1 (i,j)VR,一、图的数组(邻接矩阵)存储表示,B,A,C,D,F,E,定义:矩阵的元素为,2019/5/3,38,有向图的邻接矩阵为非对称矩阵,A,B,E,C,F,2019/5/3,39,Aij=,Wi,j (i,j)VR, (i,j)VR,网的邻接矩阵定义为,（ v1 v2 v3 v4 v5 ）,v1 v2 v3 v4 v5,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,分析1：无向图的邻接矩阵是对称的；可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 分析2：顶点i 的度第 i 行 (或列) 中1 的个数； 特别：完全图的邻接矩阵中，对角元素为0，其余全1。,顶点表： V=,讨论1、无向图的邻接矩阵表示。,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,邻接矩阵： A=,讨论2 ：有向图的邻接矩阵表示。,分析1：有向图的邻接矩阵可能是不对称的。有n个顶点的有向图需存储空间为n 分析2：顶点vi的出度=第i行元素之和，OD(vi )= A i j 顶点vi的入度=第i列元素之和。ID(vi )= A j i 顶点的度=第i行元素之和+第i列元素之和, 即：TD( vi ) = OD( vi ) + ID( vi ),邻接矩阵：,A=,( v1 v2 v3 v4 ),v1 v2 v3 v4,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。,顶点表：,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。,讨论3 ： 有权图（即网络）的邻接矩阵表示。,以有向网为例：,邻接矩阵：, ,A =,( v1 v2 v3 v4 v5 v6 ),邻接矩阵法优点：,邻接矩阵法缺点：,顶点表：,5 7 4 8 9 5 6 5 3 1, 5 7 4 8 9 5 6 5 3 1 ,v1 v2 v3 v4 v5 v6,对稀疏图而言尤其浪费空间。,typedef struct ArcCell / 弧的定义 VRType adj;/ VRType是顶点关系类型。对无权图, /用1或0表示相邻否;对带权图,则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;,#define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /最大顶点个数 Typedef enum DG, DN, UDG, UDN GraphKind; /有向图，有向网，无向图，无向网,图的数组（邻接矩阵）存储表示,typedef struct / 图的定义 VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; /邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志 MGraph;,Status CreateUDN(MGraph /adj,info,For(k=0;k的权值 If(IncInfo) Input(*G.); /若弧含有相关信息,则输入 G.arcsji=G.arcsij;/置的对称弧 Return OK; /CreateUDN,2019/5/3,47,0 A 1 4 1 B 0 4 5 2 C 3 5 3 D 2 5 4 E 0 1 5 F 1 2 3,B,A,C,D,F,E,二、图的邻接表 存储表示,2019/5/3,48,1 4,2,3,0 1,2,0 1 2 3 4,A B C D E,有向图的邻接表,A,B,E,C,D,可见，在有向图的邻接表中不易找到指向该顶点的弧。,2019/5/3,49,A,B,E,C,D,有向图的逆邻接表,A B C D E,3,0,3,4,2,0,0 1 2 3 4,在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。,2019/5/3,50,typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;,adjvex nextarc info,弧的结点结构（表结点）,2019/5/3,51,typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;,data firstarc,顶点的结点结构,2019/5/3,52,typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;,图的结构定义,2019/5/3,53,分析1: 对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点：,分析2: 在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进,怎样计算无向图顶点的度？,邻接表的缺点：,邻接表的优点：,TD(Vi)=无向图中顶点Vi的度为第i个单链表中的结点数,空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数,怎样计算有向图顶点的度？,2019/5/3,54,讨论：邻接表与邻接矩阵有什么异同之处？,1. 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。 2. 区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。 邻接矩阵中判断两结点是否相连成边，只需看对应矩阵元素是否为零，在邻接表中则要扫描某一结点的单链表（邻接链表）； 求边的数目时，邻接矩阵要检测整个矩阵，而邻接表则只需对每个边表中结点进行计数即可。 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。 3. 用途： 邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)； 而邻接表多用于稀疏图的存储（en2),它是有向图的另一种链式结构。 思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。 1、开设弧结点，设5个域（每段弧是一个数据元素） 2、开设顶点结点，设3个域（每个顶点也是一个数据元素）,data : 顶点信息 Firstin : 以顶点为弧头的第一条弧结点 Firstout: 以顶点为弧尾的第一条弧结点,顶点结点,弧结点,tailvex: 弧尾顶点位置 headvex: 弧头顶点位置 hlink: 弧头相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息,n个顶点的集合怎样储存？,仍用顺序存储结构,三、有向图的十字链表存储表示,2019/5/3,56,弧的结点结构,弧尾顶点位置 弧头顶点位置 弧的相关信息,指向下一个有相同弧尾的结点,指向下一个有相同弧头的结点,typedef struct ArcBox / 弧的结构表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode;,2019/5/3,57,顶点的结点结构,顶点信息数据,指向该顶点的第一条入弧,指向该顶点的第一条出弧,typedef struct VexNode / 顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;,2019/5/3,58,typedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点(表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;,有向图的结构表示(十字链表),例：画出有向图的十字链表。,十字链表优点：容易操作，如求顶点的入度、出度等。,此无权图未开第4分量,空间复杂度和建表的时间复杂度都与邻接表相同。,0,1,2,3,2019/5/3,60,四、无向图的邻接多重表存储表示,typedef struct Ebox VisitIf mark; / 访问标记 int ivex, jvex; /该边依附的两个顶点的位置 struct EBox *ilink, *jlink; /分别指向依附于ivex和jvex的下一条边 InfoType *info; / 该边信息指针 EBox;,边的结构表示,2019/5/3,61,typedef struct / 邻接多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;,顶点的结构表示,typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;,无向图的结构表示,2019/5/3,63,知识回顾,图的定义 图的存储,2019/5/3,64,7.3 图的遍历,从图中某个顶点出发游历图，访遍 图中其余顶点，并且使图中的每个顶点 仅被访问一次的过程。,深度优先搜索,广度优先搜索,2019/5/3,65,从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。,一、深度优先搜索遍历图 （Depth_First Search）,连通图的深度优先搜索遍历,2019/5/3,66,V,w1,SG1,SG2,SG3,W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V ： for (W1、W2、W3 ) 若该邻接点W未被访问， 则从它出发进行深度优先搜索遍历。,w2,w3,w2,2019/5/3,67,深度遍历：,深度遍历：V1 V2 V4 V8 V5 V6 V3 V7,V2,V1,V4,V8,V5,V6,V3,V7,2019/5/3,68,可见:,1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历；,为每个顶点设立一个 “访问标志 visitedw”。,2. 如何判别V的邻接点是否被访问？,深度优先搜索（遍历）步骤：,简单归纳： 访问起始点 v; 若v的第1个邻接点没访问过，深度遍历此邻接点； 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。,2019/5/3,70,详细归纳： 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1； 再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2； 然后再从 w2 出发，进行类似的访问， 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它未被访问的邻接顶点。 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问； 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,连通图的深度优先遍历算法 递归算法,Boolean visitedMAX /访问标志数组 Status（*VisitFunc)(int v);/函数变量,2019/5/3,73,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,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,DFS(Graph G, int v) visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w);,2019/5/3,75,首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,非连通图的深度优先搜索遍历,2019/5/3,76,void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图 G 作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS ,2019/5/3,77,a,b,c,h,d,e,k,f,g,F F F F F F F F F,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例如:,0 1 2 3 4 5 6 7 8,2019/5/3,78,算法分析,对每个顶点至多调用一次DFS函数。遍历图的过程实质上是对每个顶点查找其邻接点的过程。 采用二维数组：O(n2) 采用邻接表：O(n+e),基本思想：仿树的层次遍历过程。,v3 ,BFS 结果,v4 v5 ,起点,v2 v1 v6 ,v9 v8 v7,二、广度优先搜索遍历图 （Breadth_First Search）,2019/5/3,80,从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。,若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,2019/5/3,81,V,w1,w8,w3,w7,w6,w2,w5,w4,对连通图，从起始点V到其余各顶点必定存在路径。,其中，V-w1, 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,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,广度优先搜索（遍历）步骤：,简单归纳： 在访问了起始点v之后，依次访问 v的邻接点； 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点； 直到所有顶点都被访问过为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。 因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,广度优先遍历算法,2019/5/3,85,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, ,2019/5/3,86,visitedv = TRUE; Visit(v); / 访问v EnQueue(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,4 3,遍历序列：1 4 3,2 5,遍历序列：1 4 3 2 5,5,遍历序列：1 4 3 2 5,遍历序列：1 4 3 2 5,一、无向图的连通分量与生成树,对无向图进行遍历时 对于连通图，从任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问图中所有顶点。 对于非连通图，则需从多个顶点出发进行搜索，每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。,7.4 图的连通性问题,每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。,从图中任一顶点出发遍历图时，将边集分为两个集合，其中一个是遍历图过程中历经的边的集合，另一个是剩余边的集合。顶点集和遍历图过程中历经的边的集合构成连通图的极小连通子图，它是连通图的一棵生成树,非连通图,连通图,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,2019/5/3,93,A,B,M,L,C,F,J,D,E,H,K,G,I,A,B,M,L,C,F,J,D,E,G,K,I,H,2019/5/3,94,假设以孩子兄弟链表作生成森林的存储结构,建立无向图G的深度优先生成森林的孩子兄弟链表,Void DFSForest(Graph G,CSTree /建立以p为根的生成树 /DFSForest,T,p,q,建立无向图G的深度优先生成森林的孩子兄弟链表。,Void DFSTree(Graph G,int v,CSTree /从第w个顶点出发深度优先遍历图G，建立子生成树q /if /DFSTree,从第v个顶点出发深度优先遍历图G，建立以T为根的生成树,A,B,L,M,C,F,D,E,G,H,J,K,I,T,二、有向图的强连通分量,深度优先遍历是求有向图的强连通分量的一个有效方法，具体求解步骤如下： 在有向图中，从某个顶点出发进行深度优先遍历，并按其所有邻接点的访问都完成（即出栈）的顺序将顶点排列起来。 在该有向图中，从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成访问的那个顶点出发，继续作逆向的深度优先遍历，依次类推，直至有向图中所有顶点都被访问到为止。 每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集，若仅作一次逆向深度优先遍历就能访问到图的所有顶点，则该图是强连通图。,例如对图6-3(a)所示有向图，从顶点v1出发作深度优先遍历，在访问顶点v2后，顶点v2不存在未访问的邻接点从而成为一个“死结点”，如 图(b)所示。将v2从栈顶弹出后，再从顶点v1出发，在访问顶点v3 v4后，顶点v4不存在未访问的邻接点从而也成为“死结点”，如图(c)所示。将v4从栈顶弹出后，顶点v3不存在未访问的邻接点从而也成为“死结点”， 将v3从栈顶弹出后，顶点v1不存在未访问的邻接点从而也成为“死结点”，将v1从栈顶弹出，所以，得到出栈的顶点序列为v2, v4, v3, v1；再从最后一个出栈的顶点v1出发作逆向的深度优先遍历（逆着有向边的箭头方向），得到一个顶点集 v1, v3, v4，如图(d)所示；再从顶点v2出发作逆向的深度优先遍历，得到一个顶点集v2，如图(e)所示。这就是该有向图的两个强连通分量的顶点集。,2019/5/3,101,(连通网的)最小生成树,假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？,问题：,2019/5/3,102,构造网的一棵最小生成树（Minimum Cost Spanning Tree），即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,该问题等价于：,2019/5/3,103,最小树MST性质,假设N=(V,E)是一个连通图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u U, vV-U，则必存在一颗包含边(u,v)的最小生成树。,算法一：普里姆（Prim）算法,算法二：克鲁斯卡尔( Kruskal)算法,2019/5/3,104,取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。,普里姆算法的基本思想:,2019/5/3,105,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,2019/5/3,106,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,2019/5/3,107,设置一个辅助数组，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：,struct VertexType adjvex; / U集中的顶点序号 VRType lowcost; / 边的权值 closedgeMAX_VERTEX_NUM;,2019/5/3,108,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,2019/5/3,109,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) ,继续向生成树上添加顶点;,2019/5/3,110,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 ;,2019/5/3,111,具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔算法的基本思想：,2019/5/3,112,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,2019/5/3,113,算法描述:,构造非连通图 ST=( V, ); k = i = 0; / k 计选中的边数 while (kn-1) +i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路， 则 输出边(u,v); 且 k+; ,2019/5/3,114,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀疏图,算法名,适应范围,比较两种算法,定义：无环的有向图,用途：是描述含有公共子式的表达式的有效工具。实现对相同子式的共享，节省存储空间。,有向无环图,例子见p179图7.23,7.5 有向无环图及其应用,另一用途：有向无环图是描述工程或系统的进行过程的有效工具。：几乎所有工程都可分为若干个称为活动的子工程，而这些子工程之间，通常受着一定条件的约束，如某些子工程的开始必须在另一子工程完成之后。 关心两方面问题：1、工程能否顺利进行。2、估算整个工程完成必须的最短时间。,检查有向图是否存在环：从有向图上某个顶点v出发遍历，在dfs结束之前出现一条从顶点u到顶点v的回边，由于u在生成树是v的子孙，则有向图中必存在包含顶点v和u的环。,拓扑排序 问题提出：学生选修课程问题 顶点表示课程 有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序 定义 AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网 若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继 AOV网中不允许有回路，这意味着某项活动以自己为先决条件 拓扑排序： 由某个集合上的一个偏序得到该集合上的一个全序 由偏序定义得到拓扑有序（全序）的操作,拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环 拓扑排序的方法 在有向图中选一个没有前驱的顶点且输出之 从图中删除该顶点和所有以它为尾的弧 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止,拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一个AOV网的拓扑序列不是唯一的,算法实现 以邻接表作存储结构 把邻接表中所有入度为0的顶点进栈 栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕,在算法中需用定量的描述替代定性的概念： 没有前驱的顶点 入度为零的顶点 删除顶点及以它为尾的弧 弧头顶点的入度减1 为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈”，以保存“入度为零”的顶点。,邻接表结点： typedef struct node int vex; /顶点域 struct node *next; /链域 JD;,表头结点： typedef struct tnode int in; /入度域 struct node *link; /链域 TD; TD gM; /g0不用,1、扫描顶点表，将入度为0 的顶点入栈； 2、while ( 栈非空 ) 将栈顶顶点v弹出并输出之； 检查v的出边，将每条出边终点u的入度减1， 若u的入度变为0，则把u推入栈； 3、若输出的顶点数小于n，则输出“有回路”；否则拓扑 排序正常结束。,拓扑排序算法框架,Status TopologicalSort(ALGraph G) /有向图G采用邻接表存储结构 /若G无回路，则输出G的顶点的一个拓扑序列并返回/OK，否则ERROR。 FindInDegree(G,indegree); /对各顶点求入度indegree0vernum-1 InitStack(S); for ( i=0; iG.vexnum; +i) /建零入度顶点栈S if (!indegreei) Push(S, i);/入度为零的顶点入栈 count=0; /对输出顶点计数 while (! StackEmpty (S) Pop(S, i); printf(i, G.verticesi.data); +count;,/输出i号顶点并计数 for (p=G.verticesi.Firstarc; p; p=p-nextarc) k=p-adjvex; / 对i号顶点的每个邻接点的入度减一 if (!(-indegreek) Push(S,k); /若入度为零，则入栈 /for /while if (countG.vexnum ) return ERROR;/该有向图有回路 Else return OK; /TopologicalSort,算法分析,建邻接表：T(n)=O(e) 搜索入度为0的顶点的时间：T(n)=O(n) 拓扑排序：T(n)=O(n+e),算法描述,1,6,输出序列：6,输出序列：6,输出序列：6,输出序列：6,输出序列：6,输出序列：6,输出序列：6 1,输出序列：6 1,输出序列：6 1,4,输出序列：6 1,4,输出序列：6 1,4,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1,4,3,输出序列：6 1 3,4,3,输出序列：6 1 3,4,输出序列：6 1 3,4,输出序列：6 1 3,4,输出序列：6 1 3,4,2,输出序列：6 1 3,4,2,输出序列：6 1 3,4,2,输出序列：6 1 3 2,4,2,输出序列：6 1 3 2,4,输出序列：6 1 3 2 4,4,输出序列：6 1 3 2 4,输出序列：6 1 3 2 4,5,输出序列：6 1 3 2 4,5,输出序列：6 1 3 2 4 5,5,输出序列：6 1 3 2 4 5,关键路径,如果在无有向环的带权有向图中 用有向边表示一个工程中的各项活动(Activity) 用边上的权值表示活动的持续时间(Duration) 用顶点表示事件(Event),AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：