复习：树 树的基本概念和术语 二叉树的概念及性质 二叉树的存储结构 遍历二叉树 线索二叉树 树的应用：哈夫曼树 顺序存储 链式存储 递归算法 非递归算法 线索二叉树 树的应用：哈夫曼树

第8章 图

重点内容 图的定义和术语 图的存储结构 掌握： 图的遍历：深度优先，广度优先 图与线性表、树形结构的关系 图的表示 术语：基本术语，[特别注意：弧尾，弧头，有序，无序] 三种关系：图与网，顶点与边的数目，图与树、森林 图的存储结构 顺序存储：数组表示法 链表存储：邻接表，多重链表表示法，十字链表，邻接多重表 掌握： 存储结构的存储方式，各种操作的实现思想 各种存储结构的特点和优势 图的遍历：深度优先，广度优先

8.1 图的基本概念 图的定义（P135） 图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： G=(V，E) 其中：G表示一个图，V(vertex)是图G中顶点的集合，E(edge)是图G中顶点之间边的集合。 即： V = { x | x  某个数据对象} 是顶点的有穷非空集合； E = {(x, y) | x, y  V } 是顶点之间关系的有穷集合，也叫做边(edge)集 合。例如:E={ <A,B>,<C,D>,<A.D>,<B,C>}

8.1 图的逻辑结构 V1 V2 V3 V4 V5 若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。 如果图的任意两个顶点之间的边都是无向边，则称该图为无向图undigraph。 V1 V2 若从顶点vi到vj的边有方向，则称这条边为有向边，表示为<vi,vj>。 V3 V4 如果图的任意两个顶点之间的边都是有向边，则称该图为有向图digraph。

8.1 图的逻辑结构 图的基本术语（P136-137） 无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。 有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。 V1 V2 V3 V4 V1 V2 V3

图的分类 着眼点：存储结构的选择。 无向完全图 边数：n*(n-1)/2 有向完全图 弧数：n*(n-1) 稀疏图 边数≈顶点数 稠密图 边数≈顶点数2 带权图（网） 边或顶点带权值

8.1 图的逻辑结构 图的基本术语（续） 顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。 顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)； 顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。

8.1 图的逻辑结构 图的基本术语（续） 权：是指对边赋予的有意义的数值量。 网：边上带权的图，也称网图。 2 V1 V2 7 5 8 V3

8.1 图的逻辑结构 图的基本术语（续） 路径：着眼点：顶点间的联系。 V1 V2 V3 V4 V5 V1 到V4的路径： V1 V4 顶点间路径 Vi,……,Vj 顶点间连通 若从Vi到Vj有路径，称Vi到Vj是连通的。 路径长度 路径上边/弧的数目。 V1 V2 V3 V4 V5 V1 到V4的路径： V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4 一般情况下，图中的路径不惟一。

8.1 图的逻辑结构 图的基本术语（续） 路径长度： V1 V2 V3 V4 V5 非带权图——路径上边的个数 带权图——路径上各边的权之和

8.1 图的逻辑结构 图的基本术语（续） 路径长度： V1 V2 V3 V4 V5 2 5 6 3 8 非带权图——路径上边的个数 带权图——路径上各边的权之和 V1 V2 V3 V4 V5 2 5 6 3 8 V1 V4：长度为8 V1 V2 V3 V4 ：长度为7 V1 V2 V5V3 V4 ：长度为15

8.1 图的逻辑结构 图的基本术语（续） 回路（环）：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。 V1 V2 V3 V4 V1 V2 V3 V4 V5

8.1 图的逻辑结构 图的基本术语（续） 子图：若图G=（V，E），G'=（V'，E'），如果V'V 且E'  E ，则称图G'是G的子图。 V1 V2 V1 V2 V3 V4 V5 V1 V3 V4 V3 V4 V5

8.1 图的逻辑结构 图的基本术语（续） 连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。 连通分量：非连通图的极大连通子图称为连通分量。 1.含有极大顶点数； 2. 依附于这些顶点的所有边。

