图的定义和术语课件.ppt

7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用 7.6 最短路径,第七章 图,图(Graph)由一个顶点集V和一个边集E构成的数据结构。 Graph = (V, E )其中，V = x | x 某个数据对象 是非空有限的顶点集合； E = (x, y) | x, y V 或 E = | x, y V Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的,所以也叫做弧(arc)的集合,x称为弧尾或始点,y称为弧头或终点.,7.1 图的定义和术语,有向图有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头无向图无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v),7.1 图的定义和术语,例7.1,图G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,图G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),7.1 图的定义和术语,无向完全图(Completed graph) n个顶点的无向图有n(n-1)/2条边（最大边数是n(n-1)/2）有向完全图n个顶点的有向图，有n(n-1)条边（最大边数是n(n-1) ）稀疏图(sparse graph)：边或弧很少的图,通常边数 nlog2n稠密图(Dense graph)无向图中，边数接近n(n-1)/2 ； 有向图中，边数接近n(n-1),7.1 图的定义和术语,有向完全图,7.1 图的定义和术语,无向图(树),有向图,完全图,无向 完全图,权与图的边或弧相关的数网带权的有向图叫有向网，带权的无向图叫无向网,7.1 图的定义和术语,子图如果图G(V,E)和图G(V,E),满足：VV，EE 则称G为G的子图,7.1 图的定义和术语,邻接点(或相邻点),关联 如果 e=(u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点或相邻顶点;称边e与顶点u ,v 关联; 如果 e= 是 E(G) 中的一条弧，则称 u 邻接到v,v邻接于u,也称e与u,v关联;称弧e与顶点u ,v 关联;,7.1 图的定义和术语,顶点的度（于树的度不同）无向图中，顶点的度为与每个顶点相连的边数,记作TD(v)有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目,记为ID(v)出度：以该顶点为尾的弧的数目,记为OD(v)一个顶点的度数等于该顶点的入度与出度之和,即TD(v)=OD(v)+ID(v),7.1 图的定义和术语,路径路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1jn)路径长度沿路径边的数目或沿路径各边权值之和简单路径序列中顶点不重复出现的路径回路(环)第一个顶点和最后一个顶点相同的路径简单回路(简单环)除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路,7.1 图的定义和术语,7.1 图的定义和术语,V0V1V3V2,V0V1V3V2V0V1V2,V0V1V3V0,连通图与连通分量在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。,7.1 图的定义和术语,强连通图与强连通分量在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,强连通图,有向图G 有向图G的两个 强连通分量,7.1 图的定义和术语,生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环若图中有n个顶点，却少于n-1条边，必为非连通图。,7.1 图的定义和术语,生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,有向图G的生成森林,有向图G,7.1 图的定义和术语,本章只讨论简单图,有两类图形不在本章讨论之列：,7.1 图的定义和术语,图的抽象数据类型定义,ADT Graph 数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系 R：R=VR；VR=|v,wV 且 P(v,w), 表示从v到w的弧， 谓词P(v,w)定义了弧的意义或信息基本操作P：,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 的最后一个邻接点，则返回“空”。,基本操作,InsertArc( / 在G中增添弧，若G是无向的， /则还增添对称弧。,DeleteArc( /在G中删除弧，若G是无向的， /则还删除对称弧。,DeleteVex( / 删除G中顶点v及其相关的弧。,InsertVex( /在图G中增添新顶点v。,基本操作,DFSTraverse(G, v, Visit()/从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。,BFSTraverse(G, v, Visit()/从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。,图的四种常用的存储形式：邻接矩阵和加权邻接矩阵（labeled adjacency matrix）邻接表十字链表邻接多重表,7.2 图的存储结构,一、(加权)邻接矩阵（labeled adjacency matrix）,设图 G= 是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 G.arcsnn，定义：,无向图G1,有向图G2,一、(加权)邻接矩阵（continue）,(1) 对称矩阵(可采用压缩存储);(2) 每一行(或列)1的个数是该顶点的度;(3) 主对角线全为0(简单图);,从邻接矩阵中可以反映图的许多特征:,无向图,一、(加权)邻接矩阵（continue）,有向图,(1) 每一行1的个数是该顶点的出度;,(2) 每一列1的个数是该顶点的入度;,(3) 主对角线全为0(简单图);,有向图的邻接矩阵不一定对称。,定义为：,以有向网为例：,邻接矩阵：,N.Edge =,( v1 v2 v3 v4 v5 v6 ),顶点表：, 5 7 4 8 9 5 6 5 3 1 ,网络的邻接矩阵,一、(加权)邻接矩阵（continue）,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。,邻接矩阵法优点：,邻接矩阵法缺点：,一、(加权)邻接矩阵（continue）,#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef enumDG, DN,UDG,UDN GraghKind;typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,用邻接矩阵表示的图的存储表示(P161),typedef struct / 图的定义 VertexType vexsMAX_VERTEX_NUM;/ 顶点信息 AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph;,用邻接矩阵表示的图的存储表示(continue),Status CreateUDN(Mgraph ,例：用邻接矩阵生成无向网的算法（参见教材P162）,scanf(/输入顶点值，存入一维向量中,for(i=0; iG.vexnum; +i) /对邻接矩阵n*n个单元初始化，adj=,info=NULL for(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL;,for(k=0;kG.arcnum;+k) /给弧赋初值(循环次数弧数) scanf( G.arcsji = G.arcs i j； /无向网是对称矩阵 ,对于n个顶点e条弧的网，建网时间效率 = O(n2+n+e*n),int firstAdjVex(Mgraph G, int v) /返回顶点v的第一个邻接点，G为无向图 for (k=0;k0 ) break;if (k=G.vexnum) k= -1; / 无邻接点return k;/ end firstAdjVex( ),图的部分操作在邻接矩阵上的实现,二、 邻接表 (Adjacency List),无向图的邻接表为每个顶点建立一个单链表,第i个单链表中的结点表示与顶点vi相邻的顶点,注：邻接表不唯一，因各个边结点的链入顺序是任意的。,data: 结点的数据域，保存结点的数据值。firstarc: 结点的指针域，给出自该结点出发的的第一条边 的边结点的地址。,头结点:,表结点:,adjvex: 该边或弧所指向的顶点的位置.nextarc: 指向下一条边或弧的指针.,二、 邻接表 (Adjacency List),在无向图的邻接表中,如何求每个顶点的度？,若顶点数为n,边数为e时,则在无向图中共需多少 个结点？,二、 邻接表 (Adjacency List),n个头结点,2e个表结点,第 i 个链表中的结点个数是顶点 i 的度,有向图的邻接表和逆邻接表在有向图的邻接表中，第 i 个单链表链接的边都是顶点 i 发出的边。也叫做出边表。在有向图的逆邻接表中，第 i 个单链表链接的边都是进入顶点 i 的边。也叫做入边表。,邻接表(出边),逆邻接表(入边),0123,0123,用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。,网络 (带权图) 的邻接表,带权图的边结点中保存该边上的权值 cost,邻接表表示的图的存储结构（P163）,/边结点定义typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;,/头结点定义typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;,邻接表表示的图的存储结构（P163）,/图的定义typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;,邻接表表示的图的存储结构（P163）,图的操作在邻接连表的上的实现int firstAdjVex(ALGraph ghead ,int v) return gheadv-firstArc.adjvex;/ end firstAdjVex( )int nextAdjVex(ALGraph ghead,int v, int w) p=gheadv-firstArc;while (p/ end nextAdjVex( ),找某顶点的所有邻接点的时间复杂度是O(e),如何建立邻接表（以有向图为例）,算法思想：首先将邻接表表头数组初始化，vertex域初始化为i，firstarc初始化为NULL；然后对读入的每一条弧，产生一个表结点，adjver域置为j，并将结点链接到邻接表的第i个链表中。,算法如下：,Void GreatAdjList(ALGraph / GreatAdjList,讨论：邻接表与邻接矩阵的比较,1. 联系：都可以用来存储有向图和无向图；邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2. 区别：邻接矩阵是顺序结构，邻接表是链式结构对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2),三、 邻接多重表 (无向图的一种存储结构),在无向图的邻接表中,一条边出现两个单链表中.浪费空间，也给某种操作带来了困难。在邻接多重表中，每一条边只有一个结点(称边结点)为有关边的处理提供了方便。,其中:mark 是记录是否处理过的标记；ivex和jvex是依附于该边的两顶点位置。ilink域指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边。需要时还可设置一个存放与该边相关的权值的域 cost。,边结点的结构,Ebox:,三、 邻接多重表 (无向图的一种存储结构),顶点结点的结构: 其中:data 存放与该顶点相关的信息;Firstarc 是指示第一条依附于该顶点的边的指针。存储顶点信息的结点表以顺序表方式组织.在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。从顶点 i 出发, 可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。,VexBox:,三、 邻接多重表 (无向图的一种存储结构),三、 邻接多重表 (无向图的一种存储结构),四、十字链表(有向图的一种存储结构),可以把十字链表看成是将有向图的邻接表和逆邻接表这两个表结合起来而得到的一种链表。在十字链表中,有向图中每一条弧对应一个结点(称弧结点)每一个顶点也对应一个结点(称顶点结点)。,其中: tailvex表示该弧的弧尾顶点在图中的位置； headvex表示该弧的弧头顶点在图中的位置； hlink指向弧头相同的下一条弧的指针； tlink指向弧尾相同的下一条边的指针。 需要时还可有权值域cost,边结点的结构,ArcBox:,四、十字链表(有向图的一种存储结构),顶点结点的结构,VexNode:,其中:数据域data存放与该顶点相关的信息，指针域Firstin指向以该顶点为弧头的第一条弧；指针域Firstout指向以该顶点为弧尾的第一条弧。,四、十字链表(有向图的一种存储结构),四、十字链表(有向图的一种存储结构),#define MAX_VERTEX_NUM 20Typedef struct ArcBox /弧结点结构 int tailvex , headvex ; struct ArcBox * hlink , tlink; InfoType *info; ArcBox；Typedef struct VexNode /顶点结构 VertexType data; ArcBox * firstin,*firstout;VexNode; Typedef struct VexNode xlist MAX_VERTEX_NUM ; /表头向量 int vexnum, arcnum;OLGraph; /图结构,7.3 图的遍历,从已给的连通图中某一顶点出发，沿着一些边访问图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph Traversal )。,深度优先遍历,广度优先遍历,图的两种遍历方法,图中可能存在回路，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited i 为 1，防止它被多次访问。,7.3 图的遍历,DFS算法思想：,深度优先搜索DFS ( Depth First Search ),从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至V0 的所有邻接点都被访问到。,若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,深度优先搜索DFS ( Depth First Search ),深度优先搜索的示例,深度优先遍历生成树,图的深度优先遍历算法void dfsTraverse( )for (v=1; v=n; v+) visitedv=false;for (v=1; v=n; v+) if (!visitedv) dfs(v);void dfs(int v) visitedv=1; for (w=firstAdjVex(v); w; w=nextAdjVex(v,w)if (!visitedw) dfs(w); / 使用ADT,在递归函数中增加一计数器sum，初值为n，每访问一次就减1,减到0则return，可避免递归时间过长。,在邻接矩阵A上实现 void dfs(int v) visitedv=true; for (w=1; w0) if (!visitedw) dfs(w); /,图的深度优先遍历算法,在邻接链表上实现 void dfs(int v) visitedv=true; p=gheadv-firstArc; while (p) w=p-adjvex; if (!visitedw) dfs(w);p=p-next; ,同学们自己考虑非递归实现算法,图的深度优先遍历算法,Dfs1(Graph g, int v)/利用栈实现非递归算法 /第一个顶点入栈并访问 Visit(v); visitv=1;push(s,v);/当栈不空时做 Whlie(!EmptyStack(s) p=gheadv-firstArc;/找到栈顶的一个未被访问的邻接点，入栈并访问while (p) w=p-adjvex; if (!visitedw) push(s,w);visit(w); p=gheadw-firstArc; else p=p-next; /while/如果所有邻接点都被访问，出栈 pop(s,v); /while,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,DFS 算法效率分析:,设图中有 n 个顶点，e 条边，遍历时对图中每个顶点至多调用一次DSF函数，遍历图的过程就是对每个顶点查找其邻接点的过程，消耗的时间取决于所采用的存储结构如果用邻接矩阵来表示图，查找每个顶点的邻接点所需的时间为O(n2)。如果用邻接表来表示图，查找每个顶点的邻接点所需的时间为O(e),加上访问 n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。,二、广度优先搜索BFS ( Breadth First Search ),BFS算法思想：,从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。,若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,A,B,C,D,E,F,G,H,I,J,K,L,树的按层次进行访问的次序： A、B、C、D、E、F、G、H、 I、J、K、L适用的数据结构：队列,二、广度优先搜索BFS,除了辅助数组 visited 之外，为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,广度优先搜索BFS,Void BFSTraverse( Gragh G, int v) for (v=0; vG.vexnum; v+) visitedv=0; /清访问标记 InitQueue(Q); /清队列Q; for (v=0; vG.vexnum; v+) /对每一个顶点v if (!visitedv) visitedv=1; visit(v); /访问v; 标记v; EnQueue(Q,v); /v未被访问 while (!QueueEmpty(Q) / Q不空 DeQueue(Q,u); /出队头元素到u for (w=firstAdjVex(u); w; w=nextAdjVex(u,w) if (!visitedw) visitedw=1; visit(w); EnQueue(w); /将u的每个未被访问的邻接点w 入队 /if /while /if ,算法分析:,如果使用邻接表表示图，则循环的总时间代价为 d0+ d1 + + dn-1 = O(e)，其中的 di 是顶点 i 的度如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。,广度优先搜索BFS,DFS与BFS之比较：空间复杂度相同，都是O(n)(借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。,1. 求一条从顶点 i 到顶点 s 的简单路径,2. 求两个顶点之间的一条路径长度最短的路径,三、遍历应用举例,应用1. 求一条从顶点 i 到顶点 s 的简单路径,a,b,c,h,d,e,k,f,g,求从顶点 b 到顶点 k 的一条简单路径。,从顶点 b 出发进行深度优先搜索遍历,例如:,假设找到的第一个邻接点是a,且得到的结点访问序列为: b a d h c e k f g,假设找到的第一个邻接点是c,则得到的结点访问序列为: b c h d a e k f g,void DFSearch( int v, int s, char *PATH) / 从第v个顶点出发递归地深度优先遍历图G， / 求得一条从v到s的简单路径，并记录在PATH中 visitedv = TRUE; / 访问第 v 个顶点 for (w=FirstAdjVex(v); w!=0 ; w=NextAdjVex(v) if (!visitedw) DFSearch(w, s, PATH); ,Append(PATH, getVertex(v); / 第v个顶点加入路径,&!found,if (w=s) found = TRUE; Append(PATH, w); else,if (!found) Delete (PATH,v); / 从路径上删除顶点 v,应用2. 求两个顶点之间的一条路径长度最短的路径,若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?,a,b,c,h,d,e,k,f,g,求路径长度最短的路径可以基于广度优先搜索遍历进行，但需要修改队列的结点结构及其入队列和出队列的算法。,深度优先搜索访问顶点的次序取决于图的存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。,例如:求下图中顶点 3 至顶点 5 的一条最短路径。,队列用双向链表的表示:,3,2,1,4,7,5,6,8,9,7.4 图的连通性问题,对无向连通图进行遍历得到的将是一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。对非连通图进行遍历，得到的将是各连通分量的生成树，即图的生成森林！,7.4.1 无向图的连通分量和生成树,例1 ：画出下图的生成树,DFS生成树,邻接表,v0,v2,v1,v4,v3,BFS生成树,v0,无向连通图,例2：画出下图的生成森林（或极小连通子图）,求解步骤：Step1:先求出邻接矩阵或邻接表；Step2:写出DFS或BFS结果序列；Step3:画出对应子图或生成森林。,我们选用邻接表方式来求深度优先搜索生成森林,子图1：,再写出DFS结果（3次）ABMJLCFDEGHKI,先写出邻接表（或邻接矩阵）：,子图2：,子图3：,极小连通！,子图(或连通分量),生成森林,求连通分量的算法（生成森林用对应的二叉树存储）Void DFSForest( BiTree / 深度优先遍历，并建立树；/if/,Void DFSTree(Graph G, int v, CSTree / if / DFSTree(),7.4.2有向图的强连通分量 算法思想：使用dfs算法思想。设一编号数组finished 1. 对图G的邻接链表进行dfs遍历，并按退出递归的次序给顶点编号。（1，2，3，.）2.对图G的逆邻接链表进行dfs遍历，每次调用dfs的出发点是编号最大的未被访问的顶点(上次最后完成搜索的顶点）,图G,得到的顶点集：1, 3，24，5,7.4.3 最小生成树 MST( Minimum cost Spanning Tree ),使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。,MST:在网络的多个生成树中，寻找一个各边权值之和最小的生成树。,构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。,假设在n个城市之间要建立通信网络线，要求使得这个城市之间连通且费用最少。,MST典型用途：,数学模型：顶点表示城市，有n个；边表示线路，有n1条；边的权值表示线路的经济代价；连通网表示n个城市间通信网。,问题抽象： n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST,求一个带权连通图中的最小生成树的方法: Prim算法 Kruskal算法,都是利用MST的性质构造最小生成树的算法,7.4.3 最小生成树 MST,最小生成树的 MST 性质：,若U集是V的一个非空子集，若(u0, v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0, v0)必在某一最小生成树上。,U,V-U,证明（反证法）设G的任何MST都不包含（u,v）。设T是G的一个MST，将（u,v）加入T，形成回路。去掉（u,v）得到T , 因 wuvwuv，所以T 的边权之和小于T 的边权之和，与T是MST矛盾。,Uuu,V-Uvv,最小生成树的 MST 性质：,1、普里姆(Prim)算法,普里姆算法的基本思想（是一种贪婪算法）设连通网络图G = ,TE是G上最小生成树中边的集合.1. TE= ，U=u0 ;2. 在U和V-U之间选最小边（u,v），将v加入U，将(u,v)加入TE中;3. 重复2直到U=V(或n-1次),普里姆(Prim)算法过程示例,1,2,3,7,4,5,6,28,16,12,22,25,10,25,14,18,1,2,3,7,4,5,6,28,16,12,22,25,10,25,14,18,普里姆(Prim)算法过程示例,1,2,3,7,4,5,6,28,16,12,22,25,10,25,14,18,普里姆(Prim)算法过程示例,1,2,3,7,4,5,6,28,16,12,22,25,10,25,14,18,普里姆(Prim)算法过程示例,1,2,3,7,4,5,6,28,16,12,22,25,10,25,14,18,普里姆(Prim)算法过程示例,1,2,3,7,4,5,6,28,16,12,22,25,10,25,14,18,普里姆(Prim)算法过程示例,1,2,3,7,4,5,6,28,16,12,22,25,10,25,14,18,普里姆(Prim)算法过程示例,设置一个辅助数组closedge ，对每个顶点viVU,存在分量closedgei-1,有两个域，Lowcost=Mincost(u,vi)|u Uadjvex: 存储与该边关联的U中顶点,Prime算法的实现,辅助数组closedge说明如下:Struct VertexType adjvex; VRType lowcost;closedgeMAX_VERTEX_NUM;,细化的普里姆(Prim)算法:TE= ; closedgev.adjvex=v1; closedgev.lowcost=adj.matrix1v;2. U1=1; U2n=0;3. 选Uk=0 的closedgek.lowcost最小的k；4. Uk=1, u= closedgek.adjvex, (u,k) 加入TE中5. 修改所有不属于U的k的邻接点w的lowcost 值，规则是：如果closedgew.lowcost adj.matrixkw则：closedgew.lowcost= adj.matrixkw,1,2,3,7,4,5,6,28,16,12,22,25,10,25,14,18,void MiniSpanTree_PRIM(Mgtaph G,VertexType int u) k=LocateVer(G,u); /k为顶点u的序号 for (v=0; vG.vexnum; v+) if(v!=k) closedgev=u, G.arcskj.adj; closedgek.lowcost=0;/第k个顶点加入在U集合中 for (i=1; i G.vexnum; i+) k=minimum(closedge); /lowcost最小的顶点序号为k u=closedgek.adjvex; prinf(u,G.vexsk ); closedgek.lowcost=0;/第k个顶点并入U集 for (j=0; jG.vexnum; j+) if (G.arcskj.adjclosedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj / for / MinISpan_Tree_PRIM,设连通网络有 n 个顶点 ，则该算法的时间复杂度为O(n2)。它适用于边稠密的网络。,Prime算法分析,2、Kruscal 算法,算法思想: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,构造非连通图 ST=( V, ); k = i = 0; / k 计选中的边数,i计检查的边数 while (kn-1) +i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路， 则 输出边(u,v); 且 k+;,算法描述:,7.4.4 关节点和重连通分量 (Biconnected Component),若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。,若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点(割点)。,没有关节点的连通图为重（双）连通图。,如何判别给定的连通图是否是双连通图？,在一个无向连通图G中, 重连通分量可以利用深度优先生成树找到。关节点的两个特性：1.深度优先生成树的根是关节点的充要条件是它至少有两个子女。2.其它顶点 u 是关节点的充要条件是它至少有一个子女 w, 以 w为根的子树与u 的任一祖先之间无回边。,7.4.4 关节点和重连通分量 (Biconnected Component),例如:下列连通图中，,顶点 a 和顶点 c 是关节点,深度优先生成树,1) 设V0为深度优先遍历的出发点 p = G.vertices0.firstarc; v = p-adjvex; DFSArticul(G, v); / 从第v顶点出发深度优先搜索 if (count G.vexnum) / 生成树的根有至少两棵子树 printf (0, G.vertices0.data); / 根是关节点,2) 定义函数: low(v) = Minvisitedv, loww, visitedk 其中: 顶点w 是生成树上顶点v 的孩子; 顶点k 是生成树上和顶点v有回边相联接的祖先; visited记录深度优先遍历时的访问次序 若对顶点v，在生成树上存在一个子树根w, 且 loww visitedv 则顶点v为关节点。,对深度优先遍历算法作如下修改：,visitedv的值改为遍历过程中顶点的访问次序count 值;,2. 遍历过程中求得 lowv=Minvisitedv,loww,visitedk,3. 从子树遍历返回时， 判别lowwvisitedv?,for(p=G.verticesv0.firstarc; p; p=p-nextarc) ,void DFSArticul(ALGraph G, int v0) / 从第v0个顶点出发深度优先遍历图 G, / 查找并输出关节点 / DFSArticul,min =visitedv0 = +count; / v0是第count个访问的顶点, 并设lowv0的初值为min,/ 检查v0的每个邻接点,lowv0 = min;,w = p-adjvex; / w为v0的邻接顶点 if (visitedw = 0) / w未曾被访问 DFSArticul(G, w); / 返回前求得loww else / w是回边上的顶点,if (loww min) min = loww;,if (loww=visitedv0) printf(v0, G.verticesv0.data); /输出关节点,if (visitedw min) min = visitedw;,算法 Biconnected 的时间代价是 O(n+e)。其中 n 是该连通图的顶点数，e 是该连通图的边数 此算法的前提条件是连通图中至少有两个顶点,因为正好有一个顶点的图连一条边也没有。,7.5.1 拓扑排序7.5.2 关键路径,7.5 有向无环图及其应用,7.5.1 拓扑排序,一、概念1、有向无环图 DAG (Directed Acyclic Graph) 无环的有向图2、 AOV (Activity On Vertices)网络：用顶点表示活动，用有向弧表示活动间的优先关系。Vi 必须先于活动Vj 进行。这种有向图称为用顶点表示活动的网络。若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路，这意味着某项活动不能以自己为先决条件,计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,7.5 有向无环图及其应用,1、在AOV中拓扑有序序列：将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所