数据结构图结构-(动态PPT).ppt

《数据结构图结构-(动态PPT).ppt》由会员分享，可在线阅读，更多相关《数据结构图结构-(动态PPT).ppt（141页珍藏版）》请在三一办公上搜索。

1、1,本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该：1)了解图的定义和术语 2)掌握图的各种存储结构 3)掌握图的深度优先搜索和广度优先搜索遍历算法 4)理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法,本章学习导读,2,图（Graph）是一种较线性表和树更为复杂的非线性结构。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。然而在图形结构

2、中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。,3,7.1 图的定义 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径,第七章 图,4,图定义 图G由两个集合V和E组成，记为 G=(V,E)其中，V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。通常V(G)和E(G)分别称为图的顶点集合和边集合。注：E(G)可以为空集。,

3、7.1 图的定义和术语,5,7.1 图的定义和术语,图的数据结构的形式化定义（p156）,G=(V,E)其中 V=x|x dataobject E=VR VR=|p(x,y)(x,y V)VR是两顶点间的关系的集合，即边的集合。,6,图的术语,有向图:对一个图G，若边集E(G)为有向边的集合，则称该图为有向图。,G1=（V，E）V=v1,v2,v3,v4E=,其中表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head),x弧尾,y弧头,7,图的术语,无向图:对一个图G，若边集E(G)为无向边的集合，则称该图为无向图。,G2=（V，E）V=v1,v2,v3,v4,v

4、5E=(v1,v2),(v1,v3),(v2,v3),(v3,v4),(v2,v5),(v3,v5)其中，(x,y)表示x与y之间的一条连线，称为边（edge）,8,图的术语,设n为顶点数，e为边或弧的条数 对无向图有：0 e n(n-1)/2 有向图有：0 e n(n-1),证明：对有向图，每个顶点至多有n-1条边与其它的n-1个顶点相连，则n个顶点至多有n(n-1)条边。但对无向图，每条边连接2个顶点，故最多为n(n-1)/2,9,图的术语,端点和邻接点 在一个无向图中，若存在一条边,则称vi，vj为该边的两个端点，并称它们互为邻结点。,10,图的术语,起点和终点 在一个有向图中，若存在一

5、条边,则称该边是顶点vi的一条出边，是vj的一条入边，称vi是起始端点（或起点），称vj是终止端点（或终点）,并称它们互为邻结点.,11,图的术语,度 图中每个顶点的度是以该顶点为一端点的边的数目。记为 D(V)。入度和出度 对于有向图，入度为以该顶点为终点的边的数目，出度为以该顶点为起点的边的数目。,例 D(v1)=3,无向图的度数为依附于顶点v的边数；有向图的度数等于以顶点v 为弧头的弧数与以顶点v为弧尾的弧数之和,例 D(v1)=2,12,图的术语,子图 设有两个图G=（V，E）G=（V，E）中，若V是V的子集，E是E的子集，则称G是G子图。,13,图的术语,简单图 对不含多重边和自环的

6、图。,简单图,非简单图,14,图的术语,完全图 边达到最大的图,无向完全图：具有n(n-1)/2条边的简单图称为无向完全图 有向完全图：具有n(n-1)条边的有向图。稀疏图：边或弧很少的图。稠密图：边或弧很多的图。权：与图的边或弧相关的数。网：边或弧上带有权值的图。,15,图的术语,路径 非空有限点、弧交替序列，W=v0,a1,v1,ak,vk 使得i=1,2,k,弧ai的头vi,尾为vi-1。,路径长度：路径上边或弧的数目,16,图的术语,简单路径：除首尾两点外，其他各点都不相同的路径称为简单路径。,简单路径,17,图的术语,回路:无重复边的闭路径。,环：闭的简单路径，称为环。,回路但不是环