8.1 图的逻辑结构 图的基本术语（续） 强连通图：在有向图中，对图中任意一对顶点vi和vj (i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。 强连通分量：非强连通图的极大强连通子图。

8.1 图的逻辑结构 图的基本术语（续） 生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。 生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。 多——构成回路 少——不连通 含有n-1条边

8.1 图的逻辑结构 无 向 图 生成 树 连通无向图中，n个顶点和n-1条边，构成的连通子图。（原连通图的极小连通子图） 森林 不连通的无向图中，各连通分量的生成树的集合。 有 强连通有向图中，n个顶点和n-1条弧，构成的单向连通子图(vi、vj间存在一条路径)。 一个顶点入度为０，其余顶点入度为１。 不强连通的有向图中，各有强连通分量的生成树的集合。

考研真题一 1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】 A．由顶点和相邻顶点序偶构成的边所形成的序列 1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】【北京航空航天大学 1999 一、7 （2分）】 3．一个n个顶点的连通无向图，其边的个数至少为（ ）【浙江大学 99 四、4 (4分)】 A．n-1 B．n C．n+1 D．nlogn；

考研真题一 4．要连通具有n个顶点的有向图，至少需要（ ）条边。【北航 2000 一、6(2分）】 A．n-l B．n C．n+l D．2n A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。【北邮 2000 二、5 （20/8分）】 A．0 B．1 C．n-1 D．N 7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈工大01 （2分）】 A．1/2 B．2 C．1 D．4

考研真题一 1.判断一个无向图是一棵树的条件是______。 2．有向图G的强连通分量是指______。【北京科技大学 1997 一、7】 3．一个连通图的______是一个极小连通子图。【重庆大学 2000 一、1】 4．具有10个顶点的无向图，边的总数最多为______。【华中理工大学 2000 一、7 （1分）】 5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。【燕山大学1998 一、6（1分）】

考研真题一 证明：具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树（在图论中树定义为无回路的连通图）。 1.（1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？ （2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？ （3）．如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？ 【复旦大学 1997 一（9分）】 4．证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。【东南大学 1993 四（10分）】

8.2 图的存储结构及实现 是否可以采用顺序存储结构存储图? 如何存储图? 图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图没有顺序映象的存储结构。但可以借助数组的数据类型表示元素之间的关系。 如何存储图? 考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。

8.2 图的存储结构及实现——邻接矩阵 1. 邻接矩阵（数组表示法） 基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系（图的顺序存储） 假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为： edges[i][j]＝ 1 若(vi, vj)∈E（或<vi, vj>∈E） 0 其它

邻接矩阵的结构型定义 引用： Mgraph g; Typedef struct { a=g.n Int no; //顶点编号 Char info; //顶点其他信息 }vertextype; //一维数组存储图中顶点的信息 Int edge[maxsize][maxsize]; //二维数组存储各顶点之间的邻接关系，边的关系用顶点的有序对表示 Int n,e; // n顶点数和 e边数 Vertextype vex[maxsize]; //存放结点信息 }MGraph; //边、结点共同表示出图的结构

8.2 图的存储结构及实现——邻接矩阵 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 无向图的邻接矩阵 V1 V2 V3 V4 vexs= V1 V2 V3 V4 V1 V2 V3 V4 V1 V3 V4 V2 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 edges= 无向图的邻接矩阵的特点？ 主对角线为 0 且一定是对称矩阵。

8.2 图的存储结构及实现——邻接矩阵 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 无向图的邻接矩阵 V1 V2 V3 V4 vexs= V1 V2 V3 V4 V1 V2 V3 V4 V1 V4 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 edges= V2 V3 如何求顶点i的度？ 邻接矩阵的第i行（或第i列）非零元素的个数。

8.2 图的存储结构及实现——邻接矩阵 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 无向图的邻接矩阵 V1 V2 V3 V4 vexs= V1 V2 V3 V4 V1 V2 V3 V4 V1 V4 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 edges= V2 V3 如何判断顶点 i 和 j 之间是否存在边？ 测试邻接矩阵中相应位置的元素edges[i][j]是否为1。

8.2 图的存储结构及实现——邻接矩阵 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 无向图的邻接矩阵 V1 V2 V3 V4 vexs= V1 V2 V3 V4 V1 V2 V3 V4 V1 V4 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 edges= V2 V3 如何求顶点 i 的所有邻接点？ 将数组中第 i 行元素扫描一遍，若edges[i][j]为1，则顶点 j 为顶点 i 的邻接点。

8.2 图的存储结构及实现——邻接矩阵 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 有向图的邻接矩阵 V1 V2 V3 V4 vexs= V1 V2 V3 V4 V1 V2 V3 V4 V1 V2 V3 V4 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 edges= 有向图的邻接矩阵一定不对称吗？ 不一定，例如有向完全图。

8.2 图的存储结构及实现——邻接矩阵 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 有向图的邻接矩阵 V1 V2 V3 V4 vexs= V1 V2 V3 V4 V1 V2 V3 V4 V1 V2 V3 V4 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 edges= 如何求顶点 i 的出度？ 邻接矩阵的第 i 行元素之和。

8.2 图的存储结构及实现——邻接矩阵 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 有向图的邻接矩阵 V1 V2 V3 V4 vexs= V1 V2 V3 V4 V1 V2 V3 V4 V1 V2 V3 V4 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 edges= 如何求顶点 i 的入度？ 邻接矩阵的第 i 列元素之和。

8.2 图的存储结构及实现——邻接矩阵 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 有向图的邻接矩阵 V1 V2 V3 V4 vexs= V1 V2 V3 V4 V1 V2 V3 V4 V1 V2 V3 V4 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 edges= 如何判断从顶点 i 到顶点 j 是否存在边？ 测试邻接矩阵中相应位置的元素edges[i][j]是否为1。

8.2 图的存储结构及实现——邻接矩阵 0 2 5 ∞ ∞ 0 ∞ ∞ ∞ ∞ 0 8 7 ∞ ∞ 0 网图的邻接矩阵可定义为： edges[i][j]＝ wij 若(vi, vj)∈E（或<vi, vj>∈E） 0 若i=j ∞ 其他 V1 V2 V3 V4 2 7 8 5 0 2 5 ∞ ∞ 0 ∞ ∞ ∞ ∞ 0 8 7 ∞ ∞ 0 edges=

邻接矩阵的结构型定义 引用： Mgraph g; Typedef struct { a=g.n Int no; //顶点编号 Char info; //顶点其他信息 }vertextype; //一维数组存储图中顶点的信息 Int edge[maxsize][maxsize]; //二维数组存储各顶点之间的邻接关系，边的关系用顶点的有序对表示 Int n,e; // n顶点数和 e边数 Vertextype vex[maxsize]; //存放结点信息 }MGraph; //边、结点共同表示出图的结构

8.2 图的存储结构及实现——邻接表 2. 邻接表 邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

8.2 图的存储结构及实现——邻接表 data firstedge adjvex nextedge 邻接表有两种结点结构：顶点表结点和边表结点。 data firstedge adjvex nextedge 顶点表 边 表 data：数据域，存放顶点信息。 firstedge：指针域，指向边表中第一个结点。 adjvex：邻接点域，边的终点在顶点表中的下标。 nextedge：指针域，指向边表中的下一个结点。

8.2 图的存储结构及实现——邻接表 Typedef struct arcNode { Int adjvex; // 边指向的结点的位置 Struct ArcNode *nextarc; // 指向下一条边的指针 Int info; //边的相关信息，如权重 }ArcNode; // 边表，以链表的形式存储 Typedef struct VNode{ Char data; // 顶点的信息 arcNode *firstarc; //指向第一条边的指针 }VNode; // 顶点表，通常以顺序结构的形式存储 Typedef struct { VNode adjlist[maxsize]; // 邻接表 Int n,e; // 图中顶点数n 和边数 e }AGraph; // 图的邻接表类型

无向图的邻接表 V1 V4 边表中的结点表示什么？ 每个结点对应图中的一条边， 邻接表的空间复杂度为O(n+e)。 V2 V3 V1 V2 3 ∧ 2 V1 V2 V3 V4 data firstedge

无向图的邻接表 V1 V4 如何求顶点 i 的度？ 顶点i的边表中结点的个数。 V2 V3 V1 V2 V3 V4 1 3 2 3 ∧ 2 V1 V2 V3 V4 data firstedge

无向图的邻接表 V4 V1 如何判断顶点 i 和顶点 j 之间是否存在边? 测试顶点 i 的边表中是否存在终点为 j 的结点。 V2 V3 3 ∧ 2 V1 V2 V3 V4 data firstedge

有向图的邻接表 V1 V2 如何求顶点 i 的出度？ 顶点 i 的出边表中结点的个数。 V3 V4 V1 V2 V3 V4 1 2 3 ∧ 3 V1 V2 V3 V4 data firstedge

有向图的邻接表 V1 V2 如何求顶点 i 的入度？ 各顶点的出边表中以顶点 i 为 终点的结点个数。 V3 V4 V1 V2 V3 V4 ∧ 3 V1 V2 V3 V4 data firstedge

有向图的邻接表 V1 V2 如何求顶点 i 的所有邻接点？ 遍历顶点 i 的边表，该边表中的所有终点都是顶点 i 的邻接点。 V3 V4 ∧ 3 V1 V2 V3 V4 data firstedge

网图的邻接表 V1 V2 2 V3 V1 V2 V4 7 5 8 V3 V4 data firstedge 2 1 5 2 1 2 3 2 1 V1 V2 V3 V4 1 2 3 data firstedge ∧ 5 2 8 3 7 0 V1 V2 V3 V4 2 7 8 5

8.2 图的存储结构及实现——邻接表 1 2 ∧ 3 ∧ v1 v2 v3 v4 1 ∧ 邻接表 V1 V2 V3 V4 3 ∧ 0 ∧ 2 ∧ 3 ∧ v1 v2 v3 v4 ∧ 2 3 1 ∧ 邻接表 V1 V2 V3 V4 3 ∧ 0 ∧ 2 ∧ v1 v2 v3 v4 1 2 3 逆邻接表 为了便于确定顶点的入度或以顶点vi为头的弧，可以建立一个有向图的逆邻接表。对每个顶点建立一个链接以vi为头的弧的表。

考研真题二： 12． 从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②） 条弧；如果是无向图，则共有（③）条边。【中科院软件所 1999 六、2（3分）】 ①．A．9 B．3 C．6 D．1 E．以上答案均不正确 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确 13．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。【南京理工大学1998一、4(2分）】

作业四、考研真题二 9．有向图的邻接表存储如下：（1）．画出其邻接矩阵存储；（2）．写出图的所有强连通分量；（3）．写出顶点a到顶点i的全部简单路径。【东北大学 1997 一、5 (5分)】

十字链表 2.4.1 结构图：将邻接表、逆邻接表合二为一。主要用于表示有向图。 和稀疏矩阵的十字链表结构相比：本质一样。 细节差别在于：行头表和列头表合并为了顶点表。

A B D E C 十字链表 等价结构：

邻接多重表 2.4.1 结构图 无向图的邻接表有50%的冗余。精简方法：每条边对应一个边结点。主要用于表示无向图。 邻接多重表结构

考研真题二 10．试用下列三种表示法画出网G 的存储结构，并评述这三种表示法的优、缺点： （1）．邻接矩阵表示法; （2）．邻接表表示法; 邻接矩阵表示法，有n个顶点的图占用n2个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。 邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n（n≥0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。 十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息（至少弧尾，弧头顶点在向量中的下标及从弧尾顶点发出及再入到弧头顶点的下一条弧的四个信息）。查询顶点的出度、入度、邻接点等信息非常方便。 邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息（如该边是否被访问）。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。 10．试用下列三种表示法画出网G 的存储结构，并评述这三种表示法的优、缺点： （1）．邻接矩阵表示法; （2）．邻接表表示法; 3）．其它表示法。 【华中理工大学2000 三（12分）】

算法实例一： 写出从图的邻接表表示转换为邻接矩阵表示的算法P203 一（7） Void MGraphToAGraph (MGraph &g1, AGraph g2) { ArcNode *p; Int i, j; For (i=1;i<=g1.n; ++i) For (j=1;j<=g1.n; ++j) g1.edges[i][j]=0; //初始化邻接矩阵 For (i=1;i<=g2.n; ++i) { P=g2.adjlist[i].firstarc; While (p) { g1.edges[i][p->adjvex]=P; P=p->nextarc; } } }// g1是邻接矩阵，g2是邻接表。

算法实例二 有向图用邻接表表示，图有n个顶点，试写一个算法求顶点K的入度。P203 一（8） Int count( AGraph g, int k) { ArcNode *p; Int i, sum; Sum=0; For(i=1;i<=g.n; ++i) { p=g.adjlist[i].firstarc; While(p!=NULL) { if (p->adjvex==k) { ++sum; break; } P=p->nextarc; } Return sum;

小结 理解图的相关概念和术语 图的存储方式 掌握： 题型：写出邻接矩阵，邻接表，画出图 存储结构的存储方式， 各种操作的实现思想 各种存储结构的特点和优势 题型：写出邻接矩阵，邻接表，画出图

第二节：图 图的遍历： 图的连通性问题 深度优先 广度优先 无向图的连通分量、有向图的强连通分量 关节点和重连通分量 最小生成树：普里姆算法、克鲁期卡尔算法 注意：各知识点的应用范围，求解思路，与类似的概念辨析

8.3 图的遍历 图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。 抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 下面仅讨论从某顶点出发遍历图的算法。

8.3 图的遍历 图的遍历操作要解决的关键问题 1 因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。 解决方案：附设访问标志数组visited[n] 2 在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？ 解决方案：深度优先遍历和广度优先遍历。

8.3 图的遍历－深度优先遍历 基本思想 ： Int visit [maxsize]; ⑴ 访问顶点v； ⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历； ⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。 Int visit [maxsize]; Void DFS(AGraph *G, int v) { ArcNode *p; Visit[v]=1; Visit(v); P=G->adjlist[v].firstarc; While(p!=NULL) { If(visit[p->adjvex]==0) DFS(G,p->adjvex); P=p->nextarc; } 是树的先根遍历的扩展 是求有向图的强连通分量的有效方法 适用于有向图和无向图

8.3 图的遍历 －深度优先遍历 图的逻辑结构 图的邻接表存储结构 以顶点0为起点的DFS：0，1，4，3，2

8.3 图的遍历 －深度优先遍历 Int visit [maxsize]; Void DFS(AGraph *G, int v) { ArcNode *p; Visit[v]=1; Visit(v); P=G->adjlist[v].firstarc; While(p!=NULL) { If(visit[p->adjvex]==0) DFS(G,p->adjvex); P=p->nextarc; } Void trave (BTNode *p) { if (p!=Null) visit(p); Trave (p->lchild); Trave (p->rchild); }//树的前序递归遍历

8.3 图的遍历 －广度优先遍历 Int visit [maxsize]; Void BFS(AGraph *G, int v,int visit[maxsize]) { ArcNode *p; Int que[maxsize]; front=0,rear=0; Int j; Visit[v]=1; Visit(v); rear=(rear+1)%maxsize; que[rear]=v; While (front!=rear) { front=(front+1) %maxsize; J=que[front]; P=G=>adjlist[j].firstarc; While(p!=NULL) { If(visit[p->adjvex]==0) { visit(P->adjvex); visit [P->adjvex] =1; rear= (rear+1)%maxsize; que[rear]=p->adjvex; } P=p->nextarc; }}} 8.3 图的遍历 －广度优先遍历 基本思想 ： ⑴ 访问顶点v； ⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk； ⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

8.3 图的遍历－广度优先遍历 以顶点0为起点的BFS：0，1，3，4，2 以顶点3为起点的BFS：3，1，0，4，2 已知邻接表，求遍历序列。

Int que[maxsize]; front=0,rear=0; Int visit [maxsize]; Void BFS(AGraph *G, int v,int visit[maxsize]) { ArcNode *p; Int que[maxsize]; front=0,rear=0; Int j; Visit[v]=1; Visit(v); rear=(rear+1)%maxsize; que[rear]=v; While (front!=rear) { front=(front+1) %maxsize; j=que[front]; P=G->adjlist[j].firstarc; While(p!=NULL) { If(visit[p->adjvex]==0) { visit(P->adjvex); visit [P->adjvex] =1; rear= (rear+1)%maxsize; que[rear]=p->adjvex; } P=p->nextarc; }}} void level(BTNode *p) // 层次遍历二叉树 { int front, rear; BTNode *que[maxsize] // 定义一个循环队列，用于记录将要访问的层次上的结点 front=rear=0; //初始化循环队列 BTNode *q; If(p!=Null) { rear=(rear+1)%maxsize; Que[rear]=p; //根结点入队 While(front!=rear) //当队列为空时循环 { front=(front+1)%maxsize; Q=que[front];//队头结点出队 Visit(q); If(q->lchild!=Null) Que[rear]=q->lchild; } If(q->rchild!=Null) { rear=(rear+1)%mazsize; Que[rear]=q->rchild; } } } }

8.3 图的遍历 V1 V1 V2 V3 V2 V3 V4 V5 V6 V7 V4 V5 V6 V7 V8 V8 由深度优先遍历得到的为深度优先生成树，由广度优先遍历得到的为广度优先生成树，二者仅是顶点访问顺序不同 时间复杂度：邻接矩阵存储：o(n2)邻接表存储：O(n+e) V1 V1 V2 V3 V2 V3 V4 V5 V6 V7 V4 V5 V6 V7 V8 V8 （a）深度优先生成树 （b） 广度优先生成树

8.3 图的遍历－二种遍历的说明 一个连通图的生成树可能不唯一，由不同的遍历次序、从不同顶点出发进行遍历都会得到不同的生成树。 对于非连通图，通过图的遍历，将得到的是生成森林。 应用： 深度优先搜索可以求有向图的强连通分量，可以求得图的关节点，判别图是否是重连通 广度优先搜索可以得到从根顶点A到其它顶点的最少路径。

考研真题一 15. 下列说法不正确的是（ ）。青岛大学 02 二、9 （2分 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 15. 下列说法不正确的是（ ）。青岛大学 02 二、9 （2分 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程 16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。【南京理工001 一、14 （1.5分）】 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b

考研真题一 15．下面的邻接表表示一个给定的无向图 （1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列；

考研真题一 16．给出图G： （1）．画出G的邻接表表示图； 3 10 5 7 8 4 2 1 6 9

算法例题 一 图采用邻接表存储，设计一个算法，判断顶点i和 顶点j 之间是否有路径。 Int DFSTrave (AGraph *G, int I, int j) { Int k; For (k=1; k<=G->n; ++k) Visit[k]=0; DFS(G,i); If ( visit [ j ]==1) Return 1; Else return 0; }

关节点和重连通分量 关节点的含义：若在删去顶点V及和V相关联的各边之后，将图的一个连通分量分割成二个或二个以上的连通分量，则称顶点V为该图的关节点 重连通图的含义：一个没有关节点的连通图为重连通图。即任意一对顶点间至少存在二条路径。 应用：网的经济性，可靠性。战争中，破坏运输网中的关节点即切断运输线。 注意对比：连通图，强连通图，重连通图，关节点

关节点和重连通分量 求关节点的算法：利用深度优先搜索可求得图的关节点。O(n+e) 若深度优先生成树的根有二棵或二棵以上的子树，则此根顶点必为关节点。 若深度优先生成树的某个非叶子结点v,其某棵子树的根和子树中的其它结点均没有指向v的祖先的回边，则v为关节点。

8.4 最小生成树 生成树的代价：设G=(V，E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。 8.4 最小生成树 在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？ 生成树的代价：设G=(V，E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。 最小生成树：在图G所有生成树中，连通网的代价最小的生成树称为最小生成树。 最小生成树的概念可以应用到许多实际问题中。

8.4.2 最小生成树算法——Prim算法 Prim算法基本思想： 初始时从V中任取一个顶点（如v1），将其放入U中，使U={v1}，这样集合U与集合VU就构成图G的一个割。 只要U是V真子集，就不断进行如下的贪心选择：选择一条权值最小的交叉边（vi, vj），其中vi∈U, vj ∈VU，并把该边（vi, vj）和其不在最小生成树中的顶点vj分别加入T的顶点集U和边集TE中。 这个过程不断重复直到图G中的n个顶点均被加入到最小生成树T中为止。 假设G=(V, E)是一个无向连通网，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u, v)的最小生成树。

8.4.2 最小生成树算法——Prim算法 Prim算法的关键： p152 如何找到连接U和V-U的最短边。 利用MST性质，可以用下述方法构造候选最短边集： 对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。

8.4.2 最小生成树算法——Prim算法 B 34 12 U={A} V-U={B, C, D, E, F} cost={(A, B)34, (A, C)46, (A, D)∞,(A, E)∞,(A, F)19} A E 19 26 F 46 25 25 38 C D 17 对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。

8.4.2 最小生成树算法——Prim算法 B 34 12 U={A, F} V-U={B, C, D, E} cost={(A, B)34,(F, C)25, (F, D)25,(F, E)26} A E 19 26 F 46 25 25 38 C D 17 对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。

8.4.2 最小生成树算法——Prim算法 B 34 12 U={A, F, C} V-U={B, D, E} cost={(A, B)34, (C, D)17, (F, E)26} A E 19 26 F 46 25 25 38 C D 17 对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。

8.4.2 最小生成树算法——Prim算法 B 34 12 U={A, F, C, D} V-U={B, E} cost={(A, B)34, (F, E)26} A E 19 26 F 46 25 25 38 C D 17 对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。

8.4.2 最小生成树算法——Prim算法 B 34 12 U={A, F, C, D, E} V-U={B} cost={(E, B)12} A E 19 26 F 46 25 25 38 C D 17 对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。

8.4.2 最小生成树算法——Prim算法 B 34 12 U={A, F, C, D, E, B} V-U={ } A E 19 26 F 46 25 25 38 C D 17

8.4.2 最小生成树算法——Prim算法 算法分析： Void Prim (MGraph g, int v0, int &sum) 从候选边中选出权值最小的边输出，并将与该边另一端相接的顶点v并入生成树中。考查所有剩余顶点vi，如果(v,vi)的权值比lowcost[vi]小，则用(v,vi)的权值更新lowcost[vi]。直到其他的n-1个顶点都并入到生成树中。 8.4.2 最小生成树算法——Prim算法 Void Prim (MGraph g, int v0, int &sum) { Int lowcost[maxsixe],vset[maxsize], v; Int i,j,k,min; V=v0; for(i=1;i<=g.n; ++i) { lowcost[i]=g.edges[v0][i]; Vset[i]=0;} Vset[i]=1; Sum=0; for(i=1; i<g.n; ++i) { min=INF; for(j=1;j<=g.n;++j) If (vest[j]==0&&lowcost[j]<min) {min=lowcost[j]; K=j; } Vset[k]=1; v=k; sum+=min; for(j=1;j<=g.n;++J) if(vset[j]==0&& g.edges[v][j]<lowcost[j]) lowcost[j]=g.edges[v][j]; } //初始化候选边，设置结点未访问 //寻找更新最小值 //设置访问标记，将K并到树中，更新V点 //以刚并入的顶点V为媒介更新候选边

8.4.2 最小生成树算法——Prim算法 性能分析： 思想：从U＝{u0}开始，在所有u∈U,v∈V-U的边(u,v) ∈E中找一条代价最小的边(u0,v0)并入最小生成树中，同时v0并入U，直到U＝V 时间复杂度：O（n2），与边无关。 适用的情况：稠密图

8.4.3 最小生成树——Kruskal算法 Kruskal算法基本思想： 设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。每次找出候选边中权值最小的边，将该边加入生成树中。 若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路。如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。

8.4.3 最小生成树——Kruskal算法 B B 34 12 A E 19 26 A E F F 46 25 25 38 C D C D 17 连通分量＝{A}, {B}, {C}, {D}, {E}, {F}

8.4.3 最小生成树——Kruskal算法 B B 34 12 12 A E 19 26 A E F F 46 25 25 38 C D 17 连通分量＝{A}, {B}, {C}, {D}, {E}, {F} 连通分量＝{A}, {B, E}, {C}, {D}, {F}

8.4.3 最小生成树——Kruskal算法 B B 34 12 12 A E 19 26 A E F F 46 25 25 38 C D 17 17 连通分量＝{A, F}, {B, E}, {C}, {D} 连通分量＝{A, F}, {B, E}, {C, D}

8.4.3 最小生成树——Kruskal算法 B B 34 12 12 A E 19 26 A 19 E F F 46 25 25 38 C D C D 17 17 连通分量＝{A}, {B, E}, {C}, {D}, {F} 连通分量＝{A, F}, {B, E}, {C}, {D}

8.4.3 最小生成树——Kruskal算法 B B 34 12 12 A E 19 26 A 19 E F F 46 25 25 25 38 C D C D 17 17 连通分量＝{A, F}, {B, E}, {C, D} 连通分量＝{A, F, C, D}, {B, E}

8.4.3 最小生成树——Kruskal算法 B B 34 12 12 A E 19 26 A 19 E 26 F F 46 25 25 38 C D C D 17 17 连通分量＝{A, F, C, D}, {B, E} 连通分量＝{A, F, C, D, B, E}

8.4.3 最小生成树——Kruskal算法 1. 初始化：U=V； TE={ }； 2. 循环直到T中的连通分量个数为1 2.1 在E中寻找最短边(u，v); 2.2 如果顶点u、v位于T的两个不同连通分量，则 2.2.1 将边(u，v)并入TE； 2.2.2 将这两个连通分量合为一个； 2.3 在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；

8.4.3 最小生成树——Kruskal算法 Typdef struct { int a, b; int w; } Road; //a,b为一条边上的二个顶点 Road road[maxsize]; int v[maxsize]; Int getroot(int a) { while(a!=v[a]) a=v[a]; return a; } Void Kruskal (MGraph g, int &sum, Road road[ ]) { Int i; int N, E, a, b; N=g.n; E=g.e; sum=0; For(i=1; i<=N;++i) v[i]=i; //每个顶点都是一个连通分量 Sort(road,E); // 对road数组中的E条边按权值大小排序 For(i=1;i<=E; ++i) { a=getRoot(road[i].a); b=getRoot(road[i].b); If(a!=b) { v[a]=b; sum+=road[i].w; } } //在并查集中查树根结点 //如果不在同一个连通图中，则将二树并成一个连通图

8.4.3 最小生成树——Kruskal算法 性能分析： 思想：将n个结点看成是n个连通分量，从边集中选择最小边，若该边依附的顶点在T中不同的连通分量上，则将此加入T中，否则舍去此边而选择下一条代价最小的边。直到最后连成一个连通分量。 时间复杂度：算法时间主要取决于排序，O(eloge) 适用情况：无向图，稀疏图 算法利用的工具：

讨论： 图的最小生成树唯一吗？为什么？ 什么样的图其最小生成树是唯一的？ 有多条边权值相同且同为最小值，就会产生多种最小生成树。 要产生唯一一棵最小生成树，所有边的权值都为不相同的图才能满足条件。

考研真题二 20. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 【合肥工业大学 2001 一、2 （2分）】 O(n) B. O(n+e) C. O(n2) D. O(n3) 21. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1 ），下面步骤重复n-1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。 【南京理工大学 1997 一、11_14 （8分）】 （1）A．VT，ET为空 B．VT为所有顶点，ET为空 C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边 （2）A. 选i属于VT，j不属于VT，且（i，j）上的权最小 B．选i属于VT，j不属于VT，且（i，j）上的权最大 C．选i不属于VT，j不属于VT，且（i，j）上的权最小 D．选i不属于VT，j不属于VT，且（i，j）上的权最大 （3）A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET C. 顶点j加入VT，（i,j）从ET中删去 D顶点i,j加入VT，（i,j）加入ET （4）A．ET 中为最小生成树 B．不在ET中的边构成最小生成树 C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解

考研真题二： 28．G=(V,E)是一个带有权的连通图,则： （1）．请回答什么是G的最小生成树； （2）．G为下图所示,请找出G的所有最小生成树。【北方交通大学 1993 二 （12分）】 1 4 3 5 2 9 8 7 6 无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树 最小生成树有两棵。给出顶点集合和边集合，边以三元组（Vi,Vj, W）形式，其中W代表权值。V（G）={1，2，3，4，5} E1(G)={(4，5，2)，（2，5，4），（2，3，5），（1，2，7）}； E2(G)={(4，5，2），（2，4，4），（2，3，5），（1，2，7）}

考研真题 二： 25.在什么情况下，Prim算法与Kruskual算法生成不同的MST？ 【西安电子科技大学 2000计应用 一、11 （5分）】 在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST。

算法 P203（9） 写出以邻接表为存储结构的图的深度优先搜索DFS算法的非递归算法。 Void DFS1 (AGraph *g, int v) { ArcNode *p; int i, k, visit [maxsixe]; Int stack[maxsixe], top=-1; For (i=1; i<=g->n; ++i) visit[i]=0; //设置访问标记 Visit(v); visti[v]=1; stack-[++top]=v; While(top!=-1) { k=stack[top]; P=g->adjlist[k].firstacrc; While(p!=null && visit [p->adjvex]==1) p=p->nextarc; If(p==NULL) --top; Else { Visit(p->adjvex); visit[p->adjvex ]=1; stack[++top] =p->adjvex; } }

小结： 图的遍历：深度优先，广度优先 图的连通性问题 深度优先生成树、广度优先生成树，写出遍历结点序列，路径，最小成生树 无向图的连通分量、有向图的强连通分量 最小生成树：普里姆算法、克鲁期卡尔算法 关节点和重连通分量 深度优先生成树、广度优先生成树，写出遍历结点序列，路径，最小成生树

复习： 理解图的相关概念和术语 图的存储方式 掌握： 图的遍历：深度优先，广度优先 存储结构的存储方式， 各种操作的实现思想 各种存储结构的特点和优势 图的遍历：深度优先，广度优先 题型：写出邻接矩阵，邻接表，画出图、深度优先生成树、广度优先生成树，写出遍历结点序列，路径

第三节、图的应用 有向无环图的应用 AOV网：顶点表示活动的网 拓扑排序 AOE网：边表示活动的网 关键路径、关键活动 最短路径： 单源点的最短路径Jijkstra算法 每一对顶点之间的最短路径，Floyd算法

有向无环图及其应用 有向无环图：DAG,directed acycline graph 1、描述工程的进行过程： 2、检查图是否有环： 工程能否顺利进行（AOV网，拓扑排序） 估算整个工程完成所必须的最短时间。（关键活动，关键路径－－AOE网） 2、检查图是否有环： 无向图：深度优先遍历过程中遇到回边，则必有环。 有向图：拓扑排序

8.6 AOV网与拓扑排序 什么AOV网？ (Activity On Vertices) AOV网：在一个表示工程的有向图中，用顶点表示活动，用有向边<Vi, Vj> 表示活动的前后次序。Vi 必须先于活动Vj 进行。称这样的有向图为顶点表示活动的网，简称AOV网。 AOV网中出现回路意味着什么？ p164 某项活动以自已为先决条件。这是荒谬的。

8.6 AOV网与拓扑排序 AOV网特点： (Activity On Vertices)

AOV网 C3 C5 C1 C4 C7 C2 C6 编号 课程名称 先修课 C1 高等数学 无 C2 计算机导论 C3 离散数学 C4 程序设计 C1, C2 C5 数据结构 C3，C4 C6 计算机原理 C2，C4 C7 数据库原理 C4，C5，C6 C1 C2 C3 C4 C6 C5 C7

拓扑排序 拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。

拓扑排序 基本思想： ⑴ 从AOV网中选择一个没有前驱的顶点并且输出； ⑵ 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧；

拓扑排序 C3 C5 C1 C4 C7 C2 C6 拓扑序列： C1,

拓扑排序 C3 C5 C4 C7 C2 C6 拓扑序列： C1, C2,

拓扑排序 C3 C5 C4 C7 C6 拓扑序列： C1, C2, C3,

拓扑排序 C5 C4 C7 C6 拓扑序列： C1, C2, C3, C4,

拓扑排序 C5 C7 C6 拓扑序列： C1, C2, C3, C4, C5,

拓扑排序 C7 C6 拓扑序列： C1, C2, C3, C4, C5, C6,

拓扑排序 C7 拓扑序列： C1, C2, C3, C4, C5, C6, C7,

拓扑排序算法框架 1、扫描邻接表，计算各顶点的入度； 2、将入度为0 的顶点入栈； 3、while ( 栈非空 ) { 将栈顶顶点v 弹出并输出之； 检查v的出边，将每条出边<v,u>终点u的入度减1， 若u的入度变为0，则把u推入栈； } 3、若输出的顶点数小于n（变化后仍有度不为0的结点），则输出“有回路”；否则拓扑 排序正常结束。

拓扑排序算法的具体描述 while ( top!=-1) void TopSort (ALGraph &G) {//图采用邻接表结构 Int i, j ,count=0; //对输出顶点计数 int stack[maxsize], top=-1; ArcNode * p; for (i=1; i=<G.n; ++i) //使入度为0的顶点入栈 if (G->adjlist[i].count==0) stack[++top]=i; //Push(S,i); if (n==G->n) return OK ; else return 0; } while ( top!=-1) { i=stacj[top--]; //Pop(S, i); cout<<G.getVexValue(i)<<“ ”; ++count; P=G->adjlist[i].firstarc; While(p=!NULL) { j=p->adjvex; --(G->adjlist[j].count; //由顶点i引出的边所指向的顶点j的入度减1 if ( G->adjlist[j].count==0 ) stack[+++top]=j; // Push(S,k); P=p->nextarc; //使新的入度为0的j顶点入栈 }

算法分析 设AOV网有n个顶点，e条边。初始建立入度为0 的顶点栈，要检查所有顶点一次，执行时间为O(n)；排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为O(n+e)，所以总的时间复杂度为O(n+e)。

考研真题一 40．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。 【北京理工大学 2001 七、3 （2分）】 42．在 AOV网 中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。 【厦门大学 1999 一、2】 43. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为______的顶点，并进栈； （2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是______； （3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。 【南京理工大学 1996 二、3 （6分）】 19．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学 2000 4、2（4分）】 A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径

考研真题一 44．已知图的邻接矩阵为：当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出：【同济大学 98 一 (12分 )】 （1）以顶点V1为出发点的唯一的深度优先遍历； （2）以顶点V1为出发点的唯一的广度优先遍历； （3）该图的拓扑有序序列。 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 1

*8.7 AOE网与关键路径 如果在带权无环有向图中 用有向边表示一个工程中的各项活动(Activity) 用边上的权值表示活动的持续时间(Duration) 用顶点表示事件(Event) 则这样的有向图叫做用边表示活动的网络，简称AOE (Activity On Edges)网。

AOE网在某些工程估算方面非常有用。例如，可以使人们了解： (1) 完成整个工程至少需要多少时间(假设网络中没有环). (2) 为缩短完成工程所需的时间, 应当加快哪些活动. 在AOE网中, 有些活动顺序进行，有些活动并行进行。

从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。 完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。 因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。

事件Vi 的最早可能开始时间Ve(i) vertex early 是从源点V0 到顶点Vi 的最长路径长度。 事件Vi 的最迟允许开始时间Vl[i] vertex later 是在保证汇点Vn-1 在Ve[n-1] 时刻完成的前提 下，事件Vi 的允许的最迟开始时间。 活动ak 的最早可能开始时间 e[k] 设活动ak 在边< Vi , Vj >上，则e[k]是从源点 V0到顶点Vi 的最长路径长度。 e[k] = Ve[i]。 活动ak 的最迟允许开始时间 l[k] l[k]是在不会引起时间延误的前提下，该活动允许的最迟开始时间 l[k] = Vl[j] - dur(<i, j>)。其中，dur(<i, j>)是完成ak 所需的时间。

时间余量 l[k] - e[k] 表示活动ak 的最早可能开始时间和最迟允许开始时间的时间余量。l[k] == e[k]表示活动ak 是没有时间余量的关键活动。显然，关键路径上的所有活动都是关键活动。 为找出关键活动, 需要求各个活动的 e[k] 与 l[k]，以判别是否 l[k] == e[k]. 为求得e[k]与 l[k]，需要先求得从源点V0到各个顶点Vi 的 Ve[i] 和 Vl[i]。

从Ve[0] = 0开始，向前递推 求Ve[i]的递推公式 < Vi, Vj >  S2, i = 1, 2, , n-1 其中, S2是所有从Vi指向顶点Vj 的有向边< Vi , Vj>的集合。 从Vl[n-1] = Ve[n-1]开始，反向递推 < Vi, Vj >  S1, i = n-2, n-3, , 0 其中, S1是所有从顶点Vi 发出的有向边< Vi , Vj >的集合。

设活动ak (k = 1, 2, …, e)在带权有向边< Vi , Vj > 上, 它的 这两个递推公式的计算必须分别在拓扑有序及逆拓扑有 序的前提下进行。 设活动ak (k = 1, 2, …, e)在带权有向边< Vi , Vj > 上, 它的 持续时间用dur (<Vi , Vj >) 表示，则有 e[k] = Ve[i]； l[k] = Vl[j] - dur(<Vi , Vj >)；k = 1, 2, …, e。 这样就得到计算关键路径的算法。 计算关键路径时，可以一边进行拓扑排序一边计算各顶 点的Ve[i]，并按拓扑有序的顺序对各顶点重新进行了编 号。算法在求Ve[i], i=0, 1, …, n-1时按拓扑有序的顺序计 算，在求Vl[i], i=n-1, n-2, …, 0时按逆拓扑有序的顺序计 算。

6 16 v5 v1 v2 v3 v4 v6 v7 v8 v9 4 6 5 1 2 9 7 6 16 18 7 18 7 14 4 14 6 5 7 8 10

v5 v1 v2 v3 v4 v6 v7 v8 v9 4 6 5 1 2 9 7 16 14 18 10 8 活动 1-2 1-3 1-4 2-5 3-5 4-6 5-7 5-8 6-8 7-9 8-9 e 6 4 5 7 16 14 l 2 3 8 10 e-l

v5 v1 v2 v7 v8 v9 6 1 9 7 4 2 16 14 18

说明： 1、并不是加快任何一个关键活动都可以缩短整个工程的工期。只有加快那些包括在所有关键路径上的关键活动才能达到这个目的。 2、关键活动的速度提高是有限度的 计算弧的活动最早开始时间和最迟开始时间的复杂度为O(e)，所以关键路径的时间复杂度o(n+e)

考研真题二 48．下图是带权的有向图G的邻接表表示法，求： （1）以结点V1出发深度遍历图G所得的结点序列； （3）从结点V1到结点V6的最短路径； （4）从结点V1到结点V6的关键路径。 【青岛海洋大学 1999 四（10分）】 V1 V2 V4 V3 V5 V6 a1=3 a2=2 a3=2 a4=3 a5=4 a6=3 a7=2 a8=1

8.5 最短路径 在非网图中，最短路径是指两顶点之间经历的边数最少的路径。可由广度优先生成树求得根顶点A到顶点B的最少路径。 B AE：1 D C AE：1 ADE：2 ADCE：3 ABCE：3

8.5 最短路径 在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。 B AE：100 A C ADE：90 ADCE：60 50 30 100 20 60 AE：100 ADE：90 ADCE：60 ABCE：70

8.5 最短路径 (Shortest Path) 两种最短路径问题： 求解算法 单源最短路径 — Dijkstra算法 1. 求图中某顶点到其余各顶点的最短路径问题，也称为单源最短路径问题； 2.求每对顶点之间的最短路径问题 求解算法 单源最短路径 — Dijkstra算法 任意顶点对之间的最短路径 — Floyd算法

8.5 最短路径 单源点最短路径问题 问题描述：给定带权有向图G＝(V, E)和源点v∈V，求从v到G中其余各顶点的最短路径。 迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。

设置一个集合S，用于存放已求出的最短路径的顶点，则尚未确定最短路径的顶点属于集合VS。 引入一个辅助数组dist[]。它的每一个分量dist[i]表示当前所确定的从源点v0到终点vi 的最短路径的长度

{ 在集合VS中循环选择距离最小的顶点vj； S = S + {vj }; 调整集合VS中顶点的距离值； } Dijkstra算法的基本过程可描述如下 S = {v0}; //顶点v0为源点 设置集合VS中各顶点的初始距离值； while (集合S中顶点数< n) //从剩余顶点中选出一个顶点计算其最短路径长度 { 在集合VS中循环选择距离最小的顶点vj； S = S + {vj }; 调整集合VS中顶点的距离值； } 算法复杂度：O(n2)

dist[i]=Min{dist[i], dist[j] + cost(j,i) }

8.5 最短路径——Dijkstra算法 B S={A} A→B:(A, B)10 A→C:(A, C)∞ A→D: (A, D)30 A→E: (A, E)100 10 50 A A C 30 10 100 20 E D 60

8.5 最短路径——Dijkstra算法 B B S={A, B} A→B:(A, B)10 A→C:(A, B, C)60 A→D: (A, D)30 A→E: (A, E)100 10 50 A A C 30 10 100 20 E D 60

8.5 最短路径——Dijkstra算法 B B S={A, B, D} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, E)90 10 50 A A C 30 10 100 20 E D D 60

8.5 最短路径——Dijkstra算法 B B S={A, B, D, C} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, C, E)60 10 50 A A C C 30 10 100 20 E D D 60

每一对顶点之间的最短路径 问题描述：给定带权有向图G＝(V, E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。 方法1：每次以一个顶点为源点，调用Dijkstra算法n次。显然，时间复杂度为O(n3)。 方法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。

Floyd计算有向图中任意一对顶点间的最短路径 算法思想： 辅助工具： 矩阵A记录当前已经求得的任意二个顶点最短路径的长度 矩阵B记录当前二个顶点最短路径上要经过的中间顶点。 //A和B都是二维数组。 For (k=0；k<g.n; ++k) //以K为中间点，检测所有的顶点对<i,j> For (i=0；i<g.n; ++i) For (j=0；j<g.n; ++j) if (A[i] [j]>A[i] [k]+A[k][j]) A[i] [j]=A[i] [k]+A[k][j]); path[i][j]=k; 算法复杂度：O(n3)

8.5 最短路径——Floyd算法 a 0 4 11 6 0 2 3 ∞ 0 3 4 11 6 c b 2 有向网图 邻接矩阵

8.5 最短路径——Floyd算法 0 4 11 6 0 2 3 ∞ 0 dist-1 = a ab ac c b ba bc ca 0 4 11 6 0 2 3 ∞ 0 dist-1 = a c b 3 4 6 11 2 ab ac ba bc ca path-1 = 初始化

8.5 最短路径——Floyd算法 0 4 11 6 0 2 3 ∞ 0 0 4 11 6 0 2 3 7 0 a c b dist-1 = 0 4 11 6 0 2 3 ∞ 0 0 4 11 6 0 2 3 7 0 a c b 3 4 6 11 2 dist-1 = dist0 = ab ac ba bc ca ab ac ba bc ca cab path-1 = path0 = 第1次迭代 中间点为a

8.5 最短路径——Floyd算法 0 4 11 0 4 6 6 0 2 6 0 2 3 7 0 3 7 0 dist0 = dist1 = 0 4 11 6 0 2 3 7 0 0 4 6 6 0 2 3 7 0 a c b 3 4 6 11 2 dist0 = dist1 = ab ac ba bc ca cab ab abc ba bc ca cab path0 = path1 = 第2次迭代 中间点为b

8.5 最短路径——Floyd算法 a c b 3 4 6 11 2 0 4 6 6 0 2 3 7 0 0 4 6 5 0 2 3 7 0 dist1 = dist2 = 第3次迭代 中间点为c ab abc ba bc ca cab ab abc bca bc ca cab path1 = path2 = 虽然在某条路径上新加入了已访问的结点，但其代价比从源直接到目标更小些。

FLOYD算法 Void Floyd(MGraph g, int A[ ][maxsize], int path [ ][maxsize]) { Int I, j, k; For(i=0;i<g.n; ++i) //初始化数组 For(j=0;j<g.n; ++j) { A[i][j]=g.edges[i][j]; Path[i][j]=-1 } For (k=0；k<g.n; ++k) //以K为中间点，检测所有的顶点对<i,j> For (i=0；i<g.n; ++i) For (j=0；j<g.n; ++j) if (A[i] [j]>A[i] [k]+A[k][j]) { A[i] [j]=A[i] [k]+A[k][j]); path[i][j]=k; } } 算法复杂度：O(n3)

考研真题三 P203 6 用Dijkstra算法求出从顶点1到其他顶点的最短路径，要求给出求解过程。 1 2 5 4 3 6 9 7

考研真题三P205 二2 有一个6个顶点（顶点编号0－5）的有向带权图G，其邻接矩阵A为上三角矩阵，它的压缩存储为 要求： 4 6 ∞ 5 3

小结： 有向无环图的应用 拓扑排序 AOV网：顶点表示活动的网 AOE网：边表示活动的网 关键路径、关键活动 最短路径： 单源点的最短路径Jijkstra算法 每一对顶点之间的最短路径，Floyd算法

有向无环图及其应用 * * * + e + + + * + * c d c d b + c d b c d 公共子式的表达式: 树与图的对比，节省存储空间 * * * + e + + + * + * c d c d b + c d b c d

Dijkstra算法描述: void Dijkstra (MGraph<T> &G, int v0, int path[ ]) { bool* S=new bool[G.vexterNum()]; float *dist=new float[G.vexterNum()];

for (v=0; v<G.vexterNum(); ++v) { S[v]=0; //集合S置空 dist[v]=G.getEdgeValue(v0,v); if (dist[v]<INFINITY) //路径初始化 path[v]=v0; //path表示路径有技巧 else path[v]=-1; //表示顶点v无前驱顶点 }

dist[v0] = 0; S[v0] = 1; // 将顶点v0加入S集 for (i=1;i<G.vexterNum();++i) { min=INFINITY; for ( j=0;j<G.vexterNum(); ++j ) //查找当前集合V-S中到源点距离最短的顶点 if ( S[j]==0 && dist[j]<min ) { k=j; min=dist[j]; }

S[k]=1; for (w=0;w<G.vexterNum();++w) // 更新集合V-S中各顶点的当前最短路径 { if ( S[w]==0 && dist[k]+G.getEdgeValue(k,w)<dist[w] ) { dist[w]=dist[k]+G.getEdgeValue(k,w); path[w]=k; } } outputPath(path); //输出最短路径 delete [ ]S; delete [ ]dist;