第7章 图 本章主题：图的基本概念、图的存储结构和图的常用算法 教学目的： 教学重点：图的各种存储方式及其运算

Presentation on theme: "第7章 图 本章主题：图的基本概念、图的存储结构和图的常用算法 教学目的： 教学重点：图的各种存储方式及其运算"— Presentation transcript:

1 第7章 图 本章主题：图的基本概念、图的存储结构和图的常用算法 教学目的： 教学重点：图的各种存储方式及其运算
第7章 图 本章主题：图的基本概念、图的存储结构和图的常用算法 教学目的： 教学重点：图的各种存储方式及其运算 教学难点：图结构存储方式的选择，几种经典图算法的实现 本章内容：图的基本概念 图的存储结构        图的遍历    最小生成树   最短路径        拓扑排序 关键路径 2018/12/9

2 本章学习导读 本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该： 1) 了解图的定义和术语
1)  了解图的定义和术语 2) 掌握图的各种存储结构 3)  掌握图的深度优先搜索和广度优先搜索遍历算法 4) 理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法 2018/12/9

3 图（Graph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。
在线性结构中，结点之间的关系是线性关系，除开始结点和 终端结点外，每个结点只有一个直接前趋和直接后继。 在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。 在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。 由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。 2018/12/9

4 7.1 图及其基本运算 7. 1 .1 图的定义 图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V, R )
7.1 图及其基本运算 图的定义 图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V, R ) V = { x | x  某个数据对象} ， 是顶点的有穷非空集合； R——边的有限集合 R = {(x, y) | x, y  V } 无向图 或 R = {<x, y> | x, y  V && Path (x, y)}有向图 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。x弧尾，y弧头。 2018/12/9

5 有向图中：边用<x, y>表示，且x与y是有序的。 a. 有向图中的边称为“弧” b. x——弧尾或初始点 y——弧头或终端点
有向图与无向图 有向图中：边用<x, y>表示，且x与y是有序的。 a. 有向图中的边称为“弧” b. x——弧尾或初始点 y——弧头或终端点 无向图：边用(x, y) 表示，且顶x与 y是无序的。 完全图 在具有n 个顶点的有向图中，最大弧数为 n(n-1) 在具有n 个顶点的无向图中，最大边数为 n(n-1)/2 顶点的度 无向图：与该顶点相关的边的数目 有向图： 入度ID(v) ：以该顶点为头的弧的数目 出度OD(v) ：以该顶点为尾头的弧的数目 在有向图中, 顶点的度等于该顶点的入度与出度之和。 2018/12/9

6 图7-1 无向图和有向图 2018/12/9

7 在图7-1中，图(a)为无向图，其中G1的顶点集合和边集合分别为： V(G1)={1，2，3，4，5，6，7}，
E(G1)={(1，2)，(l，3)，(2，3)，(3，4)，(3，5)，(5，6)，(5，7)}。 图(c)为有向图，其中G3的顶点集合和弧集合分别为 V(G3)={1，2，3，4，5，6}， E(G3)={<1，2>，<1，3>，<1，4>，<3，1>，<4，5>，<5，6>，<6，4>} 2018/12/9

8 7.1.2 图的基本术语 1． 顶点的度 与顶点v相关的边或弧的数目称作顶点v的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。 例如图7-1中，无向图G1中顶点3的度为4，顶点5的度为3。 例如在图7-1中，有向图G3中顶点1的出度OD (1)=3，入度ID (1)=1，其度TD (1)=4。 2018/12/9

9 若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。
2．路径和回路 在无向图G中，若存在一个顶点序列Vp ,Vi1，Vi2，…，Vin，Vq, 使得（Vp,Vi1）,(Vi1,Vi2),…..，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。 若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。 起点和终点相同的路径称为回路； 简单路径组成的回路称为简单回路。 路径长度 路径上经过的边的数目称为该路径的路径长度。 非带权图的路径长度是指此路径上边/弧的条数。 带权图的路径长度是指路径上各边/弧的权之和。 2018/12/9

10 简单路径 若路径上各顶点 v1,v2,...,vm 均不互相重复, 则称这样的路径为简单路径。
2018/12/9

11 3.边和弧 边: 无向图中顶点的偶对，写成（Vx，Vy）或（Vy，Vx）。 弧: 有向图中顶点的偶对,〈Vx,Vy〉表示从Vx到Vy。
弧头: 弧的终点 弧尾: 弧的起点 弧 〈Vx，Vy〉 弧尾Vx 弧头Vy 2018/12/9

12 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。
4．子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。 2018/12/9

13 5．连通性 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点vi和vj（vi，vj∈V）都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 图7-1中G1是连通图，G2是非连通图。 G2中有3个连通分量，如图7-3（a）所示。 6 ．强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 图7-3 连通分量和强连通分量 2018/12/9

14 权 某些图的边或弧具有与它相关的数, 称之为权。权可以代表一个顶点到另一个顶点的距离，耗费等。
7．网络 权 某些图的边或弧具有与它相关的数, 称之为权。权可以代表一个顶点到另一个顶点的距离，耗费等。 网络 这种带权连通图图一般称为网络。如图7-4所示。 2018/12/9

15 生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。
8．生成树、生成森林 生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。 生成树是对连通图而言的 是连同图的极小连同子图 包含图中的所有顶点 有且仅有n-1条边 非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。 2018/12/9

16 Vx Vy Vx Vy 9．邻接点 顶点: 图中的结点 邻接点: 无向图中，若边(Ｖx,Ｖy)E，
两顶点之间有条边，则两顶点互 为邻接点。 x —— y ( x ,y ) 有向图中，若弧(Ｖx,Ｖy)E， 从x到y有一条弧，则y是x的邻接点， 但x不是y的邻接点。 x y <x ,y > Vx Vy Ｖx、Ｖy互为邻接点 Vx Vy Ｖy是Ｖx的邻接点 2018/12/9