7、,环,18,图的术语,连通图：任何两点都有路径的图。无向图：若图中任意两个顶点vi,vj都是连通 的，则称该图是连通图(vivj)有向图：若图中任意两个顶点vi,vj，都存在 从vi到vj 和从 vj到vi的路径，则称 该有向图为强连通图(vivj),19,图的术语,连通分量：无向图：无向图中极大连通子图，称为 连通分量 有向图：有向图中极大强连通子图，称为 强连通分量,20,生成树,图的术语,生成树 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。,有向树 如果一个有向图恰有一个顶点入度为0，其余顶点的入度均为1，则是一棵有向树。,21,生成树、生

8、成森林生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的 是连通图的极小连通子图 包含图中的所有顶点 有且仅有n-1条边 非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。,一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。,22,图有两种存储结构 邻接矩阵 邻接表,7.2 图的存储结构,23,7.2.1 邻接矩阵 邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的

9、n阶方阵。,7.2 图的存储结构,无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。在有向图中：第 i 行 1 的个数就是顶点 i 的出度，第 j 列 1 的个数就是顶点 j 的入度。在无向图中,第 i 行(列)1 的个数就是顶点i 的度。,24,一、邻接矩阵（用二维数组表示）,例如：G1的邻接矩阵,例如：G2的邻接矩阵,无向图的邻接矩阵为对称矩阵,25,对于无向图，（vi，vj）和（vj，vi）表示同一条边，因此，在邻接矩阵中Aij=Aji。无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。对有向图，弧和表示方向不同的两条弧，Aij和Aji表

10、示不同的弧，所以有向图的邻接矩阵一般不具有对称性。邻接矩阵表示法适合于以顶点为主的运算。,26,对于有向图，顶点vi的出度OD(vi)等于邻接矩阵第i行元素之和；顶点vi的入度ID(vi)等于邻接矩阵第i列元素之和，即：,对于无向图，顶点vi的度等于邻接矩阵第i行的元素之和，即：,OD(vi)=,ID(vi)=,TD（vi）=,27,若G是网（有权图），邻接矩阵定义为,如图：,Wij 若 或 E(G)A i，j=0或 若其它,28,顶点表:一个记录各个顶点信息的一维数组，邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示

11、图的顶点之间关系（边或弧）的集合，数据类型定义如下：#define MAX_VERTEX_NUM 20/最大顶点数typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵类型typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点表AdjMatrix arcs;/邻接矩阵int vexnum，arcnum;/图的顶点数和弧数 MGraph;由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。,29,邻接表 图的链式存储结构 1)为每个顶点建立一个单链表，2)第i

12、个单链表中包含顶点Vi的所有邻接顶点。邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。,30,1.无向图邻接表,31,2.有向图邻接表,如图G1的邻接表为：,32,在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。建立邻接表的时间复杂度为O(n*e)。若顶点信息即为

13、顶点的下标，则时间复杂度为O(n+e)。,33,存储表示typedef struct ArcNodeint adjvex;/该弧所指向的顶点的位置struct ArcNode*nextarc;/指向下一条弧的指针 int*info;/该弧相关信息的指针 ArcNode;/边结点类型typedef struct VNodeVertexType data;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;/邻接表typedef structAdjList vertices;int vexnum,arcnum;/图的当

14、前顶点数和弧数 int kind;/图的种类标志ALGraph;,34,1.无向图邻接表,二、邻接表,35,1.无向图邻接表,对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域.,其中：邻接点域（adjvex）记载与顶点Vi邻接的顶点信息；链域（nextarc）指向下一个与顶点Vi邻接的链表p结点,每个链表设一个头结点，头结点结构为：,其中：vexdata存放顶点信息（姓名、编号等）；firstarc指向链表的第一个结点。,二、邻接表,36,二、邻接表（adjacency list）,如图G2的邻接表为：,37,B,A,C,D,F,E,例 2,38,2.

