七章图.PPT

《七章图.PPT》由会员分享，可在线阅读，更多相关《七章图.PPT（142页珍藏版）》请在三一文库上搜索。

1、1,第七章 图,图(Graph)是一种较线性表和树更为复杂的数据结构。 线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继； 在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关； 而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。,2,图(Graph)是由非空的顶点集合和一个描述顶点之间关系边（或者弧）的集合组成，其形式化定义为： G（V，E） Vvi| vidataobject E( vi,vj)| vi, vj V P(vi, vj) 其中，G表示一个图，V是

2、图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。,图的定义和术语,3,在该图中 集合Vv1,v2,v3,v4,v5； 集合E(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)。,（1）无向图 在一个图中，如果任意两个顶点构成的偶对（vi, vj）E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。如下图所示是一个无向图G1。,4,（2）有向图 在一个图中，如果任意两个顶点构成的偶对（vi, vj）E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。,

3、G2=(V2,E2) V2=v1,v2,v3,v4 E2=, , , ,5,（3）顶点、边、弧、弧头、弧尾。 图中，数据元素vi称为顶点(vertex )；(vi, vj)表示在顶点vi和顶点vj之间有一条直接连线。 在无向图中，则称这条连线为边；边用顶点的无序偶对（vi, vj）来表示，称顶点vi和顶点vj互为邻接点，边（vi, vj）依附于顶点vi与顶点vj； 在有向图中，一般称这条连线为弧。弧用顶点的有序偶对来表示，有序偶对的第一个结点vi被称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第二个结点vj被称为终点（或弧头），在图中就是带箭头的一端。,6,（4）无向完全图。在一个无

4、向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。 （5）有向完全图。在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。 （6）稠密图、稀疏图。若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图。,7,（7）顶点的度、入度、出度。 顶点的度（degree）是指依附于某顶点v的边数，通常记为TD(v) 。 在有向图中，要区别顶点的入度与出度的概念。顶点v的入度是指以顶点为终点的弧的数目,记为ID(v)；顶点v出度是指以顶点v为始

5、点的弧的数目，记为OD(v)。 TD(v)=ID(v)OD(v)。,在G1中有： D(v1)=2 D(v2)=3 D(v3)=3 D(v4)=2 D(v5)=2,8,在G2中有： ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2,对于具有n个顶点、e条边的图，顶点vi的度D (vi)与顶点的个数以及边的数目满足关系：,9,8）边的权、网图。 与边有关的数据信息称为权（weight）。边上带权的图称为网图或网络（network）。如

6、果边是有方向的带权图，则就是一个有向网图。,10,（9）路径、路径长度。顶点vp到顶点vq之间的路径（path）是指顶点序列vp,vi1,vi2, , vim,vq.。其中，（vp,vi1），(vi1,vi2)，,(vim,.vq)分别为图中的边。路径上边的数目称为路径长度。,无向图G1中，v1v4v3v5与v1v2v5是从顶点v1 到顶点v5 的两条路径，路径长度分别为3和2。,11,（10）回路、简单路径、简单回路。 序列中顶点不重复出现的路径称为简单路径。 除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。,如图中的v1v3v4v1。,12,（11）子图。

7、对于图G=（V，E），G=（V，E），若存在V是V的子集 ，E是E的子集 ，且E中的边所关联的顶点均在V中，则称图G是G的一个子图。,13,（12）连通的、连通图、连通分量。在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量。,14,（13）强连通图、强连通分量。对于有向图来说，若图中任意一对顶点vi 和vj(ij)均有从一个顶点vi到另一个顶点vj有路径，也有从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。,15,7.2 图的存储结构,邻接

8、矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G（V，E）有n个确定的顶点，即Vv0,v1,vn-1,则表示G中各顶点相邻关系为一个nn的矩阵，矩阵的元素为： 1 若(vi,vj)或是E(G)中的边 Aij= 0 若(vi,vj)或不是E(G)中的边,7.2.1数组表示法（也称为邻接矩阵表示法）,16,若G是网图，则邻接矩阵可定义为： wij 若(vi,vj)或是E(G)中的边 Aij= 0或 若(vi,vj)或不是E(G)中的边 其中，wij表示边(vi,vj)或上的权值；表示一个计算机允许的、大于所有边上权值

