第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用

Presentation on theme: "第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用"— Presentation transcript:

1 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用
第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径

2 7.1 图的定义和术语 图(Graph)——由一个顶点集V和一个边集E构成的数据结构。 Graph = (V, E )
7.1 图的定义和术语 图(Graph)——由一个顶点集V和一个边集E构成的数据结构。 Graph = (V, E ) 其中，V = { x | x  某个数据对象} 是非空有限的顶点集合； E = {(x, y) | x, y  V } 或 E = {<x, y> | x, y  V && Path (x, y)} 是有限的顶点之间关系的集合，(x,y)也叫做边(edge)集合,它是无方向的; Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的,所以<x,y>也叫做弧(arc)的集合,x称为弧尾或始点,y称为弧头或终点.

3 7.1 图的定义和术语 有向图——有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集
7.1 图的定义和术语 有向图——有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头 无向图——无向图G是由两个集合V(G)和E(G)组成的 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)

4 7.1 图的定义和术语 例7.1 2 4 5 1 3 6 G1 图G1中：V(G1)={1,2,3,4,5,6}
7.1 图的定义和术语 例7.1 2 4 5 1 3 6 G1 图G1中：V(G1)={1,2,3,4,5,6} E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>} 例7.2 1 5 7 3 2 4 G2 6 图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)}

5 7.1 图的定义和术语 无向完全图(Completed graph) —n个顶点的无向图有n(n-1)/2条边（最大边数是n(n-1)/2）
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)

6 7.1 图的定义和术语 有向图 有向完全图 无向 完全图 无向图(树) 完全图

7 7.1 图的定义和术语 权——与图的边或弧相关的数 网——带权的有向图叫有向网，带权的无向图叫无向网

8 7.1 图的定义和术语 子图——如果图G(V,E)和图G’(V’,E’),满足： V’V，E’E 则称G‘为G的子图