15、有向图邻接表,特点：1.n个顶点，e条弧的有向图，需n个表头结点，e 个表结点 2.第 i 条链表上的结点数，为 Vi 的出度（求顶点的出度易，求入度难）,如图G1的邻接表为：,39,1 4,2,3,0 1,2,0 1 2 3 4,A B C D E,2.有向图的邻接表,A,B,E,C,F,可见，在有向图的邻接表中不易找到指向该顶点的弧。,40,3.有向图逆邻接表,此时，第i条链表上的结点数，为Vi的入度,如图G1的逆邻接表为：,G1,41,A,B,E,C,D,有向图的逆邻接表,A B C D E,3,0,3,4,2,0,01234,在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。,在

16、有向图的邻接表中，第 i 个链表中结点的个数是顶点Vi的出度。在有向图的逆邻接表中，第 i 个链表中结点的个数是顶点Vi 的入度。,42,4.带权有向图的邻接表,链表中每个结点为三个域.,带权图的边结点中info保存该边上的权值。,43,A,B,E,C,D,4.带权有向图的邻接表,01234,10,2,25,4,8,3,7,顶点 Vi 的边链表的头结点存放在下标为 i 的顶点数组中。,44,十字链表 十字链表(Orthogonal List)是有向图的另一种链式存储结构。可看作是将有向图的邻接表和逆邻接表结合的一种链表。在十字链表中，为每个顶点vi设置一个结点，它包含数据域data和两个链域f

17、irstout、firstin，称为顶点结点。数据域data用于存放顶点vi的有关信息；链域firstin指向以顶点vi为弧头的第一个弧结点；链域firstout指向以顶点vi为弧尾的第一个弧结点。弧结点包括四个域：尾域tailvex、头域headvex，链域hlink和tlink。hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧；data顶点信息，firstin以该顶点为头的第一个弧结点，firstout以该结点为尾的第一个弧结点。,弧结构,顶点结构,45,图7-8 十字链表,图7-8为图7-6(a)有向图的十字链表。见右图,采用十字链表表示有向图，很容易找到以顶点vi为弧

18、尾的弧和以顶点vi为弧头的弧，因此顶点的出度、入度都很容易求得。,46,十字链表的数据类型定义如下：#define MAXV typedef struct Arcbox/弧结点 int tailvex,headvex;/弧尾和弧头顶点位置 struct ArcNode*hlink,*tlink;/弧头相同和弧尾相同的弧的链域ArcBox;typedef struct VexNode/顶点结点 VertexType data;/顶点信息 ArcNode*firstin,*firstout;/分别指向该顶点的第一条入弧和出弧VexNode;,47,7.2.4 邻接多重表 邻接多重表是无向图的另一种

19、链式存储结构。在邻接多重表中设置一个边结点表示图中的一条边。边结点包含五个域，结构如下所示：,其中:mark 域 标志域，用于对该边进行标记；ivex 域 存放该边依附的一个顶点vi的位置信息；ilink 域 该链域指向依附于顶点vi的另一条边的边结点；jvex 域 存放该边依附的另一个顶点vj的位置信息；jlink 域 该链域指向依附于顶点vj的另一条边的边结点。邻接多重表为每个顶点设置一个结点，其结构如下：,48,图7-9 邻接多重表,图7-9为图7-5(a)无向图的邻接多重表。,由邻接多重表可以看出，表示边（vi，vj）的边结点通过链域ilink和jlink链入了顶点vi和顶点vj的两个

20、链表中，实现了用一个边结点表示一个边的目的，克服了在邻接表中用两个边结点表示一个边的缺点。因此邻接多重表是无向图的一种很有效的存储结构。,49,邻接多重表的结点数据类型定义如下：#define MAXV typedef struct/边结点类型 int mark;/访问标识 int ivex,jvex;/该边的两个顶点位置信息 struct Enode*ilink,*jlink;/分别指向依附这两个顶点的下一条边Enode;typedef struct/顶点结点类型 VertexType data;/顶点数据域 ENode*firstedge;/指向第一条依附该顶点的边Vnode;,50,7.