17 （1）顶点定位运算 确定顶点v在图中的位置； （2）取顶点运算 求取图中第i个顶点； （3）求第一个邻接点运算 求图中顶点v的第一个邻接点；
7.1.3 图的基本运算 图的基本运算也包括查找、插入和删除。 （1）顶点定位运算 确定顶点v在图中的位置； （2）取顶点运算 求取图中第i个顶点； （3）求第一个邻接点运算 求图中顶点v的第一个邻接点； （4）求下一个邻接点运算 已知w为图中顶点v的某个邻接点，求顶点w的下一个邻接点； （5）插入顶点运算 在图中增添一个顶点v作为图的第n+1个顶点，其中n为插入该顶点前图的顶点个数； （6）插入弧运算 在图中增添一条从顶点v到顶点w的弧。 （7）删除顶点运算 从图中删除顶点v以及所有与顶点v相关联的弧。 （8）删除弧运算 从图中删除一条从顶点v到顶点w的弧。 2018/12/9

18 7.2 图的存储结构 7.2.1 邻接矩阵 邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G＝(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵。 无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。 在有向图中： 第 i 行 1 的个数就是顶点 i 的出度， 第 j 列 1 的个数就是顶点 j 的入度。 在无向图中, 第 i 行 (列) 1 的个数就是顶点i 的度。 2018/12/9

19 图7-5 无向图及其邻接矩阵 图7-6 有向图及其邻接矩阵 2018/12/9

20 对于无向图，（vi，vj）和（vj，vi）表示同一条边，因此，在邻接矩阵中Aij=Aji。
无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。 对有向图，弧<vi，vj>和< vj，vi >表示方向不同的两条弧，Aij和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。 邻接矩阵表示法适合于以顶点为主的运算。 2018/12/9

21 对于无向图，顶点vi的度等于邻接矩阵第i行的元素之和，即：
TD（vi）= 对于有向图，顶点vi的出度OD (vi)等于邻接矩阵第i行元素之和；顶点vi的入度ID (vi)等于邻接矩阵第i列元素之和，即 ： OD (vi)= ID (vi)= 对于带权图的邻接矩阵，定义为： 2018/12/9

22 顶点表: 一个记录各个顶点信息的一维数组， 邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。
使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下： #define MAX_VERTEX_NUM //最大顶点数 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵类型 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点表 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的顶点数和弧数 } MGraph; 由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。 2018/12/9

23 建立邻接矩阵算法: void CreateMGraph(MGraph &G) { int i,j,k,w; char v1,v2;
printf("Input vexnum & arcnum:"); scanf("%d,%d",&G.vexnum,&G.arcnum); printf("Input Vertices:"); scanf("% s",G.vexs); for (i=0;i<G.vexnum;i++) scanf("%c",&G.vexs[i]); for (j=0;j<G.vexnum;j++) G.arcs[i][j]=0; for (k=0;k<G.arcnum;k++) { printf("Input Arcs(v1,v2 & w):\n"); scanf("%c%c,%d",&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); j=LocateVex(G,v2); G.arcs[i][j]=w; G.arcs[j][i]=w; } return; 2018/12/9

24 void PrintMGraph(MGraph G) //输出 { int i,j; printf("Output Vertices:");
printf("%s",G.vexs); printf("\n"); printf("Output AdjMatrix:\n"); for (i=0;i<G.vexnum;i++) { for (j=0;j<G.vexnum;j++) printf("%4d",G.arcs[i][j]); printf("\n"); } return; 2018/12/9

25 7.2.2 邻接表 图的链式存储结构 1) 为每个顶点建立一个单链表， 2) 第i个单链表中包含顶点Vi的所有邻接顶点。
邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。 2018/12/9

26 把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点（边结点），邻接点域adjvex保存与该边相关联的另一顶点的顶点下标 ， 链域nextarc存放指向同一链表中下一个表结点的指针 ，数据域info存放边的权。边链表的表头指针存放在头结点中。头结点以顺序结构存储，其数据域data存放顶点信息，链域firstarc指向链表中第一个顶点。 表结点 头结点 adjvex nextarc info data firstarc 2018/12/9

27 带权图的边结点中info保存该边上的权值 。 顶点 Vi 的边链表的头结点存放在下标为 i 的顶点数组中。
在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。 设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。 建立邻接表的时间复杂度为O(n*e)。若顶点信息即为顶点的下标，则时间复杂度为O(n+e)。 2018/12/9

28 在有向图的邻接表中，第 i 个链表中结点的个数是顶点Vi的出度。 在有向图的逆邻接表中，第 i 个链表中结点的个数是顶点Vi 的入度。
有向图的邻接表和逆邻接表 在有向图的邻接表中，第 i 个链表中结点的个数是顶点Vi的出度。 在有向图的逆邻接表中，第 i 个链表中结点的个数是顶点Vi 的入度。 2018/12/9

29 图7-7 为图7-6 (a)的的邻接表和逆邻接表 7-6 (a) 图7-7 有向图的邻接表和逆邻接表 2018/12/9

30 网络 (带权图) 的邻接表 2018/12/9

31 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int info;
存储表示 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int info; }ArcNode; //边结点类型 typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; //邻接表 int vexnum,arcnum; }ALGraph; 2018/12/9

