《数据结构图》PPT课件.ppt

9.1 图的基本概念 第 9章 图 9.2 图的存储结构 9.3 图的遍历 9.4 生成树和最小生成树 9.5 最短路径 9.6 拓扑排序 本章小结 9.7 AOE网与关键路径 9.1 图的基本概念 9.1.1 图的定义 图 (Graph)G由两个集合 V(Vertex)和 E(Edge) 组成 ,记为 G=(V,E),其中 V是顶点的有限集合 ,记 为 V(G),E是连接 V中两个不同顶点 (顶点对 )的边 的有限集合 ,记为 E(G)。 在图 G中 ,如果代表边的顶点对是无序的 ,则称 G为 无向图 ,无向图中代表边的无序顶点对通常用圆括号 括起来 ,用以表示一条无向边 。 如果表示边的顶点对是有序的 ,则称 G为 有向图 ,在 有向图中代表边的顶点对通常用尖括号括起来 。 9.1.2 图的基本术语 1. 端点和邻接点 在一个无向图中 ,若存在一 条边 (vi,vj),则称 vi和 vj为此边的两 个端点 ,并称它们互为 邻接点 。 在一个有向图中 ,若存在一条 边 ,则称此边是顶点 vi的一 条出边 ,同时也是顶点 vj的一条入 边；称 vi和 vj分别为此边的起始端 点 (简称为起点 )和终止端点 (简称 终点 )；称 vi和 vj互为 邻接点 。 1 3 0 2 4 1 3 0 2 4 (a) (b ) 2. 顶点的度 、 入度和出度 在无向图中 ,顶点所具有的边的 数目称为该 顶点的度 。 在有向图中 ,以顶点 vi为终点的 入边的数目 ,称为该顶点的 入度 。 以 顶点 vi为始点的出边的数目 ,称为该 顶点的 出度 。 一个顶点的入度与出 度的和为该顶点的度 。 若一个图中有 n个顶点和 e条边 , 每个顶点的度为 di(1in),则有： 1 3 0 2 4 1 3 0 2 4 (a) (b ) n 1i id2 1e 3. 完全图 若无向图中的每两个顶点之间 都存在着一条边 ,有向图中的每两 个顶点之间都存在着方向相反的 两条边 ,则称此图为 完全图 。 显然 ,完全无向图包含有条边 , 完全有向图包含有 n(n-1)条边。 例如 ,图 (a)所示的图是一个具有 4 个顶点的完全无向图 ,共有 6条边。 图 (b)所示的图是一个具有 4个顶 点的完全有向图 ,共有 12条边。 1 0 2 3 1 0 2 3 (a) (b ) 4. 稠密图 、 稀疏图 当一个图接近完全图时 ,则称为 稠密图 。 相反 ,当一个图含有较少 的边数 (即当 en(n-1)时 ,则称为 稀疏图 。 5. 子图 设 有 两 个 图 G=(V,E) 和 G=(V,E),若 V是 V的子集 ,即 VV,且 E是 E的子集 ,即 EE,则 称 G是 G的 子图 。 例如图 (b)是图 (a)的子图 ,而图 (c)不是图 (a)的子 图 。 1 3 0 2 4 (a) (b ) 1 3 0 2 4 1 3 0 2 4 ( c ) 6. 路径和路径长度 在一个图 G=(V,E)中 ,从顶点 vi到顶点 vj 的 一 条 路 径 是 一 个 顶 点 序 列 (vi,vi1,vi2, ,vim,vj),若此图 G是无向图 ,则 边 (vi,vi1),(vi1,vi2), ,(vim-1,vim),(vim,vj)属于 E(G) ；若此图是有向图 , 则 , , 属 于 E(G)。 路径长度是指一条路径上经过的边 的数目 。 若一条路径上除开始点和结束 点可以相同外 ,其余顶点均不相同 ,则称此 路径为简单路径 。 例如 ,有图中 ,(v0,v2,v1) 就是一条简单路径 ,其长度为 2。 1 0 2 3 7. 回路或环 若一条路径上的开始点与结束 点为同一个顶点 ,则此路径被称为回 路或环 。 开始点与结束点相同的简 单路径被称为简单回路或简单环 。 例如 ,右图中 ,(v0,v2,v1,v0)就是 一条简单回路 ,其长度为 3。 1 0 2 3 8. 连通 、 连通图和连通分量 在无向图 G中 ,若从顶点 vi到顶点 vj有路径 , 则称 vi和 vj是连通的 。 若图 G中任意两个顶点都连通 ,则称 G为 连通图 ,否则称为非连通图 。 无向图 G中的极大连通子图称为 G的连通 分量 。 显然 ,任何连通图的连通分量只有一个 , 即本身 ,而非连通图有多个连通分量 。 9. 强连通图和强连通分量 在有向图 G中 ,若从顶点 vi到顶 点 vj有路径 ,则称从 vi到 vj是连通的。 若图 G中的任意两个顶点 vi和 vj 都连通 ,即从 vi到 vj和从 vj到 vi都存在 路径 ,则称图 G是强连通图。例如 ,右 边两个图都是强连通图。 有向图 G中的极大强连通子图 称为 G的强连通分量。显然 ,强连通 图只有一个强连通分量 ,即本身 ,非 强连通图有多个强连通分量。 1 0 2 3 （ a ） 1 0 2 （ b ） 10. 权和网 图中每一条边都可以附有一个对应的数值 , 这种与边相关的数值称为权。权可以表示从一 个顶点到另一个顶点的距离或花费的代价。边 上带有权的图称为带权图 ,也称作网。 例 9.1 有 n个顶点的有向强连通图最多需要多 少条边？最少需要多 少条边？ 答：有 n个顶点的有向强连通图最多有 n(n- 1)条边 (构成一个有向完全图的情况 )；最少有 n条边 (n个顶点依次首尾相接构成一个环的情 况 )。 9.2 图的存储结构 9.2.1 邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵 。 设 G=(V,E)是具有 n(n 0)个顶点的图 ,顶点的顺序依次为 (v0,v1, ,vn-1),则 G的邻接矩阵 A是 n阶方阵 ,其定义如下： (1) 如果 G是无向图 ,则： Aij= 1:若 (vi,vj) E(G) 0:其他 (2) 如果 G是有向图 ,则： Aij= 1:若 E(G) 0:其他 (3) 如果 G是带权无向图 ,则： Aij= wij :若 vivj且 (vi,vj) E(G) :其他 (4) 如果 G是带权有向图 ,则： Aij= wij :若 vivj且 E(G) :其他 01101 10111 11010 01101 11010 =1A 1 3 0 2 4 1 3 0 2 4 (a) (b ) 01001 00000 11000 01100 01010 =2A 邻接矩阵的特点如下： (1) 图的邻接矩阵表示是惟一的 。 (2) 无向图的邻接矩阵一定是一个对称矩阵 。 因此 ,按照压缩存储的思想 ,在具体存放邻接矩阵时 只需存放上 (或下 )三角形阵的元素即可 。 (3) 不带权的有向图的邻接矩阵一般来说是一 个稀疏矩阵 ,因此 ,当图的顶点较多时 ,可以采用三元 组表的方法存储邻接矩阵 。 (4) 对于无向图 ,邻接矩阵的第 i行 (或第 i列 )非零 元素 (或非 元素 )的个数正好是第 i个顶点 vi的度 。 (5) 对于有向图 ,邻接矩阵的第 i行 (或第 i列 )非零元 素 (或非 元素 )的个数正好是第 i个顶点 vi的出度 (或入 度 )。 (6) 用邻接矩阵方法存储图 ,很容易确定图中任意 两个顶点之间是否有边相连 。 但是 ,要确定图中有多 少条边 ,则必须按行 、 按列对每个元素进行检测 ,所花 费的时间代价很大 。 这是用邻接矩阵存储图的局限 性 。 邻接矩阵的数据类型定义如下： #define MAXV typedef struct int no; /*顶点编号 */ InfoType info; /*顶点其他信息 */ VertexType; /*顶点类型 */ typedef struct /*图的定义 */ int edgesMAXVMAXV; /*邻接矩阵 */ int vexnum,arcnum; /*顶点数 ,弧数 */ VertexType vexsMAXV; /*存放顶点信息 */ MGraph; 9.2.2 邻接表存储方法 图的邻接表存储方法是一种顺序分配与链式 分配相结合的存储方法 。 在邻接表中 ,对图中每个 顶点建立一个单链表 ,第 i个单链表中的结点表示依 附于顶点 vi的边 (对有向图是以顶点 vi为尾的弧 )。 每个单链表上附设一个表头结点 。 表结点和表头 结点的结构如下： 表结点 表头结点 advex nextarc info data firstarc 其中 ,表结点由三个域组成 ,adjvex指示与顶点 vi邻接的点在图中的位置 ,nextarc指示下一条边或 弧的结点 ,info存储与边或弧相关的信息 ,如权值等。 表头结点由两个域组成 ,data存储顶点 vi的名称或 其他信息 ,firstarc指向链表中第一个结点。 1 3 0 2 4 1 3 0 2 4 (a) (b ) 0 1 2 3 4 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v 0 v 1 v 2 v 3 v 4 1 2 3 0 3 3 4 3 v 0 v 1 v 2 v 3 v 4 (a ) (b ) 邻接表的特点如下： (1) 邻接表表示不惟一 。 这是因为在每个顶点对应 的单链表中 ,各边结点的链接次序可以是任意的 ,取决于 建立邻接表的算法以及边的输入次序 。 (2) 对于有 n个顶点和 e条边的无向图 ,其邻接表有 n 个顶点结点和 2e个边结点 。 显然 ,在总的边数小于 n(n- 1)/2的情况下 ,邻接表比邻接矩阵要节省空间 。 (3) 对于无向图 ,邻接表的顶点 vi对应的第 i个链表的 边结点数目正好是顶点 vi的度 。 (4) 对于有向图 ,邻接表的顶点 vi对应的第 i个链表的 边结点数目仅仅是 vi的出度 。 其入度为邻接表中所有 adjvex域值为 i的边结点数目 。 邻接表存储结构的定义如下： typedef struct ANode /*弧的结点结构类型 */ int adjvex; /*该弧的终点位置 */ struct ANode *nextarc; /*指向下一条弧的指针 */ InfoType info; /*该弧的相关信息 */ ArcNode; typedef struct Vnode /*邻接表头结点的类型 */ Vertex data; /*顶点信息 */ ArcNode *firstarc; /*指向第一条弧 */ VNode; typedef VNode AdjListMAXV; /*AdjList是邻接表类型 */ typedef struct AdjList adjlist; /*邻接表 */ int n,e; /*图中顶点数 n和边数 e*/ ALGraph; /*图的类型 */ 例 9.2 给定一个具有 n个结点的无向图的邻接矩阵 和邻接表 。 (1) 设计一个将邻接矩阵转换为邻接表的算法； (2) 设计一个将邻接表转换为邻接矩阵的算法； (3) 分析上述两个算法的时间复杂度 。 解： (1)在邻接矩阵上查找值不为 0的元素 ,找到这 样的元素后创建一个表结点并在邻接表对应的单链表 中采用前插法插入该结点 。 算法如下： void MatToList(MGraph g,ALGraph * ArcNode *p; /*n为顶点数 */ G=(ALGraph *)malloc(sizeof(ALGraph); for (i=0;iadjlisti.firstarc=NULL; for (i=0;i=0;j-) if (g.edgesij!=0) p=(ArcNode *)malloc(sizeof(ArcNode); /*创建结点 *p*/ p-adjvex=j; p-nextarc=G-adjlisti.firstarc;/*将 *p链到链表后 */ G-adjlisti.firstarc=p; G-n=n;G-e=g.arcnum; (2) 在邻接表上查找相邻结点 ,找到后修改相应邻接 矩阵元素的值 。 算法如下： void ListToMat(ALGraph *G,MGraph ArcNode *p; for (i=0;iadjlisti.firstarc; while (p!=NULL) g.edgesip-adjvex=1; p=p-nextarc; g.vexnum=n;g.arcnum=G-e; (3) 算法 1的时间复杂度均为 O(n2)。 算法 2 的时间复杂度为 O(n+e),其中 e为图的边数 。 9.3 图的遍历 9.3.1 图的遍历的概念 从给定图中任意指定的顶点 (称为初始点 )出发 ,按 照某种搜索方法沿着图的边访问图中的所有顶点 ,使 每个顶点仅被访问一次 ,这个过程称为图的遍历 。 如 果给定图是连通的无向图或者是强连通的有向图 ,则 遍历过程一次就能完成 ,并可按访问的先后顺序得到 由该图所有顶点组成的一个序列 。 根据搜索方法的不同 ,图的遍历方法有两种：一 种叫做深度优先搜索法 (DFS)；另一种叫做广度优先 搜索法 (BFS)。 9.3.2 深度优先搜索遍历 深度优先搜索遍历的过程是：从图中某个初始顶 点 v出发 ,首先访问初始顶点 v,然后选择一个与顶点 v 相邻且没被访问过的顶点 w为初始顶点 ,再从 w出发 进行深度优先搜索 ,直到图中与当前顶点 v邻接的所 有顶点都被访问过为止 。 显然 ,这个遍历过程是个递 归过程 。 以邻接表为存储结构的深度优先搜索遍历算法 如下 (其中 ,v是初始顶点编号 ,visited是一个全局数 组 ,初始时所有元素均为 0表示所有顶点尚未访问过 )： void DFS(ALGraph *G,int v) ArcNode *p; visitedv=1; /*置已访问标记 */ printf(%d ,v); /*输出被访问顶点的编号 */ p=G-adjlistv.firstarc; /*p指向顶点 v的第一条弧的弧头结点 */ while (p!=NULL) if (visitedp-adjvex=0) DFS(G,p-adjvex); /*若 p-adjvex顶点未访问 ,递归访问它 */ p=p-nextarc; /*p指向顶点 v的下一条弧的弧头结点 */ 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v 0 v 1 v 2 v 3 v 4 1 3 0 2 4 例如 ,以上图的邻接表为例调用 DFS() 函数 ,假设初始顶点编号 v=2,给出调用 DFS()的执行过程 ,见教材 。 9.3.3 广度优先搜索遍历 广度优先搜索遍历的过程是：首先访问初始点 vi, 接着访问 vi的所有未被访问过的邻接点 vi1,vi2, ,vit,然 后再按照 vi1,vi2, ,vit的次序 ,访问每一个顶点的所有未 被访问过的邻接点 ,依次类推 ,直到图中所有和初始点 vi有路径相通的顶点都被访问过为止 。 以邻接表为存储结构 ,用广度优先搜索遍历图时 , 需要使用一个队列 ,以类似于按层次遍历二叉树遍历 图 。 对应的算法如下 (其中 ,v是初始顶点编号 )： void BFS(ALGraph *G,int v) ArcNode *p; int w,i; int queueMAXV,front=0,rear=0; /*定义循环队列 */ int visitedMAXV; /*定义存放结点的访问标志的数组 */ for (i=0;in;i+) visitedi=0; /*访问标志数组初始化 */ printf(%2d,v); /*输出被访问顶点的编号 */ visitedv=1; /*置已访问标记 */ rear=(rear+1)%MAXV; queuerear=v; /*v进队 */ while (front!=rear) /*若队列不空时循环 */ front=(front+1)%MAXV; w=queuefront; /*出队并赋给 w*/ p=G-adjlistw.firstarc; /*找 w的第一个的邻接点 */ while (p!=NULL) if (visitedp-adjvex=0) printf(“%2d”,p-adjvex); /*访问之 */ visitedp-adjvex=1; rear=(rear+1)%MAXV;/*该顶点进队 */ queuerear=p-adjvex; p=p-nextarc; /*找下一个邻接顶点 */ printf(n); 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v 0 v 1 v 2 v 3 v 4 1 3 0 2 4 例如 ,以上图的邻接表为例调用 BFS()函数 , 假设初始顶点编号 v=2,给出调用 BFS()的 执行过程 ,见教材 。 9.3.4 非连通图的遍历 对于无向图来说 ,若无向图是连通图 ,则一次遍历 能够访问到图中的所有顶点； 但若无向图是非连通图 ,则只能访问到初始点所 在连通分量中的所有顶点 ,其他连通分量中的顶点是 不可能访问到的 。 为此需要从其他每个连通分量中选 择初始点 ,分别进行遍历 ,才能够访问到图中的所有顶 点； 对于有向图来说 ,若从初始点到图中的每个顶点 都有路径 ,则能够访问到图中的所有顶点；否则不能 访问到所有顶点 ,为此同样需要再选初始点 ,继续进 行遍历 ,直到图中的所有顶点都被访问过为止 。 采用深度优先搜索遍历非连通无向图的算法如下： DFS1(ALGraph *g) int i; for (i=0;in;i+) /*遍历所有未访问过的顶点 */ if (visitedi=0) DFS(g,i); 采用广度优先搜索遍历非连通无向图的算法如下 ： BFS1(ALGraph *g) int i; for (i=0;in;i+) /*遍历所有未访问过的顶点 */ if (visitedi=0) BFS(g,i); 9.3.5 图遍历的应用 例 假设图 G采用邻接表存储，设计一个算法， 判断无向图 G是否连通。若连通则返回 1；否则返回 0。 解：采用遍历方式判断无向图 G是否连通。这里 用深度优先遍历方法，先给 visited数组（为全局变 量）置初值 0，然后从 0顶点开始遍历该图。 在一次遍历之后，若所有顶点 i的 visitedi均为 1， 则该图是连通的；否则不连通。对应的算法如下： int Connect(ALGraph *G) /*判断无向图 G的连通性 */ int i,flag=1; for (i=0;in;i+) /*visited数组置初值 */ visitedi=0; DFS(G,0);/*调用 DSF算法 ,从顶点 0开始深度优先遍历 */ for (i=0;in;i+) if (visitedi=0) flag=0; break; return flag; 例 假设图 G采用邻接表存储，设计一个算法， 输出图 G中从顶点 u到 v的长度为 l的所有简单路径。 解：所谓简单路径是指路径上的顶点不重复。利 用回溯的深度优先搜索方法。 从顶点 u开始，进行深度优先搜索，在搜索过程 中，需要把当前的搜索线路记录下来。为此设立一个 数组 path保存走过的路径，用 d记录走过的路径长度。 若当前扫描到的结点 u等于 v且路径长度为 l时，表示 找到了一条路径，则输出路径 path。 对应的算法如下： void PathAll(ALGraph *G,int u,int v,int l,int path,int d) /*d是到当前为止已走过的路径长度，调用时初值为 -1*/ int m,i; ArcNode *p; visitedu=1; d+; /*路径长度增 1*/ pathd=u; /*将当前顶点添加到路径中 */ if (u=v for (i=0;iadjlistu.firstarc; /*p指向 u的第一条弧的弧头结点 */ while (p!=NULL) m=p-adjvex; /*m为 u的邻接顶点 */ if (visitedm=0) /*若顶点未标记访问 ,则递归访问之 */ PathAll(G,m,v,l,path,d); p=p-nextarc /*找 u的下一个邻接顶点 */ visitedu=0; /*恢复环境 */ void main() int pathMAXV,u=1,v=4,d=3,i,j; MGraph g; ALGraph *G; g.n=5;g.e=6; int AMAXVMAXV= 0,1,0,1,0,1,0,1,0,0, 0,1,0,1,1, 1,0,1,0,1, 0,0,1,1,0 ; for (i=0;ig.n;i+) /*建立图 9.1(a)的邻接矩阵 */ for (j=0;jg.n;j+) g.edgesij=Aij; MatToList(g,G); for (i=0;ig.n;i+) visitedi=0; printf(图 G:n);DispAdj(G);/*输出邻接表 */ printf(从 %d到 %d的所有长度为 %d路径 :n,u,v,d); PathAll(G,u,v,d,path,-1); printf(n); 程序执行结果如下： 图 G: 0: 1 3 1: 0 2 2: 1 3 4 3: 0 2 4 4: 2 3 从 1到 4的所有长度为 3路径 : 1 0 3 4 1 2 3 4 1 3 2 4 0 9.4 生成树和最小生成树 9.4.1 生成树的概念 一个连通图的生成树是一个极小连通子图 ,它含有 图中全部顶点 ,但只有构成一棵树的 (n-1)条边 。 如果在一棵生成树上添加一条边 ,必定构成一个环： 因为这条边使得它依附的那两个顶点之间有了第二条 路径 。 一棵有 n个顶点的生成树 (连通无回路图 )有且仅 有 (n-1)条边 ,如果一个图有 n个顶点和小于 (n-1)条边 ,则 是非连通图 。 如果它多于 (n-1)条边 ,则一定有回路 。 但 是 ,有 (n-1)条边的图不一定都是生成树 。 对于一个带权 (假定每条边上的权均为大于零的实 数 )连通无向图 G中的不同生成树 ,其每棵树的所有边上 的权值之和也可能不同；图的所有生成树中具有边上 的权值之和最小的树称为图的最小生成树 。 按照生成树的定义 ,n个顶点的连通图的生成树有 n 个顶点 、 n-1条边 。 因此 ,构造最小生成树的准则有三条： (1) 必须只使用该图中的边来构造最小生成树； (2) 必须使用且仅使用 n-1条边来连接图中的 n个顶点； (3) 不能使用产生回路的边 。 9.4.2 无向图的连通分量和生成树 在对无向图进行遍历时 ,对于连通图 ,仅需调用遍历 过程 (DFS或 BFS)一次 ,从图中任一顶点出发 ,便可以遍 历图中的各个顶点 。 对非连通图 ,则需多次调用遍历 过程 ,每次调用得到的顶点集连同相关的边就构成图 的一个连通分量 。 设 G=(V,E)为连通图 ,则从图中任一顶点出发遍历 图时 ,必定将 E(G)分成两个集合 T和 B,其中 T是遍历图 过程中走过的边的集合 ,B是剩余的边的集合： TB=,T B=E(G)。 显然 ,G=(V,T)是 G的极小连通 子图 ,即 G是 G的一棵 生成树 。 由深度优先遍历得到的生成树称为 深度优先生 成树 ；由广度优先遍历得到的生成树称为广度优先 生成树 。 这样的生成树是由遍历时访问过的 n个顶 点和遍历时经历的 n-1条边组成 。 对于非连通图 ,每个连通分量中的顶点集和遍 历时走过的边一起构成一棵生成树 ,各个连通分量 的生成树组成非连通图的生成森林。 9.4.4 普里姆算法 普里姆 (Prim)算法是一种构造性算法 。 假设 G=(V,E)是一个具有 n个顶点的带权连通无向 图 ,T=(U,TE)是 G的最小生成树 ,其中 U是 T的顶点集 ,TE 是 T的边集 ,则由 G构造最小生成树 T的步骤如下： (1) 初始化 U=v0。 v0到其他顶点的所有边为候选 边； (2) 重复以下步骤 n-1次 ,使得其他 n-1个顶点被加入 到 U中： 从候选边中挑选权值最小的边输出 ,设该边在 V-U中的顶点是 v,将 v加入 U中 ,删除和 v关联的边； 考察当前 V-U中的所有顶点 vi,修改候选边：若 (v,vi)的权值小于原来和 vi关联的候选边 ,则用 (v,vi)取代 后者作为候选边。 5 0 2 1 3 4 5 (a ) 1 5 6 3 5 6 6 4 2 0 2 1 3 4 5 (b) 1 0 2 1 3 4 5 (c ) 1 4 0 2 1 3 4 5 (d) 1 4 2 0 2 1 3 4 5 (e ) 1 5 4 2 0 2 1 3 4 5 (f ) 1 3 4 2 5 普里姆算法求解最小生成树的过程 普里姆 (Prim)算法如下： #define INF 32767 /*INF表示 */ void Prim(int costMAXV,int n,int v) int lowcostMAXV,min; int closestMAXV,i,j,k; for (i=0;in;i+) /*给 lowcost和 closest置初值 */ lowcosti=costvi; closesti=v; for (i=1;in;i+) /*找出 n-1个顶点 */ min=INF; for (j=0;jn;j+) /*在 (V-U)中找出离 U最近的顶点 k*/ if (lowcostj!=0 k=j; printf(边 (%d,%d)权为 :%dn,closestk,k,min); lowcostk=0; /*标记 k已经加入 U*/ for (j=0;jn;j+) /*修改数组 lowcost和 closest*/ if (costkj!=0 closestj=k; Prim()算法中有两重 for循环 ,所以时间复杂度 为 O(n2)。 9.4.5 克鲁斯卡尔算法 克鲁斯卡尔 (Kruskal)算法是一种按权值的递增次序 选择合适的边来构造最小生成树的方法 。 假设 G=(V,E) 是一个具有 n个顶点的带权连通无向图 ,T=(U,TE)是 G的 最小生成树 ,则构造最小生成树的步骤如下： (1) 置 U的初值等于 V(即包含有 G中的全部顶点 ),TE 的初值为空集 (即图 T中每一个顶点都构成一个分量 )。 (2) 将图 G中的边按权值从小到大的顺序依次选取： 若选取的边未使生成树 T形成回路 ,则加入 TE；否则舍 弃 ,直到 TE中包含 (n-1)条边为止 。 4 1 0 2 1 3 4 5 (a ) 1 0 2 1 3 4 5 (b ) 1 0 2 1 3 4 5 (c ) 1 0 2 1 3 4 5 (d ) 1 4 2 (e ) 0 2 1 3 4 5 1 3 4 2 5 2 2 3 3 0 0 3 5 4 1 0 0 3 3 1 1 0 0 3 3 1 1 0 0 0 0 1 1 1 1 1 1 克鲁斯卡尔算法求解最小生成树的过程 为了简便 ,在实现克鲁斯卡尔算法 Kruskal()时 ,参数 E存放图 G中的所有边 ,假设它们是按权值从小到大的 顺序排列的 。 n为图 G的顶点个数 ,e为图 G的边数 。 typedef struct int u; /*边的起始顶点 */ int v; /*边的终止顶点 */ int w; /*边的权值 */ Edge; void Kruskal(Edge E,int n,int e) int i,j,m1,m2,sn1,sn2,k; int vsetMAXV; for (i=0;in;i+) vseti=i; /*初始化辅助数组 */ k=1; /*k表示当前构造最小生成树的第几条边 ,初值为 1*/ j=0; /*E中边的下标 ,初值为 0*/ while (k最小生成树的一条边 */ printf(%d,%d):%dn,m1,m2,Ej.w); k+; /*生成边数增 1*/ for (i=0;in;i+) /*两个集合统一编号 */ if (vseti=sn2) /*集合编号为 sn2的改为 sn1*/ vseti=sn1; j+; /*扫描下一条边 */ 完整的克鲁斯卡尔算法应包括对边按权值递增 排序，上述算法假设边已排序的情况下，时间复杂 度为 O(n2)。 如果给定的带权连通无向图 G有 e条边 ,n个顶点， 采用堆排序 (在第 11章中介绍 )对边按权值递增排序， 那么用克鲁斯卡尔算法构造最小生成树的时间复杂 度降为 O(elog2e)。 由于它与 n无关，只与 e有关， 所以说克鲁斯卡尔算法适合于稀疏图。 9.5 最短路径 9.5.1 路径的概念 在一个无权的图中 ,若从一顶点到另一顶点存在 着一条路径 ,则称该路径长度为该路径上所经过的边 的数目 ,它等于该路径上的顶点数减 1。 由于从一顶点到另一顶点可能存在着多条路径 , 每条路径上所经过的边数可能不同 ,即路径长度不同 , 我们把路径长度最短 (即经过的边数最少 )的那条路 径叫做最短路径 ,其路径长度叫做 最短路径长度 或 最 短距离 。 对于带权的图 ,考虑路径上各边上的权值 ,则通常 把一条路径上所经边的权值之和定义为该路径的 路 径长度 或称 带权路径长度 。 从源点到终点可能不止一条路径 ,把带权路径长 度最短的那条路径称为最短路径 ,其路径长度 (权值之 和 )称为最短路径长度或者最短距离 。 9.5.2 从一个顶点到其余各顶点的最短路径 问题：给定一个带权有向图 G与源点 v,求从 v到 G中其他顶点的最短路径 ,并限定各边上的权值大 于或等于 0。 采用 狄克斯特拉 (Dijkstra)算法 求解 基本思想是：设 G=(V,E)是一个带权有向图 , 把图中 顶点集合 V分成两组： 第一组为已求出最短路径的顶点集合 (用 S表示 ,初始 时 S中只有一个源点 ,以后每求得一条最短路径 v, vk,就 将 vk加入到集合 S中 ,直到全部顶点都加入到 S中 ,算法就 结束了 ) 第二组为其余未确定最短路径的顶点集合 (用 U表 示 )。 按最短路径长度的递增次序依次把第二组的 顶点加入 S中 。 在加入的过程中 ,总保持从源点 v到 S中各顶点的最短路径长度不大于从源点 v到 U中 任何顶点的最短路径长度 。 此外 ,每个顶点对应一个距离 ,S中的顶点的距 离就是从 v到此顶点的最短路径长度 ,U中的顶点 的距离从 v到此顶点只包括 S中的顶点为中间顶点 的当前最短路径长度 。 狄克斯特拉算法的具体步骤如下： (1) 初始时 ,S只包含源点 ,即 S=v,v的距离为 0。 U包 含除 v外的其他顶点 ,U中顶点 u距离为边上的权 (若 v与 u 有边 )或 (若 u不是 v的出边邻接点 )。 (2) 从 U中选取一个距离 v最小的顶点 k,把 k加入 S中 (该选定的距离就是 v到 k的最短路径长度 )。 (3) 以 k为新考虑的中间点 ,修改 U中各顶点的距离： 若从源点 v到顶点 u(u U)的距离 (经过顶点 k)比原来距 离 (不经过顶点 k)短 ,则修改顶点 u的距离值 ,修改后的距 离值的顶点 k的距离加上边 上的权 。 (4) 重复步骤 (2)和 (3)直到所有顶点都包含在 S中 。 v j k c vk w kj c vj V到 j的最小距离 MIN(cvk+wkj,cvj) 1 4 0 2 6 3 5 8 1 6 6 4 2 5 6 6 1 4 7 S U dist path 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1,2,3,4,5,6 0,4,6,6, 0,0,0,0,-1,-1,-1 0,1 2,3,4,5,6 0,4,5,6,11, 0,0,1,0,1,-1,-1 0,1,2 3,4,5,6 0,4,5,6,11,9, 0,0,1,0,1,2,-1 0,1,2,3 4,5,6 0,4,5,6,11,9, 0,0,1,0,1,2,-1 0,1,2,3,5 4,6 0,4,5,6,10,9,17 0,0,1,0,5,2,5 0,1,2,3,5,4 6 0,4,5,6,10,9,16 0,0,1,0,5,2,4 0,1,2,3,5,4,6 0,4,5,6,10,9,16 0,0,1,0,5,2,4 狄克斯特拉算法如下 (n为图 G的顶点数 ,v0为源点编号 )： void Dijkstra(int costMAXV,int n,int v0) int distMAXV,pathMAXV; int sMAXV;int mindis,i,j,u; for (i=0;in;i+) disti=costv0i; /*距离初始化 */ si=0; /*s置空 */ if (costv0iINF) /*路径初始化 */ pathi=v0; else pathi=-1; sv0=1;pathv0=0; /*源点编号 v0放入 s中 */ for (i=0;in;i+) /*循环直到所有顶点的最短路径都求出 */ mindis=INF; u=-1; for (j=0;jn;j+) /*选取不在 s中且具有最小距离的顶点 u*/ if (sj=0 mindis=distj; su=1; /*顶点 u加入 s中 */ for (j=0;jn;j+) /*修改不在 s中的顶点的距离 */ if (sj=0) if (costujINF pathj=u; Dispath(dist,path,s,n,v0); /*输出最短路径 */ void Ppath(int path,int i,int v0) /*前向递归查找路径上的顶点 */ int k; k=pathi; if (k=v0) return; /*找到了起点则返回 */ Ppath(path,k,v0); /*找 k顶点的前一个顶点 */ printf(%d,k); /*输出 k顶点 */ void Dispath(int dist,int path,int s,int n,int v0) int i; for (i=0;in;i+) if (si=1) printf(“从 %d到 %d的最短路径长度为 : %dt路径为 :,v0,i,disti); printf(%d,v0); /*输出路径上的起点 */ Ppath(path,i,v0); /*输出路径上的中间点 */ printf(%dn,i); /*输出路径上的终点 */ else printf(从 %d到 %d不存在路径 n,v0,i); 9.5.3 每对顶点之间的最短路径 问题：对于一个各边权值均大于零的有向图 ,对每 一对顶点 vivj,求出 vi与 vj之间的最短路径和最短路径 长度 。 可以通过以每个顶点作为源点循环求出每对顶点 之间的最短路径 。 除此之外 ,弗洛伊德 (Floyd)算法也 可用于求两顶点之间最短路径 。 假设有向图 G=(V,E)采用邻接矩阵 cost存储 ,另外设 置一个二维数组 A用于存放当前顶点之间的最短路径 长度 ,分量 Aij表示当前顶点 vi到顶点 vj的最短路径 长度 。 弗洛伊德算法的基本思想是递推产生一个矩阵序 列 A0,A1, ,Ak, ,An,其中 Akij表示从顶点 vi到顶点 vj的路径上所经过的顶点编号不大于 k的最短路径长 度 。 初始时 ,有 A-1ij=costij。 当求从顶点 vi到顶点 vj的路径上所经过的顶点编号不大于 k+1的最短路径长 度时 ,要分两种情况考虑： 一种情况是该路径不经过顶点编号为 k+1的顶点 , 此时该路径长度与从顶点 vi到顶点 vj的路径上所经过 的顶点编号不大于 k的最短路径长度相同； 另一种情况是从顶点 vi到顶点 vj的最短路径上经过 编号为 k+1的顶点 。 i j k +1 A k i , k + 1 A k k + 1, j A k i ,j Ak+1i,j=MIN(Aki,j,Aki,k+1+Akk+1,j 那么 ,该路径可分为两段 : (1) 从顶点 vi到顶点 vk+1的最短路径 ; (2) 从顶点 vk+1到顶点 vj的最短路径 。 此时最短路径长度等于这两段路径长度之和 。 这两种情况中的较小值 ,就是所要求的从顶点 vi到顶 点 vj的路径上所经过的顶点编号不大于 k+1的最短 路径 。 弗洛伊德思想可用如下的表达式来描述： A-1ij=costij Ak+1ij=MIN Akij, Akik+1+Akk+1j (0kn-1) 0 1 2 3 1 2 7 2 3 4 3 5 01 2033 240 750 01 2033 240 750 1A 1-1-1-1- 1-1-1-1- 1-1-1-1- 1-1-1-1- 1P at h 采用弗洛伊德算法求解过程 考虑顶点 v0,A0ij表示由 vi到 vj, 经由顶点 v0的最短路径 。 只有从 v2到 v1经过 v0的路径和从 v2到 v3经过 v0的 路径 ,不影响 v2到 v1和 v2到 v3的路径长 度 ,因此 ,有： 01 2033 240 750 0A 1-1-1-1- 1-1-1-1- 1-1-1-1- 1-1-1-1- 0P a t h 0 1 2 3 1 2 7 2 3 4 3 5 考虑顶点 v1,A1ij表示由 vi 到 vj,经由顶点 v1的最短路径 。 存在路径 v0-v1-v2,路径长度为 9, 将 A02改为 9,path02改为 1, 因此 ,有 ： 01 2033 240 7950 1A 1-1-1-1- 1-1-1-1- 1-1-1-1- 1-11-1- 1P a t h 0 1 2 3 1 2 7 2 3 4 3 5 考虑顶点 v2,A2ij表示由 vi到 vj, 经由顶点 v2的最短路径 。 存在路径 v3-v2-v0,长度为 4,将 A30改为 4；存 在路径 v3-v2-v1,长度为 4,将 A31改 为 4。 存在路径 v1-v2-v0,长度为 7,将 A10 改为 7 。 将 path30 、 path31和 path10均改为 2。 因 此 ,有： 0144 2033 2407 7950 2A 1-1-22 1-1-1-1- 1-1-1-2 1-11-1- 2P at h 0 1 2 3 1 2 7 2 3 4 3 5 考虑顶点 v3,A3ij表示由 vi到 vj, 经由顶点 v3的最短路径。存在路径 v0- v3-v2,长度为 8比原长度短 ,将 A02改 为 8；存在路径 v1-v3-v2-v0,长度为 6(A13+A30=2+4=6)比原长度短 , 将 A10改为 6；存在路径 v1-v3-v2,长 度为 3,比原长度短 ,将 A12改为 3； 将 path02、 path10后 path12 均改为 3。因此 ,有： 0144 2033 2306 7850 3A 1-1-22 1-1-1-1- 1-31-3 1-31-1- 3P a t h 0 1 2 3 1 2 7 2 3 4 3 5 0144 2033 2306 7850 从 0到 0路径为： 0,0 路径长度为： 0 从 0到 1路径为： 0,1 路径长度为： 5 从 0到 2路径为： 0,3,2 路径长度为： 8 从 0到 3路径为： 0,3 路径长度为： 7 从 1到 0路径为： 1,3,2,0 路径长度为： 6 从 1到 1路径为： 1,1 路径长度为： 0 从 1到 2路径为： 1,3,2 路径长度为： 3 从 1到 3路径为： 1,3 路径长度为： 2 1-1-22 1-1-1-1- 1-31-3 1-31-1- A= Path= 从 2到 0路径为： 2,0 路径长度为： 3 从 2到 1路径为： 2,1 路径长度为： 3 从 2到 2路径为： 2,2 路径长度为： 0 从 2到 3路径为： 2,3 路径长度为： 2 从 3到 0路径为： 3,2,0 路径长度为： 4 从 3到 1路径为： 3,2,1 路径长度为： 4 从 3到 2路径为： 3,2 路径长度为： 1 从 3到 3路径为： 3,3 路径长度为： 0 弗洛伊德算法如下： void Floyd(int costMAXV,int n) int AMAXVMAXV,pathMAXVMAXV;int i,j,k; for (i=0;in;i+) for (j=0;jn;j+) Aij=costij; pathij=-1; for (k=0;kn;k+) for (i=0;in;i+) for (j=0;j(Aik+Akj) Aij=Aik+Akj; pathij=k; Dispath(A,path,n); /*输出最短路径 */ 9.6 拓扑排序 设 G=(V,E)是一个具有 n个顶点的有向图 ,V中顶 点序列 v1,v2, ,vn称为一个拓扑序列 ,当且仅当该顶点 序列满足下列条件： 若 是图中的边 (即从顶点 vi到 vj有一条路径 ), 则在序列中顶点 vi必须排在顶点 vj之前 。 在一个有向图中找一个拓扑序列的过程称为拓 扑排序 。 课程代号 课程名称 先修课程 C1 高等数学 无 C2 程序设计 无 C3 离散数学 C1 C4 数据结构 C2,C3 C5 编译原理 C2,C4 C6 操作系统 C4,C7 C7 计算机组成原理 C2 例如 ,计算机专业的学生必须完成一系列规定的基 础课和专业课才能毕业 ,假设这些课程的名称与相应 代号有如下关系： 课程之间的先后关系可用有向图表示 ： C1 C3 C4 C2 C5 C7 C6 对这个有向图进行拓扑排序可得到一个拓扑 序列： C1-C3-C2-C4-C7-C6-C5。 也可得到另一 个拓扑序列： C2-C7-C1-C3-C4-C5-C6,还可以得 到其他的拓扑序列 。 学生按照任何一个拓扑序列 都可以顺序地进行课程学习 。 拓扑排序方法如下： (1) 从有向图中选择一个没有前驱 (即入度为 0) 的顶点并且输出它 。 (2) 从网中删去该顶点 ,并且删去从该顶点发出 的全部有向边 。 (3) 重复上述两步 ,直到剩余的网中不再存在没 有前驱的顶点为止 。 为了实现拓扑排序的算法 ,对于给定的有向图 ,采 用邻接表作为存储结构 ,为每个顶点设立一个链表 ,每 个链表有一个表头结点 ,这些表头结点构成一个数组 , 表头结点中增加一个存放顶点入度的域 count。 即将 邻接表定义中的 VNode类型修改如下： typedef struct /*表头结点类型 */ Vertex data; /*顶点信息 */ int count; /*存放顶点入度 */ ArcNode *firstarc; /*指向第一条弧 */ VNode; void TopSort(VNode adj,int n) int i,j;int StMAXV,top=-1; /*栈 St的指针为 top*/ ArcNode *p; for (i=0;i-1) /*栈不为空时循环 */ i=Sttop;top-; /*出栈 */ printf(%d ,i); p=adji.firstarc; while (p!=NULL) j=p-adjvex; adjj.count-; if (adjj.count=0) top+; Sttop=j; p=p-nextarc; /*找下一个相邻顶点 */ 9.7 AOE网与关键路径 若用前面介绍过的带权有向图 (DAG)描述工程的 预计进度 ,以顶点表示事件 ,有向边表示活动 ,边 e的权 c(e)表示完成活动 e所需的时间 (比如天数 ),或者说活动 e 持续时间。 图中入度为 0的顶点表示工程的 开始事件 (如开工仪 式 ),出度为 0的顶点表示工程 结束事件 。则称这样的有 向图为 AOE网 (Activity On Edge)。 通常每个工程都只有一个开始事件和一个结束事 件 ,因此表示工程的 AOE网都只有一个入度为 0的顶 点 ,称为 源点 (source),和一个出度为 0的顶点 ,称为 汇 点 (converge)。 如果图中存在多个入度为 0的顶点 ,只要加一个虚 拟源点 ,使这个虚拟源点到原来所有入度为 0的点都 有一条长度为 0的边 ,变成只有一个源点。对存在多 个出度为 0的顶点的情况作类似的处理。所以只需讨 论单源点和单汇点的情况。 在 AOE网中 ,从源点到汇点的所有路径中 ,具有最大 路径长度的路径称为关键路径。完成整个工程的最短 时间就是网中关键路径的长度 ,也就是网中关键路径上 各活动持续时间的总和 ,我们把关键路径上的活动称为 关键活动。因此 ,只要找出 AOE网中的关键活动 ,也就 找到了 关键路径 。 注意 :在一个 AOE网中 ,可以有不止一条的关键路径。 例如 ,下图表示某工程的 AOE网。共有 9个事件和 11 项活动。其中 A表示开始事件 ,G表示结束事件。 A B C D E F G H I 几个定义： (1) 事件 v的最早可发生时间：假设事件 x是源点 , 事件 y为汇点 ,并规定事件 x的发生时间为 0。定义图中 任一事件 v的最早 (event early)可发生时间 ve(v)等于 x 到 v所有路径长度的最大值 ,即： ve(v)= )p(cM A Xp 上式中的 MAX是对 x到 v的所有路径 p取最大值 ,c(p) 表示路径 p的长度 (路径上边长之和 ) ,即： c(p)= )e(c pe 完成整个工程所需的最少时间 ,等于事件 y的最早 可发生时间 ve(y)。 (2) 事件 v的最迟可发生时间：定义在不影响整个工 程进度的前提下 ,事件 v必须发生的时间称为 v的最迟 (event late)可发生时间 ,记作 vl(v)。 vl(v)应等于 ve(y)与 v到 y的最长路径长度之差 (y是汇点 ),即： vl(v)=ve(y) - )p(cM A X p (3) 关键活动 :若活动 v满足 ve(v)+c(ai)=vl(w),则称 活动 ai为关键活动 。 对关键活动来说 ,不存在富余时间 。 显然 ,关键路 径上的活动都是关键活动 。 找出关键活动的意义在于 , 可以适当地增加对关键活动的投资 (人力 、 物力等 ), 相应地减少对非关键活动的投资 ,从而减少关键活动 的持续时间 ,缩短整个工程的工期 。 只要计算出各项点的 ve(v)和 vl(v)的值 ,根据 9.3等 式就能找出所有的关键活动。为了便于计算 ,引入下 面两个递推式 ,其中 ,x和 y分别是源点和汇点。 ve(x)=0 ve(w)= wx 上式中的 MAX对所有射入 w的边 取最大值 。 vl(y)=0 vl(v)= vy )w,v(c)v(veM A X vw,v 边的所有存在 )w,v(c)w(vlM I N ww,v 边的所有存在 求 AOE网的关键活动的步骤： (1) 对于源点 x,置 ve(x)=0； (2) 对 AOE网进行拓扑排序 。 如发现回路 ,工程无法 进行 ,则退出；否则继续下一步 。 (3) 按顶点的拓扑次序 ,反复用式 9.4,依次求其余各项 点 v的 ve(v)值 。 (实际上 ,步骤 (2)和步骤 (3)可以合在一起 完成 ,即一边对顶点进行拓扑排序 ,一边求出各点的 e(v) 之值 。 ) (4) 对于汇点 y,置 vl(y)=ve(y)； (5) 按顶点拓扑次序之逆序 ,反复用式 9.5,依次求其余各 项点 v的 vl(v)的值 。 即对 v射出的所有边 ,检查是否 满足式 9.3,若是 ,则输出该边的有关信息 ,指明该边所对应 的活动是关键活动 。 (6) 活动 ai的最早开始时间 e(i)是该活动的起点所表示 的事件最早发生时间 。 如果由边 表示活动 ai,则有 e(i)=ve(j)。 (7) 活动 ai的最迟开始时间 l(i)是该活动的终点所表示 的事件最迟发生时间与该活动的所需时间之差 。 如果用 边 表示活动 ai,则有 l(i)=v