21、3 图的遍历,和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历。(Traversing Graph)。,图的遍历远比树的遍历复杂。因为从树根到达树的某个结点只有一条路径，而图的两个顶点之间可能有多条路径。,因此，在图的遍历过程中，可能会出现下面的现象，即在顺着一条路径访问了某个顶点后，可能会沿着另一条路径又回到该顶点。,为避免一个顶点被多次访问，我们设置一个标志数组int visitedMAX_VERTEX_NUM;它的元素初值为0。一旦vi被访问了，便置相应数组元素为1.,图的遍历方法有：,这两种方法对无向图和有向图都适用。,51,深度优先搜索（D

22、FS）1 深度优先搜索遍历过程：DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从w1出发，访问与 w1邻接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,52,深度优先搜索的示例,图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后

23、可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited i 为 1，防止它被多次访问。,53,对上图，深度优先搜索遍历的顺序（之一）为：v1 v2v4 v8 v5v6v3v7。,图7-10 深度优先搜索,54,深度优先搜索算法：int visitedMAX_VERTEX_NUM;void DFS(ALGraph G,int v)ArcNode*p;printf(%c,G.verticesv.data);visitedv=1;p=G.verti

24、cesv.firstarc;while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-nextarc;/从第v个顶点出发DFS,55,整个图的DFS遍历void DFSTraverse(ALGraph G)for(int v=0;vG.vexnum;+v)visitedv=0;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);对于连通图，从一个顶点出发，调用DFS函数即可将所有顶点都遍历到。,56,广度优先搜索（BFS）1 广度优先搜索思想 广度优先搜索遍历类似于树的按层次遍历。对于无向连通图，广度优先搜索是从图的某个顶

25、点v0出发，在访问v0之后，依次搜索访问v0的各个未被访问过的邻接点w1，w2，。然后顺序搜索访问w1的各未被访问过的邻接点，w2的各未被访问过的邻接点，。即从v0开始，由近至远，按层次依次访问与v0有路径相通且路径长度分别为1，2，的顶点，直至连通图中所有顶点都被访问一次。广度优先搜索的顺序不是唯一的，例如图7-10(a)连通图的广度优先搜索遍历顺序可为v1，v2，v3，v4，v5，v6，v7，v8 也可为v1，v3，v2，v7，v6，v5，v4，v8。,57,广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索

26、中需要设置一个队列Queue，使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点。,广度优先搜索过程 广度优先生成树,广度优先搜索的示例,58,广度优先搜索过程可描述为：（1）f=0;r=0;/队列初始化，空队列；f-队首指针，r-队尾指针（2）访问v0;（3）visitedv0=1;（4）insert(Queue,f,r,v0);/v0进入队尾（5）while f0 do(i)delete(Queue,f,r,x);/队首元素出队并赋于x(ii)对所有x的邻接点w if visitedw=0 then（a）访问w