32 int LocateVex(ALGraph G,char u) { int i; for (i=0;i<G.vexnum;i++)
{ if(u= =G.vertices[i].data) return i; } if (i= =G.vexnum) {printf("Error u!\n");exit(1);} return 0; } void CreateALGraph_adjlist(ALGraph &G) { int i,j,k,w; char v1,v2; ArcNode *p; printf("Input vexnum & arcnum:"); scanf("%d,%d",&G.vexnum,&G.arcnum); printf("Input Vertices:"); for (i=0;i<G.vexnum;i++) { scanf("%c",&G.vertices[i].data); G.vertices[i].firstarc=NULL; } 2018/12/9

33 printf("Input Arcs(v1,v2 & w):\n");
for (k=0;k<G.arcnum;k++) { scanf("%c,%c,%d",&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info = w; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; } return; 2018/12/9

34 7.2.3 十字链表 十字链表 (Orthogonal List)是有向图的另一种链式存储结构。 可看作是将有向图的邻接表和逆邻接表结合的一种链表。 在十字链表中，为每个顶点vi设置一个结点，它包含数据域data和两个链域firstout、firstin，称为顶点结点。数据域data用于存放顶点vi的有关信息；链域firstin指向以顶点vi为弧头的第一个弧结点；链域firstout指向以顶点vi为弧尾的第一个弧结点。 弧结点包括四个域：尾域tailvex、头域headvex，链域hlink和tlink。 hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧；data顶点信息，firstin以该顶点为头的第一个弧结点，firstout以该结点为尾的第一个弧结点 headvex tailvex hlink tlink info 弧结点 顶点结点 firstin data firstout 2018/12/9

35 采用十字链表表示有向图，很容易找到以顶点vi为弧尾的弧和以顶点vi为弧头的弧，因此顶点的出度、入度都很容易求得。
图7-8为图7-6 (a)有向图的十字链表。 图7-8 十字链表 采用十字链表表示有向图，很容易找到以顶点vi为弧尾的弧和以顶点vi为弧头的弧，因此顶点的出度、入度都很容易求得。 2018/12/9

36 #define MAXV <最大顶点个数> typedef struct //弧结点
十字链表的数据类型定义如下： #define MAXV <最大顶点个数> typedef struct //弧结点 { int tailvex,headvex; //弧尾和弧头顶点位置 struct ArcNode *hlink,*tlink; //弧头相同和弧尾相同的弧的链域 }ArcNode; typedef struct //顶点结点 { VertexType data; //顶点信息 ArcNode *firstin,*firstout; //分别指向该顶点的第一条入弧和出弧 }VexNode; 2018/12/9

37 邻接多重表是无向图的另一种链式存储结构。在邻接多重表中设置一个边结点表示图中的一条边。边结点包含五个域，结构如下所示：
7.2.4 邻接多重表 邻接多重表是无向图的另一种链式存储结构。在邻接多重表中设置一个边结点表示图中的一条边。边结点包含五个域，结构如下所示： 其中：mark 域 标志域，用于对该边进行标记； ivex 域 存放该边依附的一个顶点vi的位置信息； ilink 域 该链域指向依附于顶点vi的另一条边的边结点； jvex 域 存放该边依附的另一个顶点vj的位置信息； jlink 域 该链域指向依附于顶点vj的另一条边的边结点。 邻接多重表为每个顶点设置一个结点，其结构如下： 2018/12/9

38 图7-9为图7-5 (a)无向图的邻接多重表。 图7-9 邻接多重表
由邻接多重表可以看出，表示边（vi，vj）的边结点通过链域ilink和jlink链入了顶点vi和顶点vj的两个链表中，实现了用一个边结点表示一个边的目的，克服了在邻接表中用两个边结点表示一个边的缺点。因此邻接多重表是无向图的一种很有效的存储结构。 2018/12/9

39 邻接多重表的结点数据类型定义如下： #define MAXV <最大顶点个数> typedef struct //边结点类型
{ int mark; //访问标识 int ivex,jvex; //该边的两个顶点位置信息 struct Enode *ilink,*jlink; //分别指向依附这两个顶点的下一条边 }Enode; typedef struct //顶点结点类型 { VertexType data; //顶点数据域 ENode *firstedge; //指向第一条依附该顶点的边 }Vnode; 2018/12/9

40 7.3 图的遍历 和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历。 (Traversing Graph)。 但是，在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中或许还有顶点没有访问到，因此，图的遍历较树的遍历更复杂。 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 图的遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。对每种搜索顺序，访问各顶点的顺序也不是唯一的。 2018/12/9

41 7.3.1 深度优先搜索（DFS） 1． 深度优先搜索思想
1． 深度优先搜索思想 深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索递归调用包含以下操作： （1）访问搜索到的未被访问的邻接点； （2）将此顶点的visited数组元素值置1； （3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。 深度优先搜索DFS可描述为： （1）访问v0顶点； （2）置 visited[v0]=1； （3）搜索v0未被访问的邻接点w，若存在邻接点w，则DFS(w)。 2018/12/9

42 遍历过程： DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。 2018/12/9

43 图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
深度优先搜索的示例 图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited [i] 为 1，防止它被多次访问。 2018/12/9

44 对上图，深度优先搜索遍历的顺序（之一）为： v1 →v2→v4→ v8→ v5→v6→v3→v7。
图7-10 深度优先搜索 对上图，深度优先搜索遍历的顺序（之一）为： v1 →v2→v4→ v8→ v5→v6→v3→v7。 2018/12/9

45 深度优先搜索算法： int visited[MAX_VERTEX_NUM]; void DFS(ALGraph G, int v)
{ ArcNode *p; printf("%c",G.vertices[v].data); visited[v]=1; p=G.vertices[v].firstarc; while (p) { if (!visited[p->adjvex]) DFS(G,p->adjvex); p=p->nextarc; } } //从第v个顶点出发DFS 2018/12/9

46 void DFSTraverse(ALGraph G) { for (int v=0;v<G.vexnum;++v)
visited[v]=0; for (v=0;v<G.vexnum;++v) if (!visited[v]) DFS(G,v); } 对于连通图，从一个顶点出发，调用DFS函数即可将所有顶点都遍历到。 2018/12/9

47 7.3.2 广度优先搜索（BFS） 1． 广度优先搜索思想 广度优先搜索遍历类似于树的按层次遍历。
1． 广度优先搜索思想 广度优先搜索遍历类似于树的按层次遍历。 对于无向连通图，广度优先搜索是从图的某个顶点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。 2018/12/9

48 1． 广度优先搜索思想 设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是：
1． 广度优先搜索思想 设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是： （1）从图中的某个顶点V出发，访问之；并将其访问标志置为已被访问，即visited[i]=1； （2）依次访问顶点V的各个未被访问过的邻接 点，将V的全部邻接点都访问到； （3）分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，并使“先被访问的顶 点的邻接点”先于“后被访问的顶点的邻接 点”被访问，直到图中所有已被访问过的顶 点的邻接点都被访问到。 依此类推，直到图中所有顶点都被访问完为止 。 2018/12/9

49 广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中需要设置一个队列Queue，使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点。 广度优先搜索的示例 广度优先搜索过程 广度优先生成树 2018/12/9

50 广度优先搜索过程可描述为： （1）f=0;r=0; //队列初始化，空队列；f-队首指针，r-队尾指针 （2）访问v0;
（3）visited[v0]=1; （4）insert(Queue,f,r,v0); //v0进入队尾 （5）while f>0 do (i)delete(Queue,f,r,x); //队首元素出队并赋于x (ii)对所有x的邻接点w if visited[w]=0 then （a）访问w; （b）visited[w]=1; （c）insert(Queue,f,r,w); //w进队列 2018/12/9

51 以邻接表为存储结构，广度优先搜索遍历算法如下： #define MAXV <最大顶点数>
void bfs(ALGraph *g,int v) { ArcNode *p; int queue[MAXV]; //定义存放队列的数组 int visited[MAXV]； //定义存放结点的访问标志的数组 int f=0,r=0,x,i; //队列头尾指针初始化，把队列置空 for(i=0,i<g->n;i++) //访问标志数组初始化 visited[i]=0; printf(“％d”,v); //访问初始顶点v visited[v]=1; //置已访问标记 r=(r+1)％MAXV; queue[r]=v; //v进队 while(f!=r){ //若队列不空时循环 f=(f+1)％MAXV; x=queuet[f]; //出队并赋给x p=g->adjlist[x].firstarc; //找与顶点x邻接的第一个顶点 2018/12/9

52 p=g->adjlist[x].firstarc; //找与顶点x邻接的第一个顶点 while(p!=NULL)
{ if (visited[p->adjvex]==0) //若当前邻接点未被访问 { visited[p->adjvex]=l; //置该顶点已被访问的标志 printf(“％d”，p->adjvex); //访问该顶点 r=(r+1)％MAXV; queue[r]=p->adjvex; //该顶点进队 } p=p->nextarc; //找下一个邻接点 // w进队列 2018/12/9

53 算法分析： 如果使用邻接表表示图，则循环的总时间代价为 d0 + d1 + … + dn-1 = O(e)，其中的 di 是顶点 i 的度。
如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。 2018/12/9

54 7.4 最小生成树 1. 生成树 在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G′ 称做图G的生成树。一个图可以有多个生成树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同，例如图7-12的(b) 和(c) 为图7-12 (a) 的两棵生成树。其中 (b) 是通过DFS得到的，称为深度优先生成树；(c) 是通过BFS得到的，称为广度优先生成树。 图7-12 生成树 2018/12/9

55 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。而所有包含n-1 条边及n个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图.
由于使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树 在图论中，常常将树定义为一个无回路连通图。 对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。 2018/12/9

56 假设把n个城市看作图的n个顶点，边表示两个城市之间的线路，每条边上的权值表示铺设该线路所需造价。铺设线路连接n个城市，但不形成回路，这实际上就是图的生成树，而以最少的线路铺设造价连接各个城市，即求线路铺设造价最优问题，实际上就是在图的生成树中选择权值之和最小的生成树。构造最小生成树的算法有很多，下面分别介绍克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法。 7.4.1 克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。 2018/12/9

57 (1) 置U的初值等于V，TE的初值为空集；
算法的基本思想： 在图中任取一个顶点K作为开始点，令U={k}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离, 使之保持最小，再重复此过程，直到W为空集止。 假设G=（V，E）是一个具有n个顶点的带权无向连通图，T= (U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造最小生成树的过程如下： (1) 置U的初值等于V，TE的初值为空集； (2) 按权值从小到大的顺序依次选取图G中的边，若选取的边未使生成树T形成回路，则加入TE；若选取的边使生成树T形成回路，则将其舍弃。循环执行(2)，直到TE中包含(n-1)条边为止。 2018/12/9

58 应用克鲁斯卡尔算法构造最小生成树的过程:
2018/12/9

59 为实现克鲁斯卡尔算法需要设置一维辅助数组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; 2018/12/9

60 Void kruskal(Edge E[],int n,int e) { int i,j,m1,m2,sn1,sn2,k;
int vset[MAXV]; for(i=0;i<n;i++) //初始化辅助数组 for(i=0;i<n;i++) //初始化辅助数组 vset[i]=i; k=1; //表示当前构造最小生成树的第k条边，初值为1 j=0; //E中边的下标，初值为0 while(k<e) //生成的边数小于e时继续循环 { ml=E[j].vex1;m2=E[j].vex2;//取一条边的两个邻接点 sn1=vset[m1];sn2=vset[m2]; //分别得到两个顶点所属的集合编号 if(sn1!=sn2) //两顶点分属于不同的集合，该边是最小生成树的一条边 2018/12/9

61 { printf(“(m1，m2)：％d＼n”,E[j].weight);
k++; //生成边数增l for(i=0;i<n;i++) //两个集合统一编号 if (vset[i]= //集合编号为sn2的改为sn1 vset[i]=sn1; } j++; //扫描下一条边 如果给定带权无向连通图G有e条边，且边已经按权值递增的次序存放在数组E中，则用克鲁斯卡尔算法构造最小生成树的时间复杂度为O (e)。克鲁斯卡尔算法的时间复杂度与边数e有关，该算法适合于求边数较少的带权无向连通图的最小生成树。 2018/12/9

62 7.4.2 普里姆(Prim)算法 普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。 从连通网络 N = { V, E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2018/12/9

63 （1）初始状态，TE为空，U={v0}，v0∈V；
假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造G的最小生成树T的步骤如下： （1）初始状态，TE为空，U={v0}，v0∈V； （2）在所有u∈U，v∈V-U的边(u，v) ∈E中找一条代价最小的边(u′，v′)并入TE，同时将v′并入U； 重复执行步骤（2）n-1次，直到U=V为止。 在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。 对于每一个顶点v∈V-U，closest[v]为U中距离v最近的一个邻接点，即边 (v，closest[v]) 是在所有与顶点v相邻、且其另一顶点j∈U的边中具有最小权值的边，其最小权值为lowcost[v]，即lowcost[v]=cost[v][closest[v]]， 2018/12/9

64 lowcost域：存放在V-U中各个顶点到集合U中的当前最小权值； adjvex域： 记录该边所依附的在U中的顶点
采用邻接表作为存储结构： 设置一个辅助数组closedge[]： lowcost域 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值； adjvex域 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。 设置一个辅助数组closedge[]： lowcost域：存放在V-U中各个顶点到集合U中的当前最小权值； adjvex域： 记录该边所依附的在U中的顶点 2018/12/9

65 若选择从顶点0出发，即u0 = 0，则辅助数组的两个域的初始状态为： 然后反复做以下工作： 在 closedge [i]中选择
adjvex  0 && lowcost最小的边 i 用 k 标记它。则选中的权值最小的边为 (closedge[k], G.vexs[k])，相应的权值为 closedge[k].lowcost。 将 closedge[k].adjvex 改为 0, 表示它已加入生成树顶点集合。将边 (closedge[k], G.vexs[k])加入生成树的边集合。 2018/12/9

66 取 lowcost[i] = min{ lowcost[i], G
取 lowcost[i] = min{ lowcost[i], G.arcs[k][i] }，即用生成树顶点集合外各顶点 i 到刚加入该集合的新顶点 k 的距离 G.arcs[k][i] 与原来它们到生成树顶点集合中顶点的最短距离lowcost[i] 做比较, 取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。 如果生成树顶点集合外顶点 i 到刚加入该集合的新顶点 k 的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改adj：adjvex = v。表示生成树外顶点i到生成树内顶点k当前距离最近。 2018/12/9

67 利用普里姆算法建立最小生成树: typedef int VRType; struct{ VertexType adjvex;
VRType lowcost; }closedge[MAX_VERTEX_NUM]; void MiniSpanTree_PRIM(MGraph G,VertexType u){ int k,j,i,minCost; k=LocateVex(G,u); for (j=0;j<G.vexnum;++j) if (j!=k) { closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j]; } 2018/12/9

68 closedge[k].lowcost=0; for (i=1;i<G.vexnum;++i)
{ k=minimum(closedge); minCost=INFINITY; for (j=0;j<G.vexnum;++j) { if (closedge[j].lowcost <minCost && closedge[j].lowcost!=0) { minCost=closedge[j].lowcost; k=j;} } printf("(%c,%c)\n",closedge[k].adjvex,G.vexs[k]); if (G.arcs[k][j]<closedge[j].lowcost) { closedge[j].adjvex=G.vexs[k]; closedge[j].lowcost=G.arcs[k][j];} 2018/12/9

69 普里姆算法中的第二个for循环语句频度为n-1，其中包含的两个内循环频度也都为n-1，因此普里姆算法的时间复杂度为O(n2)。普里姆算法的时间复杂度与边数e无关，该算法更适合于求边数较多的带权无向连通图的最小生成树。 2018/12/9

70 7.5 最短路径 交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通? 在有多条通路的情况下，哪一条路最短?
7.5 最短路径 交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通? 在有多条通路的情况下，哪一条路最短? 交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。 另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路(从其它顶点达到)。 路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。 2018/12/9

71 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
最短路径： 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 对于带权的图，通常把一条路径上所经过边或弧上的权值之和定义为该路径的路径长度。从一个顶点到另一个顶点可能存在着多条路径，把路径长度最短的那条路径称为最短路径，其路径长度称为最短路径长度。无权图实际上是有权图的一种特例，我们可以把无权图的每条边或弧的权值看成是l，每条路径上所经过的边或弧数即为路径长度。本章讨论两种最常见的最短路径问题。 2018/12/9

72 问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。
问题解法 边上权值非负情形的单源最短路径问题 — Dijkstra算法 所有顶点之间的最短路径 — Floyd算法 问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。 为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。 2018/12/9

73 7.5.1 求一顶点（单源点）到其余顶点的最短路径 单源点最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。 迪杰斯特拉(Dijkstra)在做了大量观察后,首先提出了按路径长度递增产生各顶点的最短路径算法,我们称之为迪杰斯特拉算法。 算法的基本思想是:设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个以V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。 2018/12/9

74 具体做法是:设源点为Vl,则S中只包含顶点Vl，令W=V-S，则W中包含除Vl外图中所有顶点，Vl对应的距离值为0，W中顶点对应的距离值是这样规定的：若图中有弧<Vl,Vj>则Vj顶点的距离为此弧权值，否则为∞(一个很大的数)，然后每次从W中的顶点中选一个其距离值为最小的顶点Vm加入到S中，每往S中加入一个顶点Vm，就要对W中的各个顶点的距离值进行一次修改。若加进Vm做中间顶点，使<Vl,Vm>+<Vm,Vj>的值小于<Vl,Vj>值，则用<Vl,Vm>+<Vm,Vj>代替原来Vj的距离，修改后再在W中选距离值最小的顶点加入到S中，如此进行下去，直到S中包含了图中所有顶点为止。 2018/12/9

75 顶点0 顶点2：最短路径为（0，2），最短路径长度为10 顶点0 顶点4：最短路径为（0，4），最短路径长度为30
图7-16 带权有向图 设G=(V，E)是一个带权有向图，指定的顶点v0为源点，求v0到图的其余各顶点的最短路径。如图7-16所示，若以顶点0为v0，它到其余各顶点的最短路径分别为： 顶点0 顶点1：无路径 顶点0 顶点2：最短路径为（0，2），最短路径长度为10 顶点0 顶点4：最短路径为（0，4），最短路径长度为30 顶点0 顶点3：最短路径为（0，4，3），最短路径长度为50 顶点 顶点5：最短路径为（0，4，3，5），最短路径长度为60 2018/12/9

76 从以上图7-16的最短路径可以看出： (1) 最短路径并不一定是经过边或弧数最少的路径。如从顶点0到顶点5的路径（0，5）长度为100，路径（0，4，5）长度为90，路径（0，2，3，5）长度为70，路径（0，4，3，5）长度为60，其中最短路径为（0，4，3，5），最短路径长度为60。 (2) 这些最短路径中，长度最短的路径上只有一条弧，且它的权值在从源点出发的所有弧的权值中最小。如从源点0出发有3条弧，其中以弧<0，2>的权值为最小。此时（0，2）不仅是顶点 0到顶点2 的一条最短路径，而且它在从源点0到其它各顶点的最短路径中长度最短。 (3)按照路径长度递增的次序产生最短路径。求得第二条最短路径（0，4）；之后求得第三条最短路径（0，4，3），它经过已求出的第二条最短路径（0，4）到达顶点3；求得的第四条最短路径（0，4，3，5），经过已求出的第三条最短路径（0，4，3）到达顶点5。 2018/12/9

77 迪杰斯特拉算法的求解过程： 2018/12/9

78 图7-17 迪杰斯特拉算法求最短路径过程及结果 2018/12/9

79 D[j] ← arcs[0][j], j = 1, 2, …, n-1; // n为图中顶点个数 求出最短路径的长度：
Dijkstra算法可描述如下： 初始化： S ← { v0 }; D[j] ← arcs[0][j], j = 1, 2, …, n-1; // n为图中顶点个数 求出最短路径的长度： D[k] ← min{ D[i] }, i  V- S ; S ← S U { k }; 修改： D[i] ← min{ D[i], D[k] + arcs[k][i] }, 对于每一个 i  V- S ; 判断： 若S = V, 则算法结束，否则转。 2018/12/9

80 狄杰斯特拉算法dijkstra，其中n为图G的顶点数，v0为源点。
#define INF //INF表示∞ #define MAXV <最大顶点个数> void dijkstra(int cost[][MAXV]，int n，int vO) { int dist[MAXV]，path[MAXV]； int s[MAXV]； int mindis； int i，j，k； for(i=0;i<n;i++){ dist[i]=cost[vO][i]; //距离初始化 s[i]=0; //s[]初始化 if (cost[vO][i]<INF) //路径初始化 path[i]=vO; else path[i]=-1; } s[vO]=1; //源点v0放入S中 for(i=1;i<n;i++) //重复，直到求出v0到其余所有顶点的最短路径 2018/12/9

81 for(i=1;i<n;i++) //重复，直到求出v0到其余所有顶点的最短路径 { mindis=INF; k=vO;
for(j=1;j<n;j++) //从V-S中选取具有最小距离的顶点v k { if(s[j]==0 && dist[j]<mindis) { k=j; mindis=dist[j]; } s[k]=1; //将顶点k加入S中 for(j=1;j<n;j++) //修改V-S中顶点的距离dist[j] { if(s[j]==0) if(cost[k][j]<INF && dist[k]+cost[k][j]<dist[j]) { dist[j]=dist[k]+cost[k][j]; path[j]=k; dispath(dist,path,s,n,v0); //输出最短路径} 2018/12/9

82 通过path[i]向前回推直到v0为止，可以找出从v 0到顶点v i的最短路径。输出最短路径的算法dispath如下：
void dispath(int dist[],int path[],int s[],int n,int vO) { int i,k; for(i=0;i<n;i++) if(s[i]==1) //S中顶点 { k=i; printf(“％d 到 ％d的最短路径为:”, v0,i); while(k!=v0){ printf(“％d<-”,k); k=path[k]; } printf(“％d 路径长度为:％d＼n”,v0,dist[i]); else printf(“％d<-％d不存在路径＼n”,i,v0); 2018/12/9

83 在狄克斯特拉算法中，求一条最短路径所花费的时间：从V-S中选取具有最小距离的顶点v k花费时间O(n)；修改V-S中顶点的距离花费时间O(n)；输出最短路径花费时间O(n)。因此求出n-1条最短路径的时间复杂度为O(n2)。 2018/12/9

84 每对顶点之间的最短路径 顶点对之间的最短路径是指：对于给定的有向网G=(V,E),要对G中任意一对顶点有序对V、W(V≠W),找出V到W的最短距离和W到V的最短距离。 解决此问题的一个有效方法是:轮流以每一个顶点为源点,重复执行迪杰斯特拉算法n次,即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n3)。 弗洛伊德提出了另外一个求图中任意两顶点之间最短路径的算法，虽然其时间复杂度也是 O(n3)，但其算法的形式更简单，易于理解和编程。 2018/12/9

85 弗洛伊德算法仍然使用前面定义的图的邻接矩阵arcs[n+1][n+1]来存储带权有向图。算法的基本思想是:设置一个nxn的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)[i][j]表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为∞，当K=O时, A (0)[i][j]=arcs[i][j] 以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为： 2018/12/9

86 第一步，让所有边上加入中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的值，完成后得到A(1)，
第二步，让所有边上加入中间顶点2，取A[i][j]与A[i][2]+A[2][j]中较小的值，完成后得到A(2)…，如此进行下去，当第n步完成后，得到A(n)，A(n)即为我们所求结果,A(n)[i][j]表示顶点i到顶点j的最短距离。 因此，弗洛伊德算法可以描述为: A(0)[i][j]=arcs[i][j]; //arcs为图的邻接矩阵 A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]} 其中 k=1,2,…,n 2018/12/9

87 其中 D(-1) [i][j] = G.arcs[i][j]； D(k) [i][j] = min { D(k-1)[i][j]，
Floyd算法的基本思想： 定义一个n阶方阵序列： D(-1), D(0), …, D(n-1). 其中 D(-1) [i][j] = G.arcs[i][j]； D(k) [i][j] = min { D(k-1)[i][j]， D(k-1)[i][k] + D(k-1)[k][j] }, k = 0,1,…, n-1 D(0) [i][j]是从顶点vi 到vj , 中间顶点是v0的最短路径的长度, D(k) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径长度, D(n-1)[i][j]是从顶点vi 到vj 的最短路径长度。 2018/12/9

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

89 #define MAXV <最大顶点个数> void floyd(int cost[][MAXV]，int n)
#define INF //INF表示∞ #define MAXV <最大顶点个数> void floyd(int cost[][MAXV]，int n) { int A[MAXV][MAXV],path[MAXV][MAXV]; int i,j,k; for(i=0;i<n;i++) //赋值A0[i][j]和path0[i][j] for(j=0;j<n;j++) { A[i][j]=cost[i][j]; if cost[i][j]<INF path[i][j]=i; else path[i][j]=-1; } for(k=0;k<n;k++) //向vi与vj之间中n次加入中间顶点vk for(i=0;i<n;i++) for(j=0;j<n;j++) //求min{Ak[i][j]，Ak+1[i][k]+Ak+1[k][j]} if(A[i][j]>(A[i][k]+A[k][j])) 2018/12/9

90 if(A[i][j]>(A[i][k]+A[k][j])) { A[i][j]=A[i][k]+A[k][j];
path[i][j]=k; } dispath(A,path,n); //输出最短路径 以下是输出最短路径的算法dispath，其中ppath（）函数在path中递归输出从顶点vi到vj的最短路径。 void ppath(int path[][MAXV],int i,int j) { int k; k=path[i][j]; if(k==-1) //path[i][j]=-1时,顶点vi和vj之间无中间顶点 return; ppath(path,i,k); printf(“％d,”,k); ppath(path,k,j); 2018/12/9

91 void dispath(int A[][MAXV],int path[][MAXV],int n) { int i,j;
for(i=0;i<n;i++) for(j=0;j<n;j++) { if(A[i][j]==INF) { if(i!=j) printf(“从顶点％d到顶点％d没有路径\n”,i,j); } else { printf(“从顶点％d到顶点％d路径为:”,i,j);； printf(“％d ,”,i); ppath(path,i,j); printf(“％d”,j); printf(“路径长度为:％d\n”,A[i][j]); 弗洛伊德算法包含一个三重循环，其时间复杂度为O(n3)。 2018/12/9

92 7.6 拓扑排序 1.拓扑排序 通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。 例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图7-21给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须先并行学完高等数学、程序设计基础课程。 2018/12/9

93 在图7-22中，我们用一种有向图来表示课程开设，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表示活动的网络(Actire On Vertices)简称为AOV网。
图7-21 课程名称及相应的课程安排次序 图7-22 课程安排的AOV网 2018/12/9

94 AOV网——Activity On Vertex Network
用顶点表示活动，用弧表示活动间 的优先关系的有向图，称为顶点表 示活动的网。 AOV 网中不能有回路 拓扑排序： 假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，…，vn称做一个拓扑序列(Topological Order)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序(Topological Sort)。 2018/12/9

95 由于AOV网中有些活动之间没有次序要求，它们在拓扑序列的位置可以是任意的，因此拓扑排序的结果不唯一。
对图7-22进行拓扑排序，可得一个拓扑序列： C1，C3，C2，C4，C7，C6，C5 也可得到另一个拓扑序列： C2，C7，C1，C3，C4，C5，C6 还可以得到其它的拓扑序列。学生按照任何一个拓扑序列都可以完成所要求的全部课程学习。 在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。 判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。 2018/12/9

96 在AOV网络中选一个没有直接前驱的顶点, 并输出之; 从图中删去该顶点, 同时删去所有它发出的有向边;
进行拓扑排序的方法： 输入AOV网络。令 n 为顶点个数。 在AOV网络中选一个没有直接前驱的顶点, 并输出之; 从图中删去该顶点, 同时删去所有它发出的有向边; 重复以上 、 步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。 2018/12/9

97 拓扑排序的过程 2018/12/9

98 最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。
2018/12/9

99 在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组，表头结点定义如下：
typedef struct //表头结点 { Vertex data; //顶点信息 int count; //存放顶点入度 ArcNode *firstarc; //指向第一条弧 }Vnode; 在执行拓扑排序的过程中，当某个顶点的入度为零(没有前驱顶点)时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，相当于删除所有以该顶点为尾的弧。为了避免重复检测顶点的入度是否为零，需要设立一个栈来存放入度为零的顶点。执行拓扑排序的算法如下： 2018/12/9

100 void topsort(VNode adj[],int n) { int i,j;
int stack[MAXV],top=0; //栈stack的指针为top ArcNode *p; for(i=0;i<n;i++) if(adj[i].count==0) //建入度为0的顶点栈 { top++; stack[top]=i; } while(top>0) //栈不为空 { i=stack[top]; top--; //顶点vi出栈 printf(“％d”,i); //输出vi p=adj[i].firstarc; //指向以vi为弧尾的第一条弧 while(p!=NULL) { j=p->adjvex; //以vi为弧尾的弧的另一顶点vj 2018/12/9

101 while(p!=NULL) { j=p->adjvex; //以vi为弧尾的弧的另一顶点vj adj[j].count--; //顶点vj的入度减1 if(adj[j].count==0) //入度为0的相邻顶点入栈 { top++; stack[top]=j; } p=p->nextarc; //指向以vi为弧尾的下一条弧 可见，对于有n个顶点和e条边的有向图而言，for循环中建立入度为0的顶点栈时间为O（n）；若在拓扑排序过程中不出现有向环，则每个顶点出栈、入栈和入度减1的操作在while(top>0)循环语句中均执行e次，因此拓扑排序总的时间花费为O (n+e)。 2018/12/9

102 【例7-3】请给出图7-24所示的有向图G的拓扑排序过程。
2018/12/9

103 【解】依据拓扑排序算法，将图7-24中入度为0的两个顶点l和5相继入栈；顶点5出栈，输出，且以顶点5为尾的弧的另一顶点入度减一，如另一顶点2的入度值由2变为1，另一顶点6的入度值由1变为0。将入度为0的顶点6入栈；顶点6出栈，输出，且以顶点6为尾的弧的另一顶点入度减一，如另一顶点4的入度值由2变为1；依次类推得到拓扑序列：561234，拓扑排序过程栈的变化见图7-25。入度为0的顶点可以按不同顺序入栈，因此还可以得到其它拓扑序列：152364，152634，156234， ，516234，512634。 图7-25 拓扑排序过程的栈 2018/12/9

104 7.7 关键路径 如果在无有向环的带权有向图中 用有向边表示一个工程中的各项活动(Activity)
7.7 关键路径 如果在无有向环的带权有向图中 用有向边表示一个工程中的各项活动(Activity) 用边上的权值表示活动的持续时间(Duration) 用顶点表示事件(Event) 则这样的有向图叫做用边表示活动的网络，简称AOE (Activity On Edges)网络。 AOE网是一个带权的有向无环图。 AOE网络在某些工程估算方面非常有用。例如，可以使人们了解： (1) 完成整个工程至少需要多少时间(假设网络中没有环)? (2) 为缩短完成工程所需的时间, 应当加快哪些活动? 2018/12/9

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

106 图7-26就是一个AOE网，该网中有11个活动和9个事件。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如事件v5表示a4和a5活动已经完成，a7和a8活动可以开始。每个弧上的权值表示完成相应活动所需要的时间，如完成活动a1需要6天，a8需要7天。 图7-26 AOE网 2018/12/9

107 AOE网常用于表示工程的计划或进度。由于实际工程只有一个开始点和一个结束点，因此AOE网存在唯一的入度为0的开始点（又称源点）和唯一的出度为0的结束点（又称汇点），例如图7-26的AOE网从事件v1开始，以事件v9结束。同时AOE网应当是无环的。 2018/12/9

108 是在保证汇点Vn-1 在Ve[n-1] 时刻完成的前提下，事件Vi 的允许的最迟开始时间。
定义几个与计算关键活动有关的量： 事件Vi 的最早可能开始时间Ve(i) 是从源点V0 到顶点Vi 的最长路径长度。 事件Vi 的最迟允许开始时间Vl[i] 是在保证汇点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]是在不会引起时间延误的前提下，该活动允许的最迟开始时间。 2018/12/9

109 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]。 2018/12/9

110 其中, S2是所有指向顶点Vi 的有向边< Vj , Vi >的集合。 从Vl[n-1] = Ve[n-1]开始，反向递推
< Vj, Vi >  S2, i = 1, 2, , n-1 其中, S2是所有指向顶点Vi 的有向边< Vj , Vi >的集合。 从Vl[n-1] = Ve[n-1]开始，反向递推 < Vi, Vj >  S1, i = n-2, n-3, , 0 其中, S1是所有从顶点Vi 发出的有向边< Vi , Vj >的集合。 这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。 2018/12/9

111 l[k] = Vl[j] - dur(<Vi , Vj >)；k = 1, 2, …, e。这样就得到计算关键路径的算法。
设活动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时按逆拓扑有序的顺序计算。 2018/12/9

112 利用关键路径法求AOE网的各关键活动 void CriticalPath (ALGraph G) { int i, j, k, e, l;
int *Ve,*Vl; ArcNode *p; Ve = new int[G.vexnum]; Vl = new int[G.vexnum]; for ( i = 0; i < G.vexnum; i++ ) Ve[i] = 0; for ( i = 0; i < G.vexnum; i++ ) { ArcNode *p = G.vertices[i].firstarc; while ( p != NULL ) { k = p->adjvex; if (Ve[i] + p->info > Ve[k]) Ve[k] = Ve[i] + p->info; p = p->nextarc; } 2018/12/9

113 for ( i = 0; i < G.vexnum; i++ )
Vl[i] = Ve[G.vexnum-1]; for ( i = G.vexnum-2; i; i-- ) { p = G.vertices[i].firstarc; while ( p != NULL ) { k = p->adjvex; if ( Vl[k] - p->info < Vl[i]) Vl[i] = Vl[k] - p->info; p = p->nextarc; } 2018/12/9

114 for ( i = 0; i < G.vexnum; i++ ) {
p = G.vertices[i].firstarc; while ( p != NULL ) { k = p->adjvex; e = Ve[i]; l = Vl[k] - p->info; char tag= (e = = l) ? '*' : ' '; printf("(%c,%c),e=%d,l=%d,%c\n",G.vertices[i].data,G.vertices[k].data,e,l,tag); p = p->nextarc; } 在拓扑排序求Ve[i]和逆拓扑有序求Vl[i]时, 所需时间为O(n+e), 求各个活动的e[k]和l[k]时所需时间为O(e), 总 共花费时间仍然是O(n+e)。 2018/12/9

115 【例7-4】图7-29是一个具有8个活动和6个事件的AOE网，试求其关键路径。
【解】由ve (i)和vl (i)的递推公式，依次求出所有事件的最早发生时间ve (i)和最迟发生时间vl (i)，如下： 图7-29 AOE网 2018/12/9

116 求出所有活动的最早开始时间e (i)、最迟开始时间l (i)以及d (i)=l (i)-e (i)，如下：
2018/12/9

117 从以上计算得出，图7-29中AOE网的关键活动为a2，a5，a7，这些活动构成了关键路径，如图7-30所示：
2018/12/9

118 本章小结 图是一种非线性数据结构。本章介绍有关图的基本概念，如顶点和边/弧、无向图和有向图，完全图、网、顶点的度、路径、回路、子图、图的连通性等。图主要具有邻接矩阵、邻接表、十字链表和邻接多重表等存储结构，用以表示图中的顶点信息、边的信息以及顶点与边的关系信息。图的遍历是图的一种重要运算，是从图的某一顶点出发，访遍图中每个顶点，且每个顶点仅访问一次，图的遍历顺序主要有深度优先搜索和广度优先搜索。最后讨论了求最小生成树的两种算法、求解最短路径的两类算法、拓扑排序和关键路径等常用算法。 2018/12/9