9 7.1 图的定义和术语 邻接点(或相邻点),关联 如果 e=(u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点或相邻顶点;称边e与顶点u ,v 关联; 如果 e=<u, v> 是 E(G) 中的一条弧，则称 u 邻接到v,v邻接于u,也称e与u,v关联;称弧e与顶点u ,v 关联;

10 7.1 图的定义和术语 顶点的度（于树的度不同） 无向图中，顶点的度为与每个顶点相连的边数,记作TD(v) 有向图中，顶点的度分成入度与出度
7.1 图的定义和术语 顶点的度（于树的度不同） 无向图中，顶点的度为与每个顶点相连的边数,记作TD(v) 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目,记为ID(v) 出度：以该顶点为尾的弧的数目,记为OD(v) 一个顶点的度数等于该顶点的入度与出度之和,即TD(v)=OD(v)+ID(v)

11 7.1 图的定义和术语 路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E 或 <Vij-1,Vij>E,(1<jn) 路径长度——沿路径边的数目或沿路径各边权值之和 简单路径——序列中顶点不重复出现的路径 回路(环)——第一个顶点和最后一个顶点相同的路径 简单回路(简单环)——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

12 7.1 图的定义和术语 V0V1V3V2 V0V1V3V2V0V1V2 V0V1V3V0

13 7.1 图的定义和术语 连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 A B C D E F G I J L H M K 无向图G A B C D E H M F G I J L K 无向图G的三个连通分量

14 7.1 图的定义和术语 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 强连通图 有向图G 有向图G的两个 强连通分量

15 7.1 图的定义和术语 生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。 如果在生成树上添加1条边，必定构成一个环
7.1 图的定义和术语 生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。 如果在生成树上添加1条边，必定构成一个环 若图中有n个顶点，却少于n-1条边，必为非连通图。 A B C D E H M 无向图G 无向图G的生成树

16 7.1 图的定义和术语 生成森林： 由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。 有向图G 有向图G的生成森林

17 7.1 图的定义和术语 本章只讨论简单图,有两类图形不在本章讨论之列：

18 图的抽象数据类型定义 ADT Graph { 数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。
数据关系 R：R={VR}；VR={<v,w>|v,w∈V 且 P(v,w), <v,w>表示从v到w的弧， 谓词P(v,w)定义了弧<v,w>的意义或信息} 基本操作P： }

19 基本操作 CreatGraph(&G, V, VR) // 按定义(V, VR) 构造图 DestroyGraph(&G): // 销毁图
LocateVex(G, u); // 若G中存在顶点u，则返回该顶点在 图中“位置” ；否则返回其它信息。 GetVex(G, v); // 返回 v 的值。 PutVex(&G, v, value); // 对 v 赋值value。

20 基本操作 FirstAdjVex(G, v); // 返回 v 的“第一个邻接点” 。若该顶点 //在 G 中没有邻接点，则返回“空”。
NextAdjVex(G, v, w); // 返回 v 的（相对于 w 的） “下一个邻接 点”。若 w 是 v 的最后一个邻接点，则返回“空”。

21 基本操作 InsertVex(&G, v); //在图G中增添新顶点v。 DeleteVex(&G, v);
InsertArc(&G, v, w); // 在G中增添弧<v,w>，若G是无向的， //则还增添对称弧<w,v>。 DeleteArc(&G, v, w); //在G中删除弧<v,w>，若G是无向的， //则还删除对称弧<w,v>。

22 DFSTraverse(G, v, Visit())
//从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit()) //从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。

23 7.2 图的存储结构 图的四种常用的存储形式： 邻接矩阵和加权邻接矩阵（labeled adjacency matrix） 邻接表 十字链表
7.2 图的存储结构 图的四种常用的存储形式： 邻接矩阵和加权邻接矩阵（labeled adjacency matrix） 邻接表 十字链表 邻接多重表

24 一、(加权)邻接矩阵（labeled adjacency matrix）
设图 G= <V, E>是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 G.arcs[n][n]，定义：

25 无向图G1 有向图G2

26 无向图 一、(加权)邻接矩阵（continue） 从邻接矩阵中可以反映图的许多特征: (1) 对称矩阵(可采用压缩存储);
(2) 每一行(或列)1的个数是该顶点的度; (3) 主对角线全为0(简单图);

27 有向图 一、(加权)邻接矩阵（continue） (1) 每一行1的个数是该顶点的出度; (2) 每一列1的个数是该顶点的入度;
(3) 主对角线全为0(简单图); 有向图的邻接矩阵不一定对称。

28 网络的邻接矩阵 一、(加权)邻接矩阵（continue） 以有向网为例： N.Edge = G.arcs[ i ][ j ]=
Wij <vi, vj> 或（vi, vj）∈VR ∞ 无边（弧） 定义为： 以有向网为例： 顶点表： 5 v1 v2 v3 v4 v5 v6 4 8 9 7 6 1 3 N ( v1 v2 v3 v4 v5 v6 ) 邻接矩阵： ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9 ∞ ∞ ∞ ∞ 6 ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ ∞ ∞ N.Edge =

29 一、(加权)邻接矩阵（continue）
容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。 邻接矩阵法优点： 邻接矩阵法缺点：

30 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20
用邻接矩阵表示的图的存储表示(P161) #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef enum{DG, DN,UDG,UDN} GraghKind; typedef struct ArcCell { // 弧的定义 VRType adj; // VRType是顶点关系类型。 // 对无权图，用1或0表示相邻否； // 对带权图，则为权值类型。 InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

31 用邻接矩阵表示的图的存储表示(continue)
typedef struct { // 图的定义 VertexType vexs[MAX_VERTEX_NUM];// 顶点信息 AdjMatrix arcs; // 弧的信息 int vexnum, arcnum; // 顶点数，弧数 GraphKind kind; // 图的种类标志 } MGraph;

32 例：用邻接矩阵生成无向网的算法（参见教材P162）
Status CreateUDN(Mgraph &G){//用邻接矩阵表示 return OK; } for(k=0;k<G.arcnum;++k){ //给弧赋初值(循环次数＝弧数) scanf(&v1, &v2, &w); i=LocateVex(G,v1); j=LocateVex(G,v2); //找到两顶点在矩阵中的位置(n次) G.arcs[i][j].adj=w; //输入对应权值 If(IncInfo) Input(*G.arcs[i][j].info); G.arcs[j][i] = G.arcs [i] [j]； //无向网是对称矩阵 } scanf(&G.vexnum, &G.arcnum, &IncInfo); //输入总顶点数，总弧数和信息 for(i=0;i<G.vexnum,;++i) scanf(&G.vexs[i] );//输入顶点值，存入一维向量中 for(i=0; i<G.vexnum; ++i) //对邻接矩阵n*n个单元初始化，adj=∞,info=NULL for(j=0;j<G.vexnum;++j) G.arcs[i][j]={INFINITY, NULL}; 对于n个顶点e条弧的网， 建网时间效率 = O(n2+n+e*n)

33 图的部分操作在邻接矩阵上的实现 int firstAdjVex(Mgraph G, int v) { //返回顶点v的第一个邻接点，G为无向图 for (k=0;k<G.vexnum; k++) if (G.adj [v][k]>0 ) break; if (k>=G.vexnum) k= -1; // 无邻接点 return k; }// end firstAdjVex( )

34 二、 邻接表 (Adjacency List)
无向图的邻接表 为每个顶点建立一个单链表,第i个单链表中的结点表示与顶点vi相邻的顶点 v1 v2 v3 v5 v4 1 2 3 4 v1 v2 v3 v4 v5 ^ 1 3 4 2 ^ 3 4 ^ 1 4 2 ^ 2 3 ^ 1 注：邻接表不唯一，因各个边结点的链入顺序是任意的。

35 二、 邻接表 (Adjacency List)
头结点: data firstarc data: 结点的数据域，保存结点的数据值。 firstarc: 结点的指针域，给出自该结点出发的的第一条边 的边结点的地址。 表结点: adjvex nextarc adjvex: 该边或弧所指向的顶点的位置. nextarc: 指向下一条边或弧的指针. data firstarc adjvex nextarc

36 二、 邻接表 (Adjacency List)
v1 v2 v3 v5 v4 1 2 3 4 v1 v2 v3 v4 v5 ^ 1 3 4 2 ^ 3 4 ^ 1 4 2 ^ 2 3 ^ 1 在无向图的邻接表中,如何求每个顶点的度？ 第 i 个链表中的结点个数是顶点 i 的度 若顶点数为n,边数为e时,则在无向图中共需多少 个结点？ n个头结点,2e个表结点

37 在有向图的邻接表中，第 i 个单链表链接的边都是顶点 i 发出的边。也叫做出边表。
有向图的邻接表和逆邻接表 在有向图的邻接表中，第 i 个单链表链接的边都是顶点 i 发出的边。也叫做出边表。 在有向图的逆邻接表中，第 i 个单链表链接的边都是进入顶点 i 的边。也叫做入边表。 邻接表(出边) 逆邻接表(入边) v1 v2 v3 v4 V4 V3 ^ V2 V1 2 3 1 1 2 3 V4 V3 V2 V1 ^ 3 2 1 2 3 用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。

38 网络 (带权图) 的邻接表 带权图的边结点中保存该边上的权值 cost

39 邻接表表示的图的存储结构（P163） //边结点定义 typedef struct ArcNode { int adjvex;
// 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 该弧相关信息的指针 } ArcNode; adjvex info nextarc

40 邻接表表示的图的存储结构（P163） //头结点定义 typedef struct VNode {
VertexType data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧 } VNode, AdjList[MAX_VERTEX_NUM]; data firstArc

41 邻接表表示的图的存储结构（P163） //图的定义 typedef struct { AdjList vertices; int vexnum, arcnum; int kind; // 图的种类标志 } ALGraph;

42 图的操作在邻接连表的上的实现 int firstAdjVex(ALGraph ghead ,int v) {
return ghead[v]->firstArc.adjvex; }// end firstAdjVex( ) int nextAdjVex(ALGraph ghead,int v, int w) { p=ghead[v]->firstArc; while (p&&p->adjvex!=w) p=p->next; if (!p) return 0; else return p->next->adjvex; }// end nextAdjVex( ) 找某顶点的所有邻接点的时间复杂度是O(e)

43 如何建立邻接表（以有向图为例） 算法思想： 首先将邻接表表头数组初始化，vertex域初始化为i，firstarc初始化为NULL；
然后对读入的每一条弧<i,j>，产生一个表结点，adjver域置为j，并将结点链接到邻接表的第i个链表中。

44 算法如下： Void GreatAdjList(ALGraph &G) { ArcNode *p;
sacnf(“%d%d”,&n,&e); G.vexnum=n; G.arcnum=e; for(i=0; i<n; i++) { G.vertices[i].vertex=i; G.vertices[i].firstarc=NULL;} for(k=0; k<e; k++){ scanf(i,j); p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p;} }// GreatAdjList

45 讨论：邻接表与邻接矩阵的比较 1. 联系：都可以用来存储有向图和无向图；邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。 2. 区别： ①邻接矩阵是顺序结构，邻接表是链式结构 ②对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。 邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<<n2)

46 三、 邻接多重表 (无向图的一种存储结构) 在无向图的邻接表中,一条边出现两个单链表中.浪费空间，也给某种操作带来了困难。
在邻接多重表中，每一条边只有一个结点(称边结点)为有关边的处理提供了方便。

47 ivex和jvex是依附于该边的两顶点位置。 ilink域指向下一条依附于顶点ivex的边； jlink指向下一条依附于顶点jvex的边。
三、 邻接多重表 (无向图的一种存储结构) 边结点的结构 Ebox: mark ivex jvex ilink jlink 其中: mark 是记录是否处理过的标记； ivex和jvex是依附于该边的两顶点位置。 ilink域指向下一条依附于顶点ivex的边； jlink指向下一条依附于顶点jvex的边。 需要时还可设置一个存放与该边相关的权值的域 cost。

48 三、 邻接多重表 (无向图的一种存储结构) 其中: VexBox: data Firstarc 顶点结点的结构:
存储顶点信息的结点表以顺序表方式组织.在邻 接多重表中,所有依附于同一个顶点的边都链接 在同一个单链表中。从顶点 i 出发, 可以循链找到 所有依附于该顶点的边，也可以找到它的所有邻 接顶点。 VexBox: data Firstarc

49 三、 邻接多重表 (无向图的一种存储结构) 例 a e c b d 1 2 3 a c d b 4 e 0 1 0 3 2 3 2 1
1 2 3 a c d b 4 e ^ ^ ^ ^ ^

50 四、十字链表(有向图的一种存储结构) 可以把十字链表看成是将有向图的邻接表和逆 邻接表这两个表结合起来而得到的一种链表。
在十字链表中,有向图中每一条弧对应一个结点(称弧结点) 每一个顶点也对应一个结点(称顶点结点)。

51 四、十字链表(有向图的一种存储结构) 边结点的结构 ArcBox: tailvex headvex hlink tlink 其中:
需要时还可有权值域cost

52 四、十字链表(有向图的一种存储结构) 顶点结点的结构 其中: 数据域data存放与该顶点相关的信息，
VexNode: data Firstin Firstout 其中: 数据域data存放与该顶点相关的信息， 指针域Firstin指向以该顶点为弧头的第一条弧； 指针域Firstout指向以该顶点为弧尾的第一条弧。

53 四、十字链表(有向图的一种存储结构) 例 b d a c a b c d 1 2 3 0 2 0 1 2 3 2 0 3 2 3 1 3 0
1 2 3 0 2 0 1 2 3 2 0 3 2 3 1 3 0 ^ ^ ^ ^ ^ ^ ^ ^

54 #define MAX_VERTEX_NUM 20
Typedef 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; //图结构

55 7.3 图的遍历 图的两种遍历方法 深度优先遍历 广度优先遍历
7.3 图的遍历 从已给的连通图中某一顶点出发，沿着一些边访问图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph Traversal )。 图的两种遍历方法 深度优先遍历 广度优先遍历

56 7.3 图的遍历 图中可能存在回路，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点
7.3 图的遍历 图中可能存在回路，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited [i] 为 1，防止它被多次访问。

57 深度优先搜索DFS ( Depth First Search )
从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至V0 的所有邻接点都被访问到。 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

58 深度优先搜索DFS ( Depth First Search )
深度优先搜索的示例 深度优先遍历生成树

59 图的深度优先遍历算法 void dfsTraverse( ){
for (v=1; v<=n; v++) visited[v]=false; for (v=1; v<=n; v++) if (!visited[v]) dfs(v); } void dfs(int v){ visited[v]=1; for (w=firstAdjVex(v); w; w=nextAdjVex(v,w)) if (!visited[w]) dfs(w); }// 使用ADT 在递归函数中增加一计数器sum，初值为n，每访问一次就减1,减到0则return，可避免递归时间过长。

60 图的深度优先遍历算法 在邻接矩阵A上实现 void dfs(int v){ visited[v]=true;
for (w=1; w<=n; w++) if (A[v][w]>0) if (!visited[w]) dfs(w); }//

61 图的深度优先遍历算法 同学们自己考虑非递归实现算法 在邻接链表上实现 void dfs(int v){ visited[v]=true;
p=ghead[v]->firstArc; while (p) {w=p->adjvex; if (!visited[w]) dfs(w); p=p->next; } 同学们自己考虑非递归实现算法

62 Dfs1(Graph g, int v){//利用栈实现非递归算法 Visit(v); visit[v]=1;push(s,v);
//第一个顶点入栈并访问 Visit(v); visit[v]=1;push(s,v); //当栈不空时做 Whlie(!EmptyStack(s)){ p=ghead[v]->firstArc; //找到栈顶的一个未被访问的邻接点，入栈并访问 while (p) {w=p->adjvex; if (!visited[w]) {push(s,w);visit(w); p=ghead[w]->firstArc;} else p=p->next; }//while //如果所有邻接点都被访问，出栈 pop(s,v); }

63 V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1 V3  V7  V6  V2  V5  V8  V4 1 2 3 4 vexdata firstarc 7 8 ^ adjvex next 5 6

64 V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1 V3  V7  V6  V2  V4  V8  V5 1 2 3 4 vexdata firstarc 7 8 ^ adjvex next 5 6

65 DFS 算法效率分析: 设图中有 n 个顶点，e 条边，遍历时对图中每个顶点至多调用一次DSF函数，遍历图的过程就是对每个顶点查找其邻接点的过程，消耗的时间取决于所采用的存储结构 如果用邻接矩阵来表示图，查找每个顶点的邻接点所需的时间为O(n2)。 如果用邻接表来表示图，查找每个顶点的邻接点所需的时间为O(e),加上访问 n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。

66 二、广度优先搜索BFS ( Breadth First Search )
从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

67 二、广度优先搜索BFS 树的按层次进行访问的次序： A、B、C、D、E、F、G、H、 I、J、K、L 适用的数据结构：队列 A C D B

68 广度优先搜索BFS 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。 除了辅助数组 visited [ ]之外，为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问

69 Void BFSTraverse( Gragh G, int v) {
for (v=0; v<G.vexnum; v++) visited[v]=0; //清访问标记 InitQueue(Q); //清队列Q; for (v=0; v<G.vexnum; v++) //对每一个顶点v if (!visited[v]) { visited[v]=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 (!visited[w]) {visited[w]=1; visit(w); EnQueue(w); //将u的每个未被访问的邻接点w 入队 }//if }//while }

70 例 a d b c e 1 2 3 4 a c d b vexdata firstarc 5 ^ adjvex next e a f r 遍历序列：a d f r 遍历序列：a d d c f r 遍历序列：a d c

71 例 a d b c e 1 2 3 4 a c d b vexdata firstarc 5 ^ adjvex next e d c b f r 遍历序列：a d c b c b f r 遍历序列：a d c b c b e f r 遍历序列：a d c b e

72 例 a d b c e 1 2 3 4 a c d b vexdata firstarc 5 ^ adjvex next e 2 5 f r 遍历序列：adcbe 5 f r 遍历序列：adcbe f r 遍历序列：a d c b e

73 广度优先搜索BFS 算法分析: 如果使用邻接表表示图，则循环的总时间代价为 d0+ d1 + … + dn-1 = O(e)，其中的 di 是顶点 i 的度 如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。 DFS与BFS之比较： 空间复杂度相同，都是O(n)(借用了堆栈或队列）； 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。

74 三、遍历应用举例 1. 求一条从顶点 i 到顶点 s 的简单路径 2. 求两个顶点之间的一条路径长度最短的路径

75 应用1. 求一条从顶点 i 到顶点 s 的简单路径 求从顶点 b 到顶点 k 的一条简单路径。 例如: g b 从顶点 b 出发进行深度优先搜索遍历 a 假设找到的第一个邻接点是c,则得到的结点访问序列为: b c h d a e k f g c d e f h k 假设找到的第一个邻接点是a,且得到的结点访问序列为: b a d h c e k f g

76 void DFSearch( int v, int s, char *PATH) {
// 从第v个顶点出发递归地深度优先遍历图G， // 求得一条从v到s的简单路径，并记录在PATH中 visited[v] = TRUE; // 访问第 v 个顶点 for (w=FirstAdjVex(v); w!= ; w=NextAdjVex(v)) if (!visited[w]) 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

77 应用2. 求两个顶点之间的一条路径长度最短的路径
若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?

78 g f b a c e d k h 深度优先搜索访问顶点的次序取决于图的存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。
求路径长度最短的路径可以基于广度优先搜索遍历进行，但需要修改队列的结点结构及其入队列和出队列的算法。

79 3 2 例如:求下图中顶点 3 至顶点 5 的一条最短路径。 1 4 7 队列用双向链表的表示: 5 6 8 9 Q.front Q.rear

80 7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 对无向连通图进行遍历得到的将是一个极小连通子图，即图的生成树！
7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 对无向连通图进行遍历得到的将是一个极小连通子图，即图的生成树！ 由深度优先搜索得到的生成树，称为深度优先搜索生成树。 由广度优先搜索得到的生成树，称为广度优先搜索生成树。 对非连通图进行遍历，得到的将是各连通分量的生成树，即图的生成森林！

81 例1 ：画出下图的生成树 v0 v1 v2 v4 v3 邻接表 无向连通图 v0 v0 DFS生成树 BFS生成树 v3 v1 v3 v4
1 2 3 4 ^ 1 3 4 2 v4 v3 v2 v1 v0 邻接表 无向连通图 v0 v0 DFS生成树 BFS生成树 v3 v1 v3 v4 v2 v4 v2 v1

82 例2：画出下图的生成森林（或极小连通子图）
D E A B C F J L M G H I K 求解步骤： Step1:先求出邻接矩阵或邻接表； Step2:写出DFS或BFS结果序列； Step3:画出对应子图或生成森林。 我们选用邻接表方式来求深度优先搜索生成森林

83 先写出邻接表（或邻接矩阵）： 极小连通！ A B C F J L M 子图1： 子图2： D E G H I K 子图3：
再写出DFS结果（3次）ABMJLCF DE GHKI 11 5 M 12 L K 10 J 9 I 8 H 7 G 6 F E 4 D 3 C 2 B 1 A ^ 极小连通！ A B C F J L M 子图1： 子图2： D E G H I K 子图3：

84 子图 (或连通分量) A B C F J L M G H I K D E A B C F J L M G H I K D E 生成森林

85 求连通分量的算法（生成森林用对应的二叉树存储）
Void DFSForest( BiTree &T) { T=NULL; for (v=0; v<n; v++) visited[v]=0; for (v=0; v<n; v++) if (!visited[v]) { p=(CSTree) malloc(sizeof(CSNode)); //生成树的根 *p={GetVex(G,v),NULL,NULL} if (! T) T=p; // 森林空，p是第一棵树 else q->nextsibling=p; q=p; //q 当前森林中最后一棵树的根 DFSTree(G,v,p); // 深度优先遍历，并建立树； }//if }//

86 Void DFSTree(Graph G, int v, CSTree &T) {
visited[v]=1; first=true; for (w=firstAdjVex(v); w; w=nextAdjVex(v,w)) if (!visited[w]) { p=(CSTree) malloc(sizeof(CSNode)); //生成树的根 *p={GetVex(G,v),NULL,NULL}; if (first) { T->lchild=p; first=false;} else q->nextsibling=p;} q=p; DFSTree(G,w,q); }// if }// DFSTree()

87 7.4.2有向图的强连通分量 算法思想： 使用dfs算法思想。设一编号数组finished[ ]
1. 对图G的邻接链表进行dfs遍历，并按退出递归的次序给顶点编号。（1，2，3，….） 2.对图G的逆邻接链表进行dfs遍历，每次调用dfs的出发点是编号最大的未被访问的顶点(上次最后完成搜索的顶点） 1 3 2 4 5 例 1 2 3 4 5 Finished 得到的顶点集： 1, 3，2 4，5 图G

88 7.4.3 最小生成树 MST( Minimum cost Spanning Tree )
使用不同的遍历图的方法，可以得到不同的生成树； 从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。 MST:在网络的多个生成树中，寻找一个各边权值之和最小的生成树。 构造最小生成树的准则 必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用n-1条边来联结网络中的n个顶点； 不能使用产生回路的边。

89 假设在n个城市之间要建立通信网络线，要求使得这个城市之间连通且费用最少。
MST典型用途： 假设在n个城市之间要建立通信网络线，要求使得这个城市之间连通且费用最少。 数学模型： 顶点———表示城市，有n个； 边————表示线路，有n–1条； 边的权值—表示线路的经济代价； 连通网——表示n个城市间通信网。 问题抽象： n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST

90 7.4.3 最小生成树 MST 求一个带权连通图中的最小生成树的方法: Prim算法 Kruskal算法 都是利用MST的性质构造
最小生成树的算法

91 若U集是V的一个非空子集，若(u0, v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0, v0)必在某一最小生成树上。
最小生成树的 MST 性质： 若U集是V的一个非空子集，若(u0, v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0, v0)必在某一最小生成树上。 V-U U

92 最小生成树的 MST 性质： U u u’ V-U v v’ 证明（反证法） 设G的任何MST都不包含（u,v）。设T是G的一个MST，将（u,v）加入T，形成回路。去掉（u’,v’）得到T’ , 因 wuv<wu’v’，所以T’ 的边权之和小于T 的边权之和，与T是MST矛盾。

93 1、普里姆(Prim)算法 普里姆算法的基本思想（是一种贪婪算法）
设连通网络图G = <V, E ,W>,TE是G上最小生成树中边的集合. 1. TE= ，U={u0 }; 2. 在U和V-U之间选最小边（u,v），将v加入U，将(u,v)加入TE中; 3. 重复2直到U=V(或n-1次)

94 普里姆(Prim)算法过程示例 28 1 2 10 14 16 7 6 3 18 25 12 25 5 4 22

95 普里姆(Prim)算法过程示例 28 1 2 10 14 16 7 6 3 18 25 12 25 5 4 22

96 普里姆(Prim)算法过程示例 28 1 2 10 14 16 7 6 3 18 25 12 25 5 4 22

97 普里姆(Prim)算法过程示例 28 1 2 10 14 16 7 6 3 18 25 12 25 5 4 22

98 普里姆(Prim)算法过程示例 28 1 2 10 14 16 7 6 3 18 25 12 25 5 4 22

99 普里姆(Prim)算法过程示例 28 1 2 10 14 16 7 6 3 18 25 12 25 5 4 22

100 普里姆(Prim)算法过程示例 28 1 2 10 14 16 7 6 3 18 25 12 25 5 4 22

101 Prime算法的实现 设置一个辅助数组closedge[ ] ，对每个顶点viV－U,存在分量closedge[i-1],有两个域，
Lowcost=Min{cost(u,vi)|u  U} adjvex: 存储与该边关联的U中顶点 辅助数组closedge说明如下: Struct { VertexType adjvex; VRType lowcost; }closedge[MAX_VERTEX_NUM];

102 细化的普里姆(Prim)算法: TE={ }; closedge[v].adjvex=v1;
closedge[v].lowcost=adj.matrix[1][v]; 2. U[1]=1; U[2…n]=0; 3. 选U[k]=0 的closedge[k].lowcost最小的k； 4. U[k]=1, u= closedge[k].adjvex, (u,k) 加入TE中 5. 修改所有不属于U的k的邻接点w的lowcost 值，规则是： 如果closedge[w].lowcost> adj.matrix[k][w] 则：closedge[w].lowcost= adj.matrix[k][w]

103 28 1 2 10 14 16 7 6 3 18 25 12 25 5 4 22

104 Adjvex v1 v1 v1 v1 v1 v1 {1} {2,3,4, 6 Lowcost 28 10 5,6,7}
Closedge I U V-U k Adjvex v v1 v1 v1 v1 v {1} {2,3,4, Lowcost ,6,7} Adjvex v1 v1 v1 v6 v1 v1 {1,6} {2,3,4,5, 5 Lowcost } Adjvex v1 v v5 v6 v1 v5 {1,6,5} {2,3,4,7} 4 Lowcost Adjvex v v4 v5 v6 v1 v4 {1,6,5,4} {2,3,7} 3 Lowcost Adjvex v v v5 v6 v1 v4 {1,6,5,4, {2,7} Lowcost } Adjvex v v v5 v6 v1 v2 {1,6,5,4, {7} Lowcost ,2}

105 void MiniSpanTree_PRIM(Mgtaph G,VertexType int u){
k=LocateVer(G,u); //k为顶点u的序号 for (v=0; v<G.vexnum; v++) if(v!=k) closedge[v]={u, G.arcs[k][j].adj}; closedge[k].lowcost=0;//第k个顶点加入在U集合中 for (i=1; i< G.vexnum; i++) { k=minimum(closedge); //lowcost最小的顶点序号为k u=closedge[k].adjvex; prinf(u,G.vexs[k] ); closedge[k].lowcost=0;//第k个顶点并入U集 for (j=0; j<G.vexnum; j++) if (G.arcs[k][j].adj<closedge[j].lowcost) closedge[j]={G.vexs[k],G.arcs[k][j].adj} }// for } // MinISpan_Tree_PRIM

106 Prime算法分析 设连通网络有 n 个顶点 ，则该算法的时间复杂度为O(n2)。 它适用于边稠密的网络。

107 2、Kruscal 算法 算法思想: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。

108 算法描述: 构造非连通图 ST=( V,{ } ); k = i = 0; // k 计选中的边数,i计检查的边数
while (k<n-1) { ++i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路， 则 输出边(u,v); 且 k++; }

109 √ √ √ × × √ √ √

110 7.4.4 关节点和重连通分量 (Biconnected Component)
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。 如何判别给定的连通图是否是双连通图？ 若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点(割点)。 没有关节点的连通图为重（双）连通图。

111 7.4.4 关节点和重连通分量 (Biconnected Component)
在一个无向连通图G中, 重连通分量可以利用深度优先生成树找到。 关节点的两个特性： 1.深度优先生成树的根是关节点的充要条件是它至少有两个子女。 2.其它顶点 u 是关节点的充要条件是它至少有一个子女 w, 以 w为根的子树与u 的任一祖先之间无回边。

112 例如:下列连通图中， 深度优先生成树 a b c d e f g h a h g c b f d e 顶点 a 和顶点 c 是关节点

113 1 a b c d e f g h 2 3 4 5 6 7 8

114 1) 设V0为深度优先遍历的出发点 p = G.vertices[0].firstarc; v = p->adjvex; DFSArticul(G, v); // 从第v顶点出发深度优先搜索 if (count < G.vexnum) { // 生成树的根有至少两棵子树 printf (0, G.vertices[0].data); // 根是关节点

115 2) 定义函数: low(v) = Min{visited[v], low[w], visited[k] } 其中: 顶点w 是生成树上顶点v 的孩子; 顶点k 是生成树上和顶点v有回边相联接的祖先; visited记录深度优先遍历时的访问次序 若对顶点v，在生成树上存在一个子树根w, 且 low[w] ≥ visited[v] 则顶点v为关节点。

116 对深度优先遍历算法作如下修改： visited[v]的值改为遍历过程中顶点的访问次序count 值; 2. 遍历过程中求得 low[v]=Min{visited[v],low[w],visited[k]} 3. 从子树遍历返回时， 判别low[w]≥visited[v]?

117 min =visited[v0] = ++count;
void DFSArticul(ALGraph G, int v0) { // 从第v0个顶点出发深度优先遍历图 G, // 查找并输出关节点 } // DFSArticul min =visited[v0] = ++count; // v0是第count个访问的顶点, 并设low[v0]的初值为min for(p=G.vertices[v0].firstarc; p; p=p->nextarc) { } // 检查v0的每个邻接点 low[v0] = min;

118 w = p->adjvex; // w为v0的邻接顶点
if (visited[w] == 0) { // w未曾被访问 DFSArticul(G, w); // 返回前求得low[w] } else // w是回边上的顶点 if (low[w] < min) min = low[w]; if (low[w]>=visited[v0]) printf(v0, G.vertices[v0].data); //输出关节点 if (visited[w] < min) min = visited[w];

119 算法 Biconnected 的时间代价是 O(n+e)。其中 n 是该连通图的顶点数，e 是该连通图的边数
此算法的前提条件是连通图中至少有两个顶点,因为正好有一个顶点的图连一条边也没有。

120 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径

121 7.5.1 拓扑排序 一、概念 无环的有向图 1、有向无环图 DAG (Directed Acyclic Graph)
2、 AOV (Activity On Vertices)网络：用顶点表示活动，用有向弧<Vi, Vj>表示活动间的优先关系。Vi 必须先于活动Vj 进行。这种有向图称为用顶点表示活动的网络。 若<vi,vj>是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继 AOV网中不允许有回路，这意味着某项活动不能以自己为先决条件

122 7.5 有向无环图及其应用 计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。 例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。

123 例 课程代号 课程名称 先修棵 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 无 C1,C2 C3,C4 C3.C5 C3,C6 C1,C9,C10 程序设计基础 离散数学 数据结构 汇编语言 语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12

124 二、拓扑排序 1、在AOV中 拓扑有序序列：将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。 拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。 检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环

125 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列：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网的拓扑序列不是唯一的

126 对于有向图 B A D C 不能求得它的拓扑有序序列。 因为图中存在一个回路 {B, C, D}

127 2、拓扑排序算法思想 输入AOV网络。有 n个顶点。 1 在AOV网络中选一个没有直接前驱的顶点，并输出之
2 从图中删去该顶点, 同时删去所有它发出的有向边 3 重复以上 1、2 步, 直到 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或 图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环

128 a b h c d g f e 在算法中需要用定量的描述替代定性的概念 c a d g e b f h 没有前驱的顶点  入度为零的顶点
删除顶点及以它为尾的弧  弧头顶点的入度减1

129 3、AOV网络的存储方式--邻接表表示 ind data firstarc adjvex next 1 2 3 4 5 1 3 C0 C1
1 2 3 4 5 1 3 C0 C1 C2 C3 0 C4 C5 0 1 3 0 5 1 5 0 1 5 0 C0 C1 C2 C3 C4 C5

130 AOV网络的存储方式--邻接表表示 邻接表结点： typedef struct node { int adjvex; //顶点域
struct node *next; //链域 }JD; 表头结点： typedef struct tnode { int ind; //入度域 struct node *link; //链域 }TD; TD g[M];

131 4、拓扑排序算法实现 以邻接表作存储结构 把邻接表中所有入度为0的顶点进栈
栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕

132 例 1 2 3 4 5 6 1 2 in link 5 4 3 ^ vex next 6 3 2 1 4 top 6

133 1 2 in link 5 4 3 ^ vex next 6 3 2 1 4 6 top top 输出序列：6

134 1 2 in link 5 4 3 ^ vex next 6 输出序列：6 top p

135 1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 输出序列：6

136 1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 输出序列：6

137 1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 输出序列：6

138 1 2 in link 5 4 3 ^ vex next 6 p=NULL 3 2 1 4 top 输出序列：6

139 1 2 in link 5 4 3 ^ vex next 6 3 2 1 4 top top 输出序列：6 1

140 1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 输出序列：6 1

141 1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 4 输出序列：6 1

142 1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 4 输出序列：6 1

143 1 2 in link 5 4 3 ^ vex next 6 p 3 2 1 4 top 4 输出序列：6 1

144 2 in link 5 4 3 ^ vex next 1 6 p 3 2 1 4 top 3 4 输出序列：6 1

145 2 in link 5 4 3 ^ vex next 1 6 p 3 2 1 4 top 3 4 输出序列：6 1

146 2 in link 5 4 3 ^ vex next 1 6 p 3 2 1 4 top 3 4 输出序列：6 1

147 1 in link 5 4 3 ^ vex next 2 6 p 3 2 1 4 top 3 4 输出序列：6 1

148 1 in link 5 4 3 ^ vex next 2 6 p=NULL 3 2 1 4 top 3 4 输出序列：6 1

149 1 in link 5 4 3 ^ vex next 2 6 3 2 1 4 top 3 4 输出序列：

150 1 in link 5 4 3 ^ vex next 2 6 p 3 2 1 4 top 4 输出序列：

151 1 in link 5 4 3 ^ vex next 2 6 p 3 2 1 4 top 4 输出序列：

152 1 in link 5 4 3 ^ vex next 2 6 p 3 2 1 4 top 4 输出序列：

153 in link 5 4 3 ^ vex next 1 2 6 p 3 2 1 4 top 2 4 输出序列：

154 in link 5 4 3 ^ vex next 1 2 6 p 3 2 1 4 top 2 4 输出序列：

155 in link 5 4 3 ^ vex next 1 2 6 p=NULL 3 2 1 4 top 2 4 输出序列：

156 in link 5 4 3 ^ vex next 1 2 6 p=NULL 3 2 1 4 top 2 4 输出序列：

157 in link 5 4 3 ^ vex next 1 2 6 p=NULL 3 2 1 4 top 4 输出序列：

158 in link 5 4 3 ^ vex next 1 2 6 3 2 1 4 top 4 输出序列：

159 in link 5 4 3 ^ vex next 1 2 6 p 3 2 1 4 top 输出序列：

160 in link 5 4 3 ^ vex next 2 1 6 p 3 2 1 4 top 5 输出序列：

161 in link 5 4 3 ^ vex next 2 1 6 p=NULL 3 2 1 4 top 5 输出序列：

162 in link 5 4 3 ^ vex next 2 1 6 3 2 1 4 top 5 输出序列：

163 in link 5 4 3 ^ vex next 2 1 6 p=NULL 3 2 1 4 top 输出序列：

164 5、拓扑排序的算法 int TopologicalSort ( ) { int top = -1; //入度为零的顶点栈初始化 for ( int i = 0; i < n; i++ ) //入度为零顶点进栈 if ( ind[i] == 0 ) { ind[i] = top; top = i; } for ( i = 0; i < n; i++ ) //期望输出n个顶点 if ( top == -1 ){ //中途栈空,转出 cout << “网络中有回路(有向环)" << endl; return 0; } else { //继续拓扑排序 int j = top; top = ind[top]; //退栈

165 cout << j << endl; //输出
p = ghead[j].firstarc; while ( p ) { //扫描该顶点的出边表 int k = p.adjvex; //另一顶点 if ( --ind[k] == 0 ) //该顶点入度减一 { ind[k] = top; top = k; } //减至零 p = p.next; } //while } // for return 1; } // TopologicalSort

166 6、拓扑排序算法分析: 建邻接表：T(n)=O(e) 搜索入度为0的顶点的时间：T(n)=O(n) 拓扑排序：T(n)=O(n+e)

167 关键路径 1.问题提出 假设以有向网表示一个施工流图，用顶点表示事件，弧表示活动；弧上的权值表示完成该项子工程所需时间。每个事件表示在它之前的活动已完成，在它之后的活动可以开始.

168 关键路径(Critical Path) 例 设一个工程有11项活动，9个事件 事件 V1——表示整个工程开始 事件V9——表示整个工程结束
例 设一个工程有11项活动，9个事件 事件 V1——表示整个工程开始 事件V9——表示整个工程结束 问题：（1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？ 9 8 7 6 4 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4

169 2.定义 AOE (Activity On Edges) 网络: 如果在带权DAG图中 用有向边表示一个工程中的活动(Activity)
用边上权值表示活动持续时间(Duration) 用顶点表示事件 (Event) 则这样的有向图叫做用边表示活动的网络，简称 AOE (Activity On Edges) 网络。

170 关键路径(Critical Path) AOV中有关概念 路径长度—路径上各活动持续时间之和 关键路径—路径长度最长的路径
Ve(j)—表示事件Vj的最早发生时间 Vl(j)—表示事件Vj的最迟发生时间 e(i)—表示活动ai的最早开始时间 l(i)—表示活动ai的最迟开始时间 l(i)-e(i)—表示完成活动ai的时间余量 关键活动—关键路径上的活动，即l(i)=e(i)的活动

171 3.如何找e(i)=l(i)的关键活动？ 设活动ai用弧<j,k>表示，其持续时间记为：dut(<j,k>)
则有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(<j,k>) j k ai 如何求Ve(j)和Vl(j)？

172 关键路径(Critical Path) 事件发生时间的计算公式: ve(源点) = 0;
如何求Ve(j)和Vl(j)？ 事件发生时间的计算公式: ve(源点) = 0; ve(k) = Max{ve(j) + dut(<j, k>)} vl(汇点) = ve(汇点); vl(j) = Min{vl(k) – dut(<j, k>)}

173 关键路径(Critical Path) 4.求关键路径步骤 （1）求Ve(i) （2）求Vl(j) （3）求e(i) （4）求l(i)
（5）计算l(i)-e(i)

174 例 9 8 7 6 4 5 3 2 1 a2=4 a3=5 a5=1 a6=2 a9=4 a1=6 a4=1 a7=9 a8=7 a10=2
活动 e l l-e a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11  2 顶点 Ve Vl 3 6 4 5 7 16 14 18 6 8 7 10 16 14 18 V1 V2 V3 V4 V5 V6 V7 V8 V9 6 4 6 2 5 8 3 7 7 7 10 3 16 14

175 关键路径(Critical Path) 5.算法思想 （1）建立AOE网；
（2）从源点v0出发，令ve[0]=0，边进行拓扑排序，边计算其余各顶点的ve[i]。若图中有回路则结束 （3）从汇点vn-1出发, vl[n-1]=el[n-1],按逆拓扑有序的顺序求vl[i], i=n-2, …, 0。 （4）根据各点的ve和vl值，求每条弧的最早开始时间e(s)和最迟开始时间 l(s)。若某弧满足条件 e(s)= l(s)，则是关键活动。

176 关键路径(Critical Path) 6.求关键路径算法： 在此算法中需要对邻接表中单链表的结点加以修改, 在各结点中增加一个int域 info, 记录该边的权值。

177 拓扑排序算法（计算ve[]）： status topLogicalSort(ALGraph G,Stack &t){ FindInDegree(G,indegree); for (k=0; k<n; k++) //找一入度为0的顶点入栈,。 if (ind[k]==0) push(S,k); Init Stack(T); count=0; ve[0..n-1]=0; while (!s.empty()) { pop(S,j); push(T,j); count++; for (p=G.vertices[j].firstarc; p; p=p->nextarc) { k=p->adjvex; if (--indegree[k]==0) push(S,k); // 入度为0则入栈； if (ve[j]+*(p->info>ve[k]) ve[k]= ve[j]+*(p->info); } // for } //while if (count<G.vexnum) return error; //有回路 else return OK; }// topLogicalSort

178 求关键活动算法： void criticalPath (ALGraph G) { if (!topLogicalSort(G,T)) return ERROR; vl[0..G.vexnum-1]=ve[G.vexnum-1]; while (!StackEmpty(T)) { //按逆拓扑序求vl[] pop(T,j); for (p=G.vertices[j].firstarc; p; p=p.next ) { k=p->adjvex; dut=*(p->info); if (vl[j]-dut<vl[j]) vl[j]= vl[j]-dut; } //for p } // while

179 // 求ee,el和关键活动 for (j=0; j<G.vexnum; j++) for (p=G.vertics[j].firstarc; p; p=p.next ) { k=p->adjvex; dut=*(p->info); ee=ve[j]; el=vl[k]-dut; if (ee==el) tag=‘*’; else tag=‘’; printf(j,k,dut,ee,el,tag); } // for p } // criticalPath

180 7.分析时间复杂度 在拓扑排序求 ve[i] 和逆拓扑有序求 vl[i] 时, 所需时间为O(n+e), 求各个活动的 e[k]和 l[k]时所需时间为O(e), 总共花费时间仍然是O(n+e)。

181 7.6 最短路径 (Shortest Path)

182 7.6 最短路径 (Shortest Path) 求从某个源点到其余各点的最短路径 — Dijkstra算法 每一对顶点之间的最短路径
— Floyd算法

183 7.6.1 从源点到其余各点的最短路径 … v1 v2 源点 1. 迪杰斯特拉(Dijkstra)算法思想
依最短路径的长度递增的次序求得各条路径 其中，从源点到顶点v的最短路径是所有路径中长度最短者。 v1 v2 … 源点

184 1.迪杰斯特拉(Dijkstra)算法思想（continue)
路径长度最短的最短路径的特点: 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 下一条路径长度次短的最短路径的特点: 它只可能有两种情况:或者是直接从源点到该点(只含一条弧)； 或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)。

185 1.迪杰斯特拉(Dijkstra)算法思想(continue)
再下一条路径长度次短的最短路径的特点: 它可能有三种情况：或者是，直接从源点到该点(只含一条弧)； 或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是，从源点经过顶点v2，再到达该顶点。 其余最短路径的特点： 它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。

186 1.迪杰斯特拉(Dijkstra)算法思想(continue)
求最短路径步骤 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值 若存在<V0,Vi>，为<V0,Vi>弧上的权值 若不存在<V0,Vi>，为 从T中选取一个其距离值为最小的顶点W，加入S 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值 重复上述步骤，直到S中包含所有顶点，即S=V为止

187 5 1 6 4 3 2 8 30 13 7 17 32 9 终点 从V0到各终点的最短路径及其长度 V1 V2 V3 V4 V5 V6 Vj 13 <V0,V1> 8 <V0,V2>  30 <V0,V4> 32 <V0,V6> V2:8 13 <V0,V1> <V0,V2,V3> 30 <V0,V4>  32 <V0,V6> V1:13 13 <V0,V2,V3> 30 <V0,V4> 22 <V0,V1,V5> 20 <V0,V1,V6> V3:13 19 <V0,V2,V3,V4> 22 <V0,V1,V5> 20 <V0,V1,V6> V4:19 21 <V0,V2,V3,V4,V5> 20 <V0,V1,V6> V6:20 <V0, V1,V6>

188 2.迪杰斯特拉(Dijkstra)算法实现 设置辅助数组Dist，其中每个分量Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径。 一般情况下， Dist[k] = <源点到顶点 k 的弧上的权值> 或者 = <源点到其它顶点的路径长度> + <其它顶点到顶点 k 的弧上的权值>

189 2.迪杰斯特拉(Dijkstra)算法实现 1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。 V0和k之间存在弧 V0和k之间不存在弧 其中的最小值即为最短路径的长度。 2）修改其它各顶点的Dist[k]值。 假设求得最短路径的顶点为u， 若 Dist[u]+G.arcs[u][k]<Dist[k] 则将 Dist[k] 改为 Dist[u]+G.arcs[u][k]

190 迪杰斯特拉(Dijkstra)算法 void ShortestPath ( int v ){ //v是源 for ( int i = 0; i < n; i++) { dist[i] = Edge[v][i]; //dist数组初始化 S[i] = 0; if ( i != v && dist[i] < n) path[i] = v; else path[i] = -1; //path数组初始化 } // for S[v] = 1; dist[v] = 0; //顶点v加入顶点集合

191 //选择当前不在集合S中具有最短路径的顶点u
for ( i = 1; i < n; i++ ) { float min = MAX; int u = v; for ( int j = 0; j < n; j++ ) if ( !S[j] && dist[j] < min ) { u = j; min = dist[j]; } S[u] = 1; //将顶点u加入集合S for ( int w = 0; w < n; w++ ) //修改 if ( !S[w] && Edge[u][w] < MAXNUM && dist[u] + Edge[u][w] < dist[w] ) { dist[w] = dist[u] + Edge[u][w]; path[w] = u; } // for w } // for i } // ShortestPath

192 3. Dijkstra算法分析： for I 的外层循环做n-1次； for w的内层循环做n次 所以： 算法的时间复杂度：T(n)=O(n2) 考虑如何获得最短路径？ 即如何实现 getPath(k)

193 例3： 与最小生成树的不同点：路径可能是累加的！ dist[w] 5 4 3 1 2 100 60 30 10 20 50 ∞ ∞ ∞ ∞
终点 从v0到各终点的dist值和最短路径 v1 v2 v3 v4 v5 vj dist[w] 5 4 3 1 2 100 60 30 10 20 50 10 {v0,v2} ∞ 30 {v0,v4} 100 {v0, v5} ∞ ∞ ∞ 60 {v0,v2,v3} 10 {v0,v2} 50 {v0,v4,v3} 50 {v0,v4,v3} 30 {v0,v4} 30 {v0,v4} 60 {v0,v4,v3,v5} 100 {v0, v5} 90 {v0,v4, v5} 1 2 3 4 5 v2 v4 v3 v5 s {v0,v2} {v0 ,v2 ,v4} {v0 ,v2 ,v4 ,v3} {v0 ,v2 ,v4 ,v3 ,v5} 与最小生成树的不同点：路径可能是累加的！

194 7.6.2 所有顶点之间的最短路径 1.问题的提出：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi  vj，要求求出vi 与vj之间的最短路径和最短路径长度。 2.解决办法 方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次—— T(n)=O(n³) 方法二：弗洛伊德(Floyd)算法

195 3. Floyd算法思想：逐个顶点试探法 求最短路径步骤 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为 逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值 所有顶点试探完毕，算法结束

196 3  0 初始： 路径： AB AC BA BC CA 例 A C B 2 6 4 3 11 加入V1： 路径： AB AC BA BC CA CAB 加入V2： 路径： AB ABC BA BC CA CAB 加入V3： 路径： AB ABC BCA BC CA CAB

197 初始： 3  0 length= path= 例 1 3 2 6 4 11 加入V1： length= path= 加入V2： length= path= 加入V3： length= path=

198 4.论点：A(-1) [i][j]是从顶点vi 到vj , 中间顶点是v1的最短路径的长度, A(k) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度, A(n-1)[i][j]是从顶点vi 到vj 的最短路径长度。 证明：归纳证明，施归纳与s (上角标); (1) 归纳基础：当s=-1 时， A(-1) [i][j]= Edge[i][j], vi 到vj , 不经过任何顶点的边，是最短路径。 (2)归纳假设：当s<k时， A(s) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于s的最短路径的长度; (3)当s=k时，

199 A(k-1)[i][j] : 是i到j的最短路径(标号不高于k-1)；
A(k-1) [k][j] A(k-1) [i][k] i j A(k-1) [i][j] 因：A(k) [i][j] = min { A(k-1)[i][j]， A(k-1)[i][k] + A(k-1)[k][j] } 由归纳假设知： A(k-1)[i][j] : 是i到j的最短路径(标号不高于k-1)； A(k-1)[i][k] :是i到k的最短路径(标号不高于k-1) ； A(k-1)[k][j] :是k到j的最短路径(标号不高于k-1) ； 所以： A(k) [i][j] 是i到j的最短路径(标号不高于k)

200 5.算法实现 图用邻接矩阵存储 edge[ ][ ]存放最短路径长度 path[i][j]是从Vi到Vj的最短路径上Vj前一顶点序号

201 6.算法描述 void floyd ( ){ for ( int i = 0; i < n; i++ ) //矩阵dist与path初始化 for ( int j = 0; j < n; j++ ) { //置A(-1) dist[i][j] = Edge[i][j]; path[i][j] = -1; } // 初始不经过任何顶点 for ( int k = 0; k < n; k++ ) //产生dist(k)及path(k) for ( i = 0; i < n; i++ ) for ( j = 0; j < n; j++ ) if (dist[i][k] + dist[k][j] < dist[i][j] ) { dist[i][j] = dist[i][k] + dist[k][j]; path[i][j] = k; }//缩短路径, 绕过 k 到 j } // floyd

202 7.算法分析： 设最内层循环体为基本操作，算法有三层循环，每层循环n次，所以 T(n)=O(n3)

203

204 以 Path(3)为例，对最短路径的读法加以说明。从A(3)知，顶点1到0的最短路径长度为a[1][0] = 11,
其最短路径看 path[1][0] = 2，path[1][2] = 3，path [1][3] = 1, 表示顶点0  顶点2  顶点3  顶点1;从顶点1到顶点0最短路径为<1, 3>,<3, 2>,<2, 0>。

205 Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路。
本章给出的求解最短路径的算法不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图，只要在顶点vi 与vj 之间存在无向边(vi , vj )，就可以看成是在这两个顶点之间存在权值相同的两条有向边< vi , vj >和< vj , vi >。

206 本章小结 图 Dijkstra算法 Floyd算法 最短路径 邻接矩阵 邻 接 表 十字链表 邻接多重表 有向(无环)图的应用 存储结构
深度优先搜索DFS 广度优先搜索DFS 无向图的应用 遍 历 图的连通分量 图的生成树 （利用DFS） Prim算法 Kruskal算法 最小生成树 (利用DFS和BFS)

207 本章小结 熟悉图的各种存储结构及其构造算法;理解实际问题的求解效率与采用何种存储结构和算法有密切联系； 熟练掌握图的两种搜索路径的遍历；遍历的逻辑定义、深度优先搜索和广度优先搜索的算法 注意图的遍历算法与树的遍历算法之间的类似和差异； 掌握图的各种应用算法。

208 本章作业 书面作业: p47: 7.1题, 7.5题 p48: 7.7题, 7.9题,7.10题 7.11题 上机作业:
3.最短路径

209 本章结束！

210 本章作业 书面作业: p47: 7.1题, 7.5题 p48: 7.7题, 7.9题,7.10题 7.11题 上机作业:
3.最短路径问题