27、;（b）visitedw=1;（c）insert(Queue,f,r,w);/w进队列,59,void BFSseach(Graph G,int Visited,int n)for(v=0;vn;+v)visitedv=0;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;vG.vexnum;+v)if(!visitedv)/v 尚未访问 visitedv=1;Visit(v);/访问u EnQueue(Q,v);/v入队列 while(!QueueEmpty(Q)u=DeQueue(Q,u);/队头元素出队并置为u for(w=FirstAdjVex(G,u);

28、w!=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=1;Visit(w);EnQueue(Q,w);/访问的顶点w入队列/if/while/BFSTraverse,60,课堂练习,练习1、写出右图的邻接矩阵表示。,61,课堂练习,练习2、写出右图的邻接表表示。,62,课堂练习,练习3、根据右图的如下存储表示，写出以顶点A为出发点进行DFS的顶点访问序列。,A，B，D，E，F，C,63,课堂练习,A，B，C，D，E，F,练习4、根据右图的如下存储表示，写出以顶点A为出发点进行BFS的顶点访问序列。,64,使用不同的遍历图的方法，可以得到不同的生成树；从不同

29、的顶点出发，也可能得到不同的生成树。按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。构造最小生成树的准则必须使用且仅使用该网络中的n-1 条边来联结网络中的 n 个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。,7.4 最小生成树,65,普里姆(Prim)算法,普里姆算法的基本思想：从连通网络 N=V,E 中的某一顶点 u0 出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合 U 中。如此继续下去,直到网络中的

30、所有顶点都加入到生成树顶点集合 U 中为止。采用邻接矩阵作为图的存储表示。,66,25,25,10,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,原图(a)(b),5,0,4,6,1,3,2,10,(c)(d)(e)(f),5,0,4,6,1,3,2,10,22,12,5,0,4,6,1,2,10,25,14,22,16,12,3,25,22,12,67,普里姆(Prim)算法,在构造过程中，还设置了两个辅助数组：lowcost 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；nearv

31、ex 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,68,普里姆(Prim)算法,若选择从顶点0出发，即u0=0，则两个辅助数组的初始状态为：,0 28 10,-1 0 0 0 0 0 0,lowcost,nearvex,0 1 2 3 4 5 6,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,69,然后反复做以下工作在 lowcost 中选择 nearvexi-1&lowcosti最小的边,用 v 标记它。则选中的权值最小的边为(nearvexv,v),相

32、应的权值为 lowcostv。将 nearvexv 改为-1,表示它已加入生成树顶点集合,将边(nearvexv,v,lowcostv)加入生成树的边集合。取 lowcosti=min lowcosti,Edgevi，即用生成树顶点集合外各顶点 i 到刚加入该集合的新顶点 v 的距离 Edgevi 与原来它们到生成树顶点集合中顶点的最短距离lowcosti 做比较,取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。如果生成树顶点集合外顶点 i 到刚加入该集合的新顶点 v 的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改nearvexi:nearvexi=v。表示生成树外

33、顶点i到生成树内顶点v当前距离最近。,70,0 28 10,-1 0 0 0 0 0 0,lowcost,nearvex,0 1 2 3 4 5 6,选 v=5,选边(0,5),71,顶点v=5加入生成树顶点集合：,0 28 25 10,-1 0 0 0 5-1 0,lowcost,nearvex,0 1 2 3 4 5 6,选 v=4,选边(5,4),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(0,5,10)加入生成树,12,0,4,6,1,3,2,10,25,5,72,0 1 2 3 4 5 6,顶点v=4加入生成树顶点集合：,0 28 22 25

34、 10 24,-1 0 0 4-1-1 4,lowcost,nearvex,选 v=3,选边(4,3),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(5,4,25)加入生成树,12,5,0,4,6,1,3,2,10,25,22,73,顶点v=3加入生成树顶点集合：,0 28 12 22 25 10 18,-1 0 3-1-1-1 3,lowcost,nearvex,0 1 2 3 4 5 6,选 v=2,选边(3,2),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(4,3,22)加入生成树,12,5,0,4,6,1

35、,3,2,10,25,22,12,74,lowcost,nearvex,0 1 2 3 4 5 6,顶点v=2加入生成树顶点集合：,0 16 12 22 25 10 18,-1 2-1-1-1-1 3,选 v=1,选边(2,1),5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(3,2,12)加入生成树,12,5,0,4,1,3,2,10,25,22,16,12,75,顶点v=1加入生成树顶点集合：,0 16 12 22 25 10 14,-1-1-1-1-1-1 1,lowcost,nearvex,0 1 2 3 4 5 6,选 v=6,选边(1,6),5

36、,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(2,1,16)加入生成树,12,5,0,4,6,1,3,2,10,25,14,22,16,12,76,lowcost,nearvex,0 1 2 3 4 5 6,顶点v=6加入生成树顶点集合：,0 16 12 22 25 10 14,-1-1-1-1-1-1-1,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图 边(1,6,14)加入生成树,12,5,0,4,6,1,3,2,10,25,14,22,16,12,最后生成树中边集合里存入得各条边为：(0,5,10),(5,4,25)

37、,(4,3,22),(3,2,12),(2,1,16),(1,6,14),77,采用邻接表作为存储结构：设置一个辅助数组closedge：lowcost域 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；即存放在V-U中各个顶点到集合U中的当前最小权值；adjvex域 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。即记录该边所依附的在U中的顶点。,78,利用普里姆算法建立最小生成树:-了解（P175）typedef int VRType;structVertexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;

38、void MiniSpanTree_PRIM(MGraph G,VertexType u)int k,j,i,minCost;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)if(j!=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj;,79,closedgek.lowcost=0;for(i=1;iG.vexnum;+i)k=minimum(closedge);minCost=INFINITY;for(j=0;jG.vexnum;+j)if(closedgej.lowcost minCost,80,普里姆算法中的第二个

39、for循环语句频度为n-1，其中包含的两个内循环频度也都为n-1，因此普里姆算法的时间复杂度为O(n2)。普里姆算法的时间复杂度与边数e无关，该算法更适合于求边数较多的带权无向连通图的最小生成树。,81,克鲁斯卡尔(Kruskal)算法,克鲁斯卡尔算法的基本思想：设一个有 n 个顶点的连通网络 N=V,E,最初先构造一个只有 n 个顶点,没有边的非连通图 T=V,图中每个顶点自成一个连通分量。当在 E 中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中;否则将此边舍去，重新选择一条权值最小的边。如此重复下去,直到所有顶点在同一个连通分量上为止。,82,应

40、用克鲁斯卡尔算法构造最小生成树的过程,10,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,5,0,4,6,1,3,2,5,0,4,6,1,3,2,原图(a)(b),83,10,12,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,14,12,原图(c)(d),5,0,4,6,1,3,2,10,14,16,12,(e)(f)(g),5,0,4,6,1,3,2,10,14,22,16,12,5,0,4,6,1,2,10,25,14,22,16,12,3,84,为实现克

41、鲁斯卡尔算法需要设置一维辅助数组E，按权值从小到大的顺序存放图的边，数组的下标取值从0到e-1（e为图G边的数目）。了解-假设数组E存放图G中的所有边，且边已按权值从小到大的顺序排列。n为图G的顶点个数，e为图G的边数。克鲁斯卡尔算法如下：#define MAXE#define MAXV typedef struct int vex1;/边的起始顶点int vex2;/边的终止顶点int weight;/边的权值Edge;,85,Void kruskal(Edge E,int n,int e)int i,j,m1,m2,sn1,sn2,k;int vsetMAXV;for(i=0;in;i+)

42、/初始化辅助数组 vseti=i;k=1;/表示当前构造最小生成树的第k条边，初值为1 j=0;/E中边的下标，初值为0 while(ke)/生成的边数小于e时继续循环 ml=Ej.vex1;m2=Ej.vex2;/取一条边的两个邻接点 sn1=vsetm1;sn2=vsetm2;/分别得到两个顶点所属的集合编号 if(sn1!=sn2)/两顶点分属于不同的集合，该边是最小生成树的一条边,86,printf(“(m1，m2)：dn”,Ej.weight);k+;/生成边数增l for(i=0;in;i+)/两个集合统一编号 if(vseti=i)/集合编号为sn2的改为sn1 vseti=sn

43、1;j+;/扫描下一条边,如果给定带权无向连通图G有e条边，且边已经按权值递增的次序存放在数组E中，则用克鲁斯卡尔算法构造最小生成树的时间复杂度为O(e)。克鲁斯卡尔算法的时间复杂度与边数e有关，该算法适合于求边数较少的带权无向连通图的最小生成树。,87,7.有向无环图及其应用,、有向无环图的定义 有向无环图是描述一项工程或系统的进行过程的有效工具。因为几乎所有的工程均可以分为若干个称为活动的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。因此对整个工程和系统而言，最为关心的两个问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间

44、。对应于有向图，即是探讨拓扑排序和关键路径问题。,88,一个无环的有向图称作有向无环图(Directid Acycline Gragp)称为DAG图。,89,顶点 表示课程有向弧 若课程i是课程j的先决条件，则图中有弧,学生选修课程问题,90,AOV网 用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网。,拓扑排序 把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫,检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存

45、在环。,91,在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧,拓扑排序的方法,重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止,92,拓扑序列：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网的拓扑序列不是唯一的,93,94,95,96,97,98,算法实现,重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。,以邻接表作存储结构,把邻接表中所有入度为0的顶点进栈,栈非空时，输出栈顶元素Vj

46、并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈。,99,在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组，表头结点定义如下：typedef struct/表头结点 Vertex data;/顶点信息 int count;/存放顶点入度 ArcNode*firstarc;/指向第一条弧Vnode;,在执行拓扑排序的过程中，当某个顶点的入度为零(没有前驱顶点)时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，相当于删除所有以该

47、顶点为尾的弧。为了避免重复检测顶点的入度是否为零，需要设立一个栈来存放入度为零的顶点。执行拓扑排序的算法如下：,100,void topsort(VNode adj,int n)int i,j;int stackMAXV,top=0;/栈stack的指针为top ArcNode*p;for(i=0;i0)/栈不为空 i=stacktop;top-;/顶点vi出栈 printf(“d”,i);/输出vi p=adji.firstarc;/指向以vi为弧尾的第一条弧 while(p!=NULL)j=p-adjvex;/以vi为弧尾的弧的另一顶点vj,101,while(p!=NULL)j=p-ad

48、jvex;/以vi为弧尾的弧的另一顶点vj adjj.count-;/顶点vj的入度减1 if(adjj.count=0)/入度为0的相邻顶点入栈 top+;stacktop=j;p=p-nextarc;/指向以vi为弧尾的下一条弧,可见，对于有n个顶点和e条边的有向图而言，for循环中建立入度为0的顶点栈时间为O（n）；若在拓扑排序过程中不出现有向环，则每个顶点出栈、入栈和入度减1的操作在while(top0)循环语句中均执行e次，因此拓扑排序总的时间花费为O(n+e)。,102,例 设一个工程有11项活动，9个事件 事件V1表示整个工程开始 事件V9表示整个工程结束,AOE网（Activi

49、ty On Edge）,边表示活动,用顶点表示事件，弧表示活动，权表示活动持续的时间；,网中只有：唯一一个入度为0的点 源点 唯一一个出度为0的点 汇点,完成整项工程至少需要多少时间？,哪些活动是影响工程进度的关键？,7.5.2 关键路径,103,Ve(j)表示事件Vj的最早发生时间Vl(j)表示事件Vj的最迟发生时间ee(i)表示活动ai的最早开始时间el(i)表示活动ai的最迟开始时间 el(i)-ee(i)表示完成活动ai的时间余量关键活动就是时间余量el(i)-ee(i)0的活动,关键路径 路径长度最长的路径叫关键活动 关键路径上的活动叫,AOE网常用于表示工程的计划或进度。由于实际工

50、程只有一个开始点和一个结束点，同时AOE网应当是无环的。,104,如何找ee(i)=el(i)的关键活动？,设活动ai用弧表示，其持续时间记为：dut()则有：（1）ee(i)=Ve(j)（2）el(i)=Vl(k)-dut(),如何求Ve(j)和Vl(j)？,(1)从Ve(1)=0 开始向前递推,(2)从Vl(n)=Ve(n)开始向后递推,Ve(j)=从源点到顶点j的最长路径长度；,Vl(k)=从顶点k到汇点的最短路径长度。,105,V1V2V3V4V5V6V7V8V9,064577161418,0668710161418,a1a2a3a4a5a6a7a8a9a10a11,求关键路径步骤,求