9、的数。,17,define INFINITY INT_MAX /最大值 define MAX_VERTEX_NUM 20 /最大顶点个数 typedef enum DG,DN,UDG,UDN GraphKind;/ typedef struct ArcCell VRType adj; /弧是否相通，或权值 InfoType *info; /弧的相关信息 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点向量 AdjMatrix arcs; /邻接矩阵

10、int vexnum, arcnum; /图的当前顶点和弧数 GraphKind kind; /图的种类标志 Mgraph;,图的数组（邻接矩阵）存储表示,18,通过邻接矩阵，求的各个顶点的度 对于无向图：,对于有向图,出度,入度,19,算法7.1在邻接矩阵的存储结构上创建图,Status CreateGraph( MGraph / CreateGraph,20,Status CreateUDN(MGraph / CreateUDN,算法 7.2采用数组（邻接矩阵）表示法，构造无向网G,21,7.2.2 邻接表,22,邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i

11、个单链表中的结点表示依附于顶点Vi的边。 头结点 表结点 因为是每个顶点建立一个单链表，每个单链表的表头结点通常以顺序存储结构（一维数组）的形式存储，以便随机访问任一顶点的链表。,23,邻接表存储表示,#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode; /边表结点 typedef struct VNode VertexType data; ArcNode *firstarc; Vnode, AdjListMAX_VERTEX_

12、NUM; /表头结点 typedef struct AdjList vertices; int vexnum , arcnum; /顶点数和弧数 int kind; /图的种类标志 ALGraph;,24,建立无向图的邻接表,creatadjlist(ALGraph ga ) int i,j,k; ArcNode *s; for (i=0; iadjvex=j; s- nextarc = ga. vertices i. firstarc; ga. vertices i. firstarc =s; s=(ArcNode *)malloc(sizeof(ArcNode); s-adjvex=i;

13、s- nextarc = ga. vertices j. firstarc; ga. vertices j. firstarc =s; ,25,相对于矩阵存储，对于稀疏图，采用邻接表存储能节省空间； 对于无向图的邻接表，表头结点对应的单链表的结点个数图中对应结点的度； 对于有向图的邻接表，表头结点对应的单链表的结点个数图中对应结点的出度； 为了方便求有向图的入度，可以建立一个图的逆邻接表； 逆邻接表：在表头结点所指向的链表中存放的是，指向该表头结点的弧的始点；（如图P164,P7.10的c）,26,7.2.3 十字链表,十字链表（Orthogonal List）是有向图的一种存储方法，它实际上

14、是邻接表与逆邻接表的结合，即把每一条边的边结点分别组织到以弧尾顶点为头结点的链表和以弧头顶点为头顶点的链表中。,27,28,有向图的十字链表存储表示的形式描述如下： #define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex , headvex; /*该弧的尾和头顶点的位置*/ struct ArcBox * hlink, *tlink; /分别为弧头和弧尾 相同的弧的链域*/ InfoType info; /*该弧相关信息的指针*/ ArcBox; typedef struct VexNode VertexType data: Ar

15、cBox *fisrin, *firstout; /*分别指向该顶点第一条入弧和出弧*/ VexNode; typedef struct VexNode xlistMAX_VERTEX_NUM; /*表头向量*/ int vexnum , arcnum; /*有向图的顶点数和弧数*/ OLGraph;,29,Status CreateDG(OLGraph / 输入弧含有相关信息，此略 / CreateDG,算法7.3采用十字链表存储表示，构造有向图G,30,7.2.4邻接多重表,邻接多重表(Adjacency Multilist)主要用于存储无向图。因为，如果用邻接表存储无向图，每条边的两个边

16、结点分别在以该边所依附的两个顶点为头结点的链表中，这给图的某些操作带来不便。例如，对已访问过的边做标记，或者要删除图中某一条边等，都需要找到表示同一条边的两个结点。因此，在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。,31,32,33,邻接多重表存储表示的形式描述如下： #define MAX_VERTEX_NUM 20 typedef emnu unvisited,visited VisitIf; typedef struct EBox VisitIf mark: /*访问标记*/ int ivex , jvex; /*该边依附的两个顶点的位置*/ struct EBox

17、 *ilink , *jlink; /*分别指向依附这两个顶点的下一条边*/ InfoType info; /*该边信息指针*/ EBox; typedef struct VexBox VertexType data; EBox *fistedge; /*指向第一条依附该顶点的边*/ VexBox; typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum , edgenum; /*无向图的当前顶点数和边数*/ AMLGraph;,34,7.3 图的遍历,从图中某一顶点出发访遍图中所有顶点，且使图中每一顶点仅被访问一次，这一过程称图的遍

18、历。 为了便于记录顶点有否访问过，设一个数组visitedn，当visitedi=1时表示顶点Vi已访问过；当 visiti=0时表示顶点Vi未访问过。 图的遍历包括：深度优先搜索和广度优先搜索。,35,深度优先搜索（depth_first_search),假定给定G的初态是所有顶点匀未曾访问过，在G中任选一顶点Vi为初始出发点，则深度优先搜索可定义如下： 首先，访问出发点Vi，并将其标记为已访问过，然后，依此从Vi出发搜索Vi的某一个邻接点Vj，若Vj未曾访问过，则以Vj为新的出发点继续进行深度优先搜索；重复上述过程，直到图中所有顶点都被访问过为止。,36,/ 算法7.4 对图G作深度优先遍

19、历。 bool VisitedMAX; Status (*VisitFunc)(int v) void DFSTraverse(Graph G, Status (*Visit)(int v) VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = false; for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS void DFS(Graph G, int v) / 算法7.5 visitedv = true; VisitFunc(v); / 访问第v个顶点 f

20、or (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w) if (!visitedw) DFS(G, w); ,37,深度优先搜索的时间复杂度 如采用邻接矩阵存储，则时间复杂度为:O(n2) 如采用邻接表存储存储，则时间复杂度为:O(ne),38,连通图深度优先搜索举例（矩阵表示）,39,/图的结构 typedef struct vextype vexsn; adjtype arcsnn; graph;,40,/*从Vi+1出发深度优先搜索图g，g用邻接矩阵表示*/ int visitedn ; /全局变量 graph g ; /全局变量 DF

21、S( int i ) int j; printf(“node:%cn”,g.vexsi); visitedi=1; for (j=0;jn;j+) if (g.arcsij=1) /递归调用 ,41,连通图深度优先搜索举例（邻接表）,无向图如下： 该图的邻接表如下：,该图的遍历顺序为：,42,typedef struct node int adjvex; struct node *next; edgenode; typedef struct vextype vertex; edgenode *link; vexnode;,42,43,/*从Vi+1出发深度优先搜索图gl，gl用邻接表表示*/

22、vexnode gln DFSL(int i ) int j; edgenode *p; printf(“node:%cn”,gli.vertex); visitedi=true; p=gli.link; while(p!=null) if (!visited p-adjvex) DFSL(p-adjvex); /递归调用 p=p-next; ,44,广度优先搜索（breadth-first-search),从图中某顶点Vi出发，在访问了Vi之后依次访问Vi的各个未曾访问过的邻接点，再依次从这些邻接点出发广度搜索遍历图，直至图中所有的顶点都访问过。,45,void BFSTraverse(Gr

23、aph G, Status (*Visit)(int v ) for (v=0; v=0; w=NextAdjVex(G, u, w) if (!visitedw) / u的尚未访问的邻接顶点w入队列Q visitedw = TRUE; Visit(w); EnQueue(Q, w); /if /while /if / BFSTraverse,算法7.6 按广度优先非递归遍历图G。,46,连通图广度优先搜索举例（矩阵表示）,0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0

24、0 0 0 0 1 0,该图广度优先的遍历序列为：,A=,47,从上可以看出：先访问的顶点其邻接点也先被访问，因此，需引进队列保存已访问过的顶点。,48,/*从 Vk+1出发广度优先搜索图g，g用邻接矩阵表示*/ graph g BFS(int k) int i,j; setnull(Q); printf(“%cn”,g.vexsk); visitedk=1; enqueue(Q,k); /入队 While (!empty(Q) i=dequeue(Q); for (j=0;jn;j+) if (g.arcsij= =1) /入队 ,49,连通图广度优先搜索举例（邻接表表示）,无向图如下：,该

25、图广度优先的遍历序列为：,50,vexnode gln BFSL(int k) /*从Vk+1出发广度优先搜索图gl，gl用邻接表表示*/ int i; edgenode *p; setnull(Q); printf(“%cn”,glk.vertex); visitedk=1; enqueue(Q,k); /入队 while(!empty(Q) i=dequeue(Q); p=gli.link; /从队列中出队头结点 while(p!=NULL) /一直访问到指针为空 if (!visitedp-adjvex) printf(“%cn”,glp-adjvex.vertex); visitedp

26、-adjvex=1; enqueue(Q,p-adjvex); p=p-next; ,51,判定一个图的连通性是图的一个应用问题，我们可以利用图的遍历算法来求解这一问题。,7.4 图的连通性问题,7.4.1 无向图的连通分量和生成树,生成树：一个连通图的生成树是一个极小连通子图，它包含图中全部顶点，但只有足以构成一棵树的n-1条边。,52,设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G)，其中T(G)是遍历图过程中历经的边的集合；B(G)是剩余的边的集合。显然，T(G)和图G中所有顶点一起构成连通图G的极小连通子图。按生成树的定义，

27、它是连通图的一棵生成树，并且由深度优先搜索得到的为深度优先生成树；由广度优先搜索得到的为广度优先生成树。,53,typedef struct CSNode ElemType data; struct CSNode *firstchild,*nextsibling; CSNode,*CSTree;,孩子兄弟表示法 又称二叉树表示法，或二叉链表表示法。即以二叉链表作为树的存储结构。 链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。,参考书P137,图6.15,54,void DFSTree(Graph G, int v, CSTree /if / DFSTree,算法7.8从第

28、v个顶点出发深度优先遍历图G，建立以T为根的生成树,55,void DFSForest(Graph G, CSTree / 建立以p为根的生成树 /if / DFSForest,算法7.7 建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T,56,7.4.2有向图的强连通分量,深度优先搜索是求有向图的强连通分量的一个有效方法。假设以十字链表作有向图的存储结构，则求强连通分量的步骤如下： （1）在有向图G上，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成(即退出DFS函数)的顺序将顶点排列起来。 此时需对7.3.1 中的算法作如下两点修改：（a）在进

29、入DFSTraverse 函数时首先进行计数变量的初始化，即在入口处加上count=0的语句；（b）在退出 函数之前将完成搜索的顶点号记录在另一个辅助数组finishedvexnum 中，即在函数DFS结束之前加上finished+count=v 的语句。,57,（2）在有向图G上，从最后完成搜索的顶点（即finishedvexnum-1中的顶点）出发，沿着以该顶点为头的弧作逆向的深度搜索遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先搜索遍历，依次类推，直至有向图中所有顶点都被访问到为止。 此时调用DFSTraverse 时需作如下

30、修改：函数中第二个循环语句的边界条件应改为v从finishedvexnum-1至finished0。,58,例如从顶点v1出发作深度优先搜索遍历，得到finished数组中的顶点号为(1,3,2,0) ；则再从顶点v1出发作逆向的深度优先搜索遍历，得到两个顶点集 v1, v3, v4和 v2，这就是该有向图的两个强连通分量的顶点集。,59,在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G，若边集E(G)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G是原图G的生成树（Spanning tree）。 生成树有如下特点：任意两个顶点之间有且仅有一条路径；如果再增加一条边就

31、会出现环路；如果去掉一条边此子图就会变成非连通图。,7.4.3最小生成树,60,对于带权的连通图（连通网）G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（Minimum Spanning Tree）。 具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路）。,61,最小生成树应用举例,假设要在n个城市之间建立通信联络图，则连通n个城市只需n-1条线路，如何在最节省的前提下建立这个通信网。 通信网表示n个城市及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，边上的权

32、值表示代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网，其中总的费用最少的那棵生成树就叫最小生成树（minimum cost spanning tree)。,62,举例：,最小生成树,网络,63,如何构造最小生成树,构造生成树的算法是利用了最小生成树的MST(Minimum Spanning Trees)的性质： 假设N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中，uU，vV-U，则必存在一棵包含边(u,v)的最小生成树。 利用MST性质构造最小生成树的算法有：普里姆Prim算法 和 克鲁斯卡尔Krus

33、kal算法.,64,MST性质的证明： 假设T是G的一棵最小生成树，但不包含（u,v）,由于T是一棵树，所以从u到v一定有一条路径，不妨设该路径通过(u,v),给该路径再加上（u, v）就构成回路，把该回路中的(u,v)边去掉，又是一棵新的生成树 T ,由于（u,v） 小于等于(u,v)，所以生成树T 的权也一定小于等于T的权。,65,Prim算法,假设G=(V,E)是一个具有n 个顶点的连通网络，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。 算法开始时，首先从V中任取一个顶点（假定为V1），将此顶点并入U中，此时最小生成树顶点集U=V1； 然后

34、从那些其一个端点已在U中，另一个端点仍在U外的所有边中，找一条最短（即权值最小）的边，假定该边为(Vi,Vj),其中ViU，VjV-U,并把该边(Vi,Vj)和顶点Vj分别并入T的边集TE和顶点集U；,66,如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后，把所有n 个顶点都并入生成树T的顶点集U中，此时U=V，TE中包含有（n-1）条边；这样，T就是最后得到的最小生成树。 普里姆算法中每次选取的边两端，总是一个已连通顶点（在U集合内）和一个未连通顶点（在U集合外），故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。,67,最小生成树的构造过程举例,用普里姆算法：,1,

35、2,6,3,1,4,5,5,6,68,Prim算法（程序描述）,typedef struct int fromvex, endvex; /*边的起点和终点*/ float length; /*边的权值*/ edge; float distnn; /*带权值的邻接矩阵*/ edge Tn-1; /*生成树*/,69,70,k=2,k=5,k=3,71,k=1,72,void MiniSpanTree_PRIM(MGraph G, VertexType u) / 算法7.9 / 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。 / 记录从顶点集U到VU的代价最小的边的辅助数组定

36、义： / struct / VertexType adjvex; / VRType lowcost; / closedgeMAX_VERTEX_NUM; int i,j,k; k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k) closedgej.adjvex=u; closedgej.lowcost=G.arcskj.adj; closedgek.lowcost = 0;,73,for (i=1; iG.vexnum; +i) / 选择其余G.vexnum-1个顶点 k = minimum(closed

37、ge); / 求出T的下一个结点：第k顶点 printf(closedgek.adjvex, G.vexsk);/ 输出生成树的边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) if (G.arcskj.adj closedgej.lowcost) / 新顶点并入U后重新选择最小边 closedgej.adjvex=G.vexsk; closedgej.lowcost=G.arcskj.adj; / MiniSpanTree,74,该算法中每一步执行都要扫描数组closedge，在V-U顶点集中找出与U最近的顶点，令其为v

38、，然后将v加入U顶点集合中，并修改数组closedge的adjvex和lowclost。 在Prim算法中，第一个for循环的执行次数为n1，第二个for循环中又包括了两个for循环，执行次数约为2(n-1)2，所以Prim算法的时间复杂度为 O(n2) 。,算法分析,75,Kruskal算法,假设G =（V，E）是一个具有n个顶点的连通网络，T=(U,TE)是G 的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。 基本思想：将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成环路，则把它并入TE中，保留作为生成树T的一条边，若选取的边使生成树T形成环路，

39、则将其舍弃，如此进行下去，直到TE中包含n-1条边为止。此时的T即为最小生成树。,76,克鲁斯卡尔算法举例,1,2,3,5,6,4,1,1,2,3,4,6,5,1,2,1,4,6,5,2,3,1,2,3,1,3,4,6,5,2,1,2,3,4,77,#define MAXEDGE typedef struct elemtype v1; elemtype v2; int cost; EdgeType; EdgeType edgesMAXEDGE;,在结构数组edges中，每个分量edgesi代表网中的一条边，其中edgesi.v1和edgesi.v2表示该边的两个顶点，edgesi.cost表示

40、这条边的权值。为了方便选取当前权值最小的边，事先把数组edges中的各元素按照其cost域值由小到大的顺序排列。,78,int Find（int father ，int v）/*寻找顶点v所在树的根结点*/ int t; t=v; while(fathert=0) t=fathert; return(t); ,在对连通分量合并时，采用集合的合并方法。对于有n个顶点的网，设置一个数组fathern，其初值为fatheri= -1（i1，2,，n），表示各个顶点在不同的连通分量上，然后，依次取出edges数组中的每条边的两个顶点，查找它们所属的连通分量，假设vf1和vf2为两顶点所在的树的根结点在

41、father数组中的序号，若vf1不等于vf2，表明这条边的两个顶点不属于同一分量，则将这条边作为最小生成树的边输出，并合并它们所属的两个连通分量。,79,void Kruskal（EdgeType edges ，int n） /*用Kruskal方法构造有n个顶点的图edges的最小生成树*/ int fathern+1; int i,j,vf1,vf2; for (i=0;i=n;i+) fatheri= -1; i=0;j=0; while(iMAXEDGE ,80,int Find（int father，int v） int t; t=v; while(fathert=0) t=fat

42、hert; return(t); ,81,在Kruskal算法中，第二个while循环是影响时间效率的主要操作，其循环次数最多为MAXEDGE次数，其内部调用的Find函数的内部循环次数最多为n，所以Kruskal算法的时间复杂度为O（nMAXEDGE）,82,7.4.4 关节点和重连通分量,假若在删去顶点v 以及和v相关联的各边之后，将图的一个连通分量分割成两个或两个以上的连通分量，则称顶点v为该图的一个关节点(articulation point) 。 一个没有关节点的连通图称为重连通图(biconnected graph) 。在重连通图上，任意一对顶点之间至少存在两条路径。 若在连通图上

43、至少删去k个顶点才能破坏图的连通性，则称此图的连通度为 k。,83,利用深度优先搜索便可求得图的关节点，并由此可判别图是否是重连通的。 由深度优先生成树可得出两类关节点的特性： （1）若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点。因为图中不存在联结不同子树中顶点的边，因此，若删去根顶点，生成树便变成生成森林。如图7.20(b)(P177) 中的顶点A。 （2）若生成树中某个非叶子顶点v，其某棵子树的根和子树中的其它结点均没有指向v的祖先的回边，则v为关节点。因为，若删去v，则其子树和图的其它部分被分割开来。如图7.20(b)中的顶点B，D和G 。,84,85,为实现对上类关键点的判

44、断，我们引入下面两个辅助数组：,visitedv：为深度优先搜索遍历连通图时访问顶点 v的次序号；,若对于某个顶点v，存在孩子结点w且loww visitedv，则该顶点v必为关节点。因为当w是v的孩子结点时，lowwvisitedv，表明w 及其子孙均无指向v的祖先的回边。,86,求关键点对应的算法7.10与算法7.11,上述算法的过程就是一个遍历的过程，因此，求关节点的时间复杂度仍为 O(n+e)。,87,7.5有向无环图及其应用,一个无环的有向图称做有向无环图（directed acyclic Graph）。简称DAG图。 利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。 有

45、向无环图是描述一项工程或系统的进行过程的有效工具。几乎所有的工程（project）都可分为若干个称作活动（activity）的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。,88,7.5.1 拓扑排序,问题的提出 AOV网 拓扑排序 算法描述 算法实现,89,-问题的提出-,在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系： 先后关系； 子项目之间无次序要求。,90,学校里某个专业的课程学习：,-问题的提出-,91,这些类似的问题都可以用有向无环图来表示，我们把这些子项目、课程看成一个个顶点称之为活动(Activ

46、ity)。,-问题的提出-,92,AOV网络：用顶点表示活动，用弧表示活动的先后顺序，即用顶点Vi到Vj之间存在的有向边表示活动 i 必须先于活动 j 进行；这种图称做顶点表示活动的网络(Activity On Vertex network,简称AOV网络)。,-AOV网-,93,在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。,-AOV网-,94,AOV网络中一定不能存在有向环路。 例如：下图的有向环路中， V1是V2的前趋顶点， V2是V3的前趋顶点，V3又是V1的前趋顶点，顶点之间的先后关系进入

47、了死循环。,-AOV网-,95,对于一个给定的AOV网应首先判定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有的顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。,-AOV网-,96,拓扑排序： 将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。,-拓扑排序-,97,拓扑排序：从某集合上的一个偏序关系得到全序关系的操作。,-拓扑排序-,v1,v2,v4,v3,偏序关系 全序关系,98,(1) 在网络中选择一个没有前趋的顶点，并把它输出； (2) 从网络中删去该顶点和从该顶点发出的所有有向边； (3) 重复执行上述两步，直到网中所有的顶点都被输出 (此时，原AOV网络中的所有顶点和边就都被删除掉了)。,拓扑排序方法：,-拓扑排序-,99,(1) 在网络