第9章 图 图的基本概念 图的存储结构 图的实现 图的遍历 最小生成树 最短路径 拓扑排序 关键路径 主要知识点

9.1 图 1.图的基本概念 图是由顶点集合及顶点间的关系集合组成的一种数据结构。图G的定义是： G =（V，E） 其中，V = {x|x∈某个数据元素集合} E ={(x，y)|x，y∈V} 或 E = {＜x， y＞|x，y∈V并且Path(x， y)} 其中，（x，y）表示从 x到 y的一条双向通路，即（x，y）是无方向的；Path（x，y）表示从 x到 y的一条单向通路，即Path（x，y）是有方向的。 问题：图的特点

图有许多复杂结构，本课程只讨论最基本的图，因此，本章讨论的图中不包括从自身到自身的边存在的图，以及带自身环的图

基本术语： （1）顶点和边：图中的结点一般称作顶点，图中的第i个顶点记做vi。两个顶点vi和vj相关联称作顶点vi和vj之间有一条边，图中的第k条边记做ek，ek =（vi, vj）或＜vi, vj＞。 （2）有向图和无向图：在有向图中，顶点对＜x, y＞是有序的，顶点对＜x, y＞称为从顶点x到顶点y的一条有向边，有向图中的边也称作弧；在无向图中，顶点对（x, y）是无序的，顶点对（x, y）称为与顶点x和顶点y相关联的一条边。 （3）完全图：在有n个顶点的无向图中，若有n(n-1)/2条边，即任意两个顶点之间有且只有一条边，则称此图为无向完全图；在有n个顶点的有向图中，若有n(n-1)条边，即任意两个顶点之间有且只有方向相反的两条边，则称此图为有向完全图。

1 3 2 4 5 6 (a)无向完全图 (b)无向图 (c)有向图 (d)有向完全图 （4）邻接顶点：在无向图G中，若（u,v）是E(G)中的一条边，则称u和v互为邻接顶点，并称边（u,v）依附于顶点u和v；在有向图G中，若＜u,v＞是E(G)中的一条边，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称边＜u,v＞和顶点u和顶点v相关联。 。

（5）顶点的度：顶点v的度是与它相关联的边的条数，记作TD(v)。顶点的度 = 入度 + 出度。 （6）路径：在图G=(V,E)中，若从顶点vi出发有一组边使可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径 （7）权：有些图的边附带有数据信息，这些附带的数据信息称为权。带权的图也称作网络或网。 （8）路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。 （9）子图：设有图G1={V1,E1}和图G2={V2,E2}，若V1V2，且E1 E2，则称图G2是图G1的子图。

2 1 3 5 4 6 7 8 9 10 12 15 16 B A C D E 60 30 45 75 80 40 35 施工进度图 交通网络图

（10）连通图和强连通图：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶点都是连通的，则称该图是连通图。 在有向图中，若对于任意一对顶点vi和顶点vj（vi≠vj）都存在路径，则称图G是强连通图。 （11）生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。 生成树一般是对无向图来讨论。 （12）简单路径和回路：若路径上各顶点v1,v2,…,vm,互不重复，则称这样的路径为简单路径；若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环 。

2.图的抽象数据类型 数据集合：由一组顶点集合{vi}和一组边{ej}集合组成。当为带权图时每条边上权wj还构成权集合{wj}。 操作集合： （1）初始化Initiate(G, n) （2）插入顶点 InsertVertex(G, vertex) （3）插入边InsertEdgeG, v1, v2, weight) （4）删除边DeleteEdge(G, v1, v2) （5）删除顶点DeleteVertex(G, vertex) （6）第一个邻接顶点GetFirstVex(G, v) （7）下一个邻接顶点GetNextVex(G, int v1, v2) （8）遍历DepthFirstSearch(G)

9.2 图的存储结构 1.图的邻接矩阵存储结构 图的存储结构主要有邻接矩阵和邻接表两种。 假设图G=(V,E)有n个顶点，即V={v0,v1,…,vn-1}，E可用如下形式的矩阵A描述，对于A中的每一个元素aij，满足： 由于矩阵A中的元素aij表示了顶点vi和顶点vj之间边的关系，或者说，A中的元素aij表示了顶点vi和顶点vj（0≤j≤n-1）的邻接关系，所以矩阵A称作邻接矩阵。

无向图的邻接矩阵一定是对称矩阵 有向图的邻接矩阵一般是非对称矩阵 其中V表示了图的顶点集合，A表示了图的邻接矩阵

带权图及其邻接矩阵 其中V表示了图的顶点集合，A表示了图的邻接矩阵。对于带权图，邻接矩阵第i行中所有0<aij<∞的元素个数等于第i个顶点的出度，邻接矩阵第j列中所有0<aij<∞的元素个数等于第j个顶点的入度。

2.图的邻接表存储结构 当图的边数少于顶点个数且顶点个数值较大时，图的邻接n×n矩阵的存储问题就变成了稀疏矩阵的存储问题，此时，邻接表就是一种较邻接矩阵更为有效的存储结构。 B A D C E ( a ) 1 2 3 4 d t s o r c e j n x ∧ b

数组的data域存储图的顶点信息，sorce域存储该顶点在数组中的下标序号，adj域为该顶点的邻接顶点单链表的头指针。第i行单链表中的dest域存储所有起始顶点为vi的邻接顶点vj在数组中的下标序号，next域为单链表中下一个邻接顶点的指针域。如果是带权图，单链表中需再增加cost域，用来存储边<vi,vj>的权值wij。 问题：邻接表存储结构和数组一章中的什么存储结构类似？

9.3 图的实现 1.邻接矩阵存储结构下图操作的实现 #include "SeqList.h" typedef struct {   typedef struct { SeqList Vertices; int edge[MaxVertices][MaxVertices]; int numOfEdges; }AdjMGraph;

void Initiate(AdjMGraph *G, int n) { int i, j;  for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(i == j) G->edge[i][j] = 0; else G->edge[i][j] = MaxWeight; }   G->numOfEdges = 0; /*边的条数置为0*/ ListInitiate(&G->Vertices); /*顺序表初始化*/

void InsertVertex(AdjMGraph *G, DataType vertex) { ListInsert(&G->Vertices, G->Vertices.size, vertex); }  void InsertEdge(AdjMGraph *G, int v1, int v2, int weight) if(v1 < 0 || v1 > G->Vertices.size || v2 < 0 || v2 > G->Vertices.size) { printf("参数v1或v2越界出错!\n"); exit(1);   G->edge[v1][v2] = weight; G->numOfEdges++;

void DeleteEdge(AdjMWGraph *G, int v1, int v2) { if(v1 < 0 || v1 > G->Vertices.size || v2 < 0 || v2 > G->Vertices.size || v1 == v2) { printf("参数v1或v2越界出错!\n"); exit(1); }   if(G->edge[v1][v2] == MaxWeight || v1 == v2) { printf("该边不存在!\n"); exit(0); G->edge[v1][v2] = MaxWeight; G->numOfEdges--;

int GetFirstVex(AdjMGraph G, int v) { int col;   if(v < 0 || v > G.Vertices.size) { printf("参数v1越界出错!\n"); exit(1); } for(col = 0; col <= G.Vertices.size; col++) if(G.edge[v][col] > 0 &&G.edge[v][col] < MaxWeight) return col; return -1;

int GetNextVex(AdjMGraph G, int v1, int v2) { int col;   if(v1 < 0 || v1 > G.Vertices.size || v2 < 0 ||v2 > G.Vertices.size) { printf("参数v1或v2越界出错!\n"); exit(1); } for(col = v2+1; col <= G.Vertices.size; col++) if(G.edge[v1][col] > 0 && G.edge[v1][col] < MaxWeight) return col; return -1;

2.邻接矩阵图操作的测试 例9-1 以下图所示的带权有向图为例编写测试邻接矩阵图的程序。 A B C D E 10 40 30 50 20

图的创建函数设计如下： typedef struct { int row; //行下标 int col; //列下标 int weight; //权值 } RowColWeight;

void CreatGraph(AdjMGraph void CreatGraph(AdjMGraph *G, DataType V[],int n,RowColWeight E[],int e) /*在图G中插入n个顶点信息V和e条边信息E*/ { int i, k;   Initiate(G, n); /*顶点顺序表初始化*/ for(i = 0; i < n; i++) InsertVertex(G, V[i]); /*顶点插入*/ for(k = 0; k < e; k++) InsertEdge(G, E[k].row, E[k].col, E[k].weight); /*边插入*/ }

测试程序设计如下： #include <stdio.h> #include <stdlib.h>   typedef char DataType; #define MaxSize 100 #define MaxVertices 10 #define MaxEdges 100 #define MaxWeight 10000 #include "AdjMGraph.h" #include "AdjMGraphCreate.h"

void main(void) { AdjMWGraph g1; DataType a[] = {'A','B','C','D','E'}; RowColWeight rcw[] = {{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}}; int n = 5, e = 5; int i, j; CreatGraph(&g1, a, n, rcw, e); DeleteEdge(&g1, 0, 4); printf("顶点集合为："); for(i = 0; i < g1.Vertices.size; i++) printf("%c ", g1.Vertices.list[i]); printf("\n"); printf("权值集合为：\n"); { for(j = 0; j < g1.Vertices.size; j++) printf("%5d ", g1.edge[i][j]); }

2.邻接表存储结构下图操作的实现 邻接表的存储结构 typedef struct Node { int dest; /*邻接边的弧头顶点序号*/ struct Node *next; } Edge; /*邻接边单链表的结点结构体*/   typedef struct DataType data; /*顶点数据元素*/ int sorce; /*邻接边的弧尾顶点序号*/ Edge *adj; /*邻接边的头指针*/ } AdjLHeight; /*数组的数据元素类型结构体*/

typedef struct { AdjLHeight a[MaxVertices]; /*邻接表数组*/ int numOfVerts; /*顶点个数*/ int numOfEdges; /*边个数*/ } AdjLGraph; /*邻接表结构体*/ 讨论：图操作的实现方法

9.4 图的遍历 1.图的深度和广度优先遍历算法 图的遍历是访问图中的每一个顶点且每个顶点只被访问一次。算法设计需要考虑三个问题： （1）算法的参数要指定访问的第一个顶点； （2）要考虑遍历路径可能出现的死循环问题； （3）要使一个顶点的所有邻接顶点按照某种次序被访问。

一、 图的深度优先遍历算法 图的深度优先遍历算法是遍历时深度优先的算法，是一个递归算法。连通图的深度优先遍历递归算法为： （1）访问顶点v并标记顶点v为已访问； （2）查找顶点v的第一个邻接顶点w； （3）若顶点v的邻接顶点w存在，则继续执行，否则算法结束； （4）若顶点w尚未被访问则深度优先搜索递归访问顶点w； （5）查找顶点v的w邻接顶点的下一个邻接顶点w，转到步骤（3）。 对于例9-1所示的有向图，深度优先遍历访问顶点次序为： A B D C E

二、 图的广度优先遍历算法 连通图的广度优先遍历算法为： （1）访问初始顶点v并标记顶点v为已访问； （2）顶点v入队列； （3）当队列非空时则继续执行，否则算法结束； （4）出队列取得队头顶点u； （5）查找顶点u的第一个邻接顶点w； （6）若顶点u的邻接顶点w不存在，则转到步骤（3），否则循环执行： （6.1）若顶点w尚未被访问则访问顶点w并标记顶点w为已访问； （6.2）顶点w入队列； （6.3）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤（6）。

图的广度优先遍历算法是一个分层搜索的过程，需要一个队列以保持访问过的顶点的顺序，以便按访问过的顶点的顺序来访问这些顶点的邻接顶点。 对于例9-1所示的有向图，广度优先遍历访问顶点次序为： A B E D C 问题：连通图的（深度、广度）遍历和生成树的关系？

三、非连通图的遍历 对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。只能访问和初始顶点连通的所有顶点。 但是，每一个顶点都作为一次初始顶点进行深度优先遍历或广度优先遍历，并根据顶点的访问标记来判断是否需要访问该顶点，就一定可以访问非连通图中的所有顶点。

2.图的深度和广度优先遍历函数实现 一、 深度优先遍历 void DepthFSearch(AdjMWGraph G, int v, int visited[], void Visit(DataType item)) { int w; Visit(G.Vertices.list[v]); visited[v] = 1;   w = GetFirstVex(G, v); while(w != -1) { if(! visited[w]) DepthFSearch(G, w, visited, Visit); w = GetNextVex(G, v, w); }

二、非连通图的深度优先遍历 void DepthFirstSearch(AdjMWGraph G, void Visit(DataType item)) { int i; int *visited = (int *)malloc(sizeof(int)*G.Vertices.size);   for(i = 0; i < G.Vertices.size; i++) visited[i] = 0; if(! visited[i]) DepthFSearch(G, i, visited, Visit); free(visited); }

三、 广度优先遍历 while(w != -1) #include "SeqQueue.h" void BroadFSearch(AdjMWGraph G, int v, int visited[], void Visit(DataType item)) { DataType u, w; SeqCQueue queue;   Visit(G.Vertices.list[v]); visited[v] = 1;   QueueInitiate(&queue); QueueAppend(&queue, v); while(QueueNotEmpty(queue)) { QueueDelete(&queue, &u); w = GetFirstVex(G, u); while(w != -1) { if(!visited[w]) { Visit(G.Vertices.list[w]); visited[w] = 1; QueueAppend(&queue, w); } w = GetNextVex(G, u, w); } }

四、非连通图的广度优先遍历 void BroadFirstSearch(AdjMWGraph G, void Visit(DataType item)) { int i; int *visited = (int *)malloc(sizeof(int)*G.Vertices.size);   for(i = 0; i < G.Vertices.size; i++) visited[i] = 0; if(!visited[i]) BroadFSearch(G, i, visited, Visit); free(visited); }

例9-2 以图9-8所示的带权有向图为例，编写测试上述图的深度优先和广度优先遍历函数的程序。 五、程序举例 例9-2 以图9-8所示的带权有向图为例，编写测试上述图的深度优先和广度优先遍历函数的程序。 #include <stdio.h> #include <stdlib.h> #include <malloc.h>   typedef char DataType; #define MaxSize 100 #define MaxVertices 10 #define MaxEdges 100

#define MaxWeight 10000 #define MaxQueueSize 100 #include "AdjMGraph.h" #include "AdjMGraphCreate.h" #include "AdjMGraphTraverse.h"   void Visit(DataType item) { printf("%c ", item); }

void main(void) { AdjMWGraph g1; DataType a[] = {'A','B','C','D','E'}; RowColWeight rcw[] = {{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}}; int n = 5, e = 5; CreatGraph(&g1, a, n, rcw, e); printf("深度优先搜索序列为："); DepthFirstSearch(g1, Visit); printf("\n广度优先搜索序列为："); BroadFirstSearch(g1, Visit); }

9.5 最小生成树 1.基本概念 一个有n个顶点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个顶点，并且有保持图连通的最少的边。 （1）若在生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义； （2）若在生成树中增加一条边就会使该生成树中因存在回路而不再满足生成树的定义； （3）一个连通图的生成树可能有许多； （4）有n个顶点的无向连通图，无论它的生成树的形状如何，一定有且只有n-1条边。

1 V 2 3 4 5 6 (a) (b) (c) 无向图和它的不同的生成树

如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小代价生成树，简称最小生成树。 构造有n个顶点的无向连通带权图的最小生成树必须满足以下三条： （1）构造的最小生成树必须包括n个顶点； （2）构造的最小生成树中有且只有n-1条边； （3）构造的最小生成树中权值总和最小。 典型的构造方法有两种，一种称作普里姆（Prim）算法，另一种称作克鲁斯卡尔（Kruskal）算法。

2.普里姆算法 一、算法思想 假设G=(V,E)为一个带权图，其中V为带权图中顶点的集合，E为带权图中边的权值集合。设置两个新的集合U和T，其中U用于存放带权图G的最小生成树的顶点的集合，T用于存放带权图G的最小生成树的权值的集合。 普里姆算法思想是：令集合U的初值为U={u0}（即假设构造最小生成树时从顶点u0开始），集合T的初值为T={}。从所有顶点u∈U和顶点v∈V-U的带权边中选出具有最小权值的边(u,v)，将顶点v加入集合U中，将边(u,v) 加入集合T中。如此不断重复，当U=V时则最小生成树构造完毕。此时集合U中存放着最小生成树顶点的集合，集合T中存放着最小生成树边的权值集合。

图9-10 普里姆算法构造最小生成树的过程 A C B G E F D 50 60 45 52 42 30 65 40 70 (a) (b) (h) 图9-10 普里姆算法构造最小生成树的过程

其中，vertex域用来保存最小生成树每条边的弧头顶点数据，weight域用来保存最小生成树的相应边的权值。 二、普里姆函数设计 普里姆函数应有两个参数，一个参数是图G，另一个参数是通过函数得到的最小生成树的顶点数据和相应顶点的边的权值数据closeVertex。其数据类型定义为如下结构体： typeder struct { VerT vertex; int weight; } MinSpanTree; 其中，vertex域用来保存最小生成树每条边的弧头顶点数据，weight域用来保存最小生成树的相应边的权值。

普里姆函数设计： void Prim(AdjMWGraph G, MinSpanTree closeVertex[]) { VerT x; int n = G.Vertices.size, minCost; int *lowCost = (int *)malloc(sizeof(int)*n); int i, j, k;   for(i = 1; i < n; i ++) lowCost[i] = G.edge[0][i]; /*从顶点0出发构造最小生成树*/ ListGet(G.Vertices, 0, &x); closeVertex[0].vertex = x; lowCost[0] = -1; for(i = 1; i < n; i++)

{ /*寻找当前最小权值的边所对应的弧头顶点k*/ minCost = MaxWeight; for(j = 1; j < n; j++) { if(lowCost[j] < minCost && lowCost[j] > 0) { minCost = lowCost[j]; k = j; } }  ListGet(G.Vertices, k, &x); closeVertex[i].vertex = x; closeVertex[i].weight = minCost; lowCost[k] = -1; { if(G.edge[k][j] < lowCost[j]) lowCost[j] = G.edge[k][j];

设计说明： （1）函数中定义一个临时数组lowCost，数组元素lowCost[v]中保存了集合U中顶点ui与集合V-U中顶点vj的所有边中当前具有最小权值的边(u,v)。 （2）集合U的初值为U={序号为0的顶点}。lowCost的初始值为邻接矩阵数组中第0行的值，这样初始时lowCost中就存放了从集合U中顶点0到集合V-U中各个顶点的权值。 （3）每次从lowCost中寻找具有最小权值的边，根据lowCost的定义，这样的边其弧头顶点必然为集合U中的顶点，其弧尾顶点必然为集合V-U中的顶点。当选到一条这样的边(u,v)，就保存其顶点数据和权值数据到参数closeVertex中，并将lowCost[v]置为-1，表示顶点v加入了集合U中。

（5）以图9-10（a）所示的无向连通带权图为例，调用普里姆函数时数组lowCost的动态变化过程如图示。 （4）当顶点v从集合V-U加入到集合U后，若存在一条边(u,v)，u是集合U的顶点，v是集合V-U的顶点，且边(u,v)较原先lowCost[v]的代价更小，则用这样的权值修改原先lowCost[v]中的相应权值。 （5）以图9-10（a）所示的无向连通带权图为例，调用普里姆函数时数组lowCost的动态变化过程如图示。 - 1 5 2 3 4 6 l o w C s t ∞ 7 ( a ) b c d e f g

函数主要是一个两重循环，其中每一重循环的次数均为顶点个数n，所以该算法的时间复杂度为O(n2)。 三、测试程序 例9-3 以图9-10（a）所示的无向连通带权图为例设计测试上述Prim函数的程序。

3.克鲁斯卡尔算法 克鲁斯卡尔算法是一种按照带权图中边的权值的递增顺序构造最小生成树的方法。设无向连通带权图G=(V,E)，其中V为顶点的集合，E为边的集合。 克鲁斯卡尔算法思想是：设带权图G的最小生成树T由顶点集合和边的集合构成，其初值为T=(V,{})，即初始时最小生成树T只由带权图G中的顶点集合组成，各顶点之间没有一条边。这样，最小生成树T中的各个顶点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图G中的边集合E中的各条边，①若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边加入到最小生成树T，同时把两个连通分量连接为一个连通分量；②若被考察的边的两个顶点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，T中的该连通分量即为带权图G的一棵最小生成树

A C B G E F D 30 40 42 45 50 (a) (b) (c) (d) (e) (f) 克鲁斯卡尔算法构造最小生成树的过程

9.6 最短路径 1.基本概念 路径长度:一条路径上所经过的边的数目 带权路径长度:路径上所经过边的权值之和 最短路径:(带权)路径长度(值)最小的那条路径 图9-13 （a）有向带权图；（b）邻接矩阵

2.从一个顶点到其余各顶点的最短路径 一、狄克斯特拉算法思想 按路径长度递增的顺序逐步产生最短路径。 狄克斯特拉算法的思想是：设置两个顶点的集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点，设为v0，然后从集合T中选择到源点v0路径长度最短的顶点u加入到集合S中，集合S中每加入一个新的顶点u都要修改源点v0到集合T中剩余顶点的当前最短路径长度值，集合T中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过顶点u到达该顶点的路径长度中的较小者。此过程不断重复，直到集合T中的顶点全部加入到集合S中为止。

狄克斯特拉算法求从顶点A到其余各顶点最短路径的过程

二、狄克斯特拉函数设计 参数设计： 函数共有4个参数，其中2个为输入参数，分别为带权图G和源点序号v0；2个为输出参数，分别为distance[]和path[]，distance[]用来存放得到的从源点v0到其余各顶点的最短距离数值，path[]用来存放得到的从源点v0到其余各顶点的最短路径上到达目标顶点的前一顶点下标。

狄克斯特拉函数设计： void Dijkstra(AdjMGraph G, int v0, int distance[], int path[]) /*带权图G从下标v0顶点到其它顶点的最短距离distance*/ /*和最短路径下标path*/ { int n = G.Vertices.size; int *s = (int *)malloc(sizeof(int)*n); int minDis, i, j, u; /*初始化*/ for(i = 0; i < n; i ++) { distance[i] = G.edge[v0][i]; s[i] = 0; if(i != v0 && distance[i] < MaxWeight) path[i] = v0; else path[i] = -1; } s[v0] = 1;

/*在还未找到最短路径的顶点集中选有最短距离的顶点u*/ for(i = 1; i < n; i ++) { minDis = MaxWeight; for(j = 0;j < n;j ++) if(s[j] == 0 && distance[j] < minDis) { u = j; minDis = distance[j]; } /*当已不再存在路径时算法结束*/ if(minDis == MaxWeight) return; s[u] = 1; /*标记顶点u已从集合T加入到集合S中*/ /*修改从v0到其它顶点的最短距离和最短路径*/ for(j = 0; j < n; j++) if(s[j] == 0 && G.edge[u][j] < MaxWeight && distance[u] + G.edge[u][j] < distance[j]) { distance[j] = distance[u] + G.edge[u][j]; path[j] = u; }

三、测试程序 例9-4：以图9-13的有向带权图为例设计测试上述Dijkstra函数的程序。

3.每对顶点之间的最短路径 带权有向图，每对顶点之间的最短路径可通过调用狄克斯特拉算法实现。具体方法是：每次以不同的顶点作为源点，调用狄克斯特拉算法求出从该源点到其余顶点的最短路径。重复n次就可求出每对顶点之间的最短路径。由于狄克斯特拉算法的时间复杂度为O(n2)，所以这种算法的时间复杂度为O(n3)。 弗洛伊德算法的思想是：设矩阵cost用来存放带权有向图G的权值，即矩阵元素cost[i][j]中存放着下标为i的顶点到下标为j的顶点之间的权值，可以通过递推构造一个矩阵序列A0,A1,A2,……,AN来求每对顶点之间的最短路径。其中，Ak[i][j]（0≤k≤n）表示从顶点vi到顶点vj的路径上所经过的顶点下标不大于k的最短路径长度。初始时有，A0[i][j]=cost[i][j]。

当已经求出Ak,要递推求解Ak+1时，有： 一种情况是该路径不经过下标为k+1的顶点，此时该路径长度与从顶点vi到顶点vj的路径上所经过的顶点下标不大于k的最短路径长度相同； 另一种情况是该路径经过下标为k+1的顶点，此时该路径可分为两段，一段是从顶点vi到顶点vk+1的最短路径，另一段是从顶点vk+1到顶点vj的最短路径，此时的最短路径长度等于这两段最短路径长度之和。

这两种情况中的路径长度较小者，就是要求的从顶点vi到顶点vj的路径上所经过的顶点下标不大于k+1的最短路径长度。 用公式描述为： A0[i][j]=cost[i][j] Ak+1[i][j]=min{Ak[i][j], Ak[i][k+1]+Ak[k+1][j]} （0≤k≤n-1）

9.7 拓扑排序 1．偏序关系和全序关系 拓扑排序就是要由某个集合上的偏序关系得到该集合上的全序关系。 若集合X上的关系R是自反的、反对称的和传递的，则称关系R是集合X上的偏序关系（或称半序关系）。 设关系R为定义在集合X上的二元关系，若对于每一个x∈X，都有(x,x)∈R，则称R是自反的。 设关系R为定义在集合X上的二元关系，如果对于任意的x,y,z∈X，若当(x,y)∈R且(y,z)∈R时，有(x,z)∈R，则称关系R是传递的。

设关系R为定义在集合X上的二元关系，若对于所有的x,y∈X，若当(x,y)∈R且(y,x)∈R时，有x=y，则称关系R是反对称的。 例如，设X是实数集合，R为小于等于关系，即R={(x,y)|x∈X∧y∈X∧x≤y}，由于当x≤y且y≤x时有x＝y，因此，关系R是反对称关系。另外，相等关系也是反对称关系。 设关系R是集合X上的偏序关系，若对所有的x,y∈X，有(x,y)∈R或(y,x)∈R，则称关系R是集合X上的全序关系。 偏序关系的实质是在集合X的元素之间建立层次结构。这种层次结构是依赖于偏序关系的可比性建立起来的。但是，偏序关系不能保证集合X中的任意两个元素之间都能比较。而全序关系可以保证集合中的任意两个元素之间都可以比较。

一个有向图可以表示一个施工流程图，或产品生产流程图，或数据流图等。设图中每一条有向边表示两个子工程之间的先后次序关系。 2．有向图在实际问题中的应用 一个有向图可以表示一个施工流程图，或产品生产流程图，或数据流图等。设图中每一条有向边表示两个子工程之间的先后次序关系。 若以有向图中的顶点来表示活动，以有向边来表示活动之间的先后次序关系，则这样的有向图称为顶点表示活动的网 (Activity On Vertex Network)，简称AOV网。 AOV网表示的有向图要解决的一个问题，就是如何得到一个完成整个工程项目的各子工程的序列。这就是有向图的拓扑排序问题。 3 9 2 4 7 5 6 8 1

3．拓扑排序在有向图中的应用 如果把有向图中的所有顶点看作集合中的元素，把有向图中的有向边看作集合中的关系（通常情况下是先于关系），则可以证明，如果有向图中不存在回路，则对应的集合上的关系满足偏序关系。因此，如何得到AOV网表示的施工流程图的一个完成整个工程项目的各子工程的序列问题，就是一个AOV网表示的有向图的拓扑排序问题。 对一个有向图进行拓扑排序，就是将有向图中的所有顶点排成一个线性序列，使得对有向图中任意一对顶点u和v，若<u,v>是有向图中的一条有向边，则顶点u在该线性序列中出现在顶点v之前。这样的线性序列称为满足拓扑次序的序列，简称为拓扑序列。对有向图建立拓扑序列的过程称为对有向图的拓扑排序。

对于AOV网的拓扑排序就是将AOV网中的所有顶点排成一个线性序列。 拓扑排序实际上就是要由某个集合上的一个偏序关系得到该集合上的一个全序关系。 例如， 下图所示的两个有向图，由于左图中顶点B无法和顶点C比较，所以左图表示的是偏序关系。如果在左图中人为添加一条顶点B到顶点C的有向边，即右图，则右图表示的就是全序关系。 如果我们对一个有向图进行拓扑排序，得到了该有向图中所有顶点的一个线性序列，因线性序列中所有顶点均可以比较，也就相当于通过人为添加一些有向边，把有向图对应的偏序关系变成了全序关系。

4．有向图的拓扑排序算法 有向图的拓扑排序算法： (1) 在有向图中选择一个没有前驱的顶点，并把它输出； (2) 从有向图中删去该顶点以及与它相关的有向边。 重复上述两个步骤，直到所有顶点都输出，或者剩余的顶点中找不到没有前驱的顶点。在前一种情况下，顶点的输出序列就是一个拓扑序列；后一种情况则说明有向图中存在回路，如果有向图中存在回路，则该有向图一定无法得到一个拓扑序列。

上述算法仅能得到有向图的一个拓扑序列。改进上述算法，可以得到有向图的所有拓扑序列。 如果一个有向图存在一个拓扑序列，通常表示该有向图对应的某个施工流程图的一种施工方案切实可行；而如果一个有向图不存在一个拓扑序列，则说明该有向图对应的某个施工流程图存在设计问题，不存在切实可行的任何一种施工方案。

例：对于如下图所示的AOV网，写出利用拓扑排序算法得到的一个拓扑序列。 解：根据拓扑排序算法，得到的一个拓扑序列为0,1,7,2,4,8,5,9,3,6。 3 9 图9-17 AOV网 2 4 7 5 6 8 1

9.8关键路径 1．工程管理中的问题 在工程规划中，经常需要考虑这样的问题，完成整个工程最短需要多长时间，工程中的哪些工序是一些重要的工序，缩短这些重要工序的时间可以缩短整个工程的工期。在生产管理中，也存在这样的问题，一件产品有多道生产工序，减少哪道工序所用的时间可以缩短产品的生产周期。诸如此类的问题，可以使用有向图进行描述和分析。下面我们首先给出描述这类问题的有关概念，然后讨论解决的方法。

2．AOE网对工程管理问题的表示 在有向图中，如果顶点表示事件，有向边表示活动，有向边上的权值表示活动持续的时间，这样的有向图称为边表示活动的网(Activity On Edge)，简称AOE网。 对于AOE网，需要研究的问题是： （1）完成整个工程需要多少时间？ （2）哪些活动是影响工程进度的关键？

a3=3 a7=5 a11=8 v1 v3 v5 v8 a1=5 a8=4 a12=2 a15=3 a6=4 a4=6 v0 v6 a13=8 a2=7 a9=6 v2 v4 v9 v7 a5=3 a10=5 a14=9 图9-19 AOE网

基本概念： 路径长度：AOE网的一条路径上所有活动的总和称为该路径的长度。 关键路径：在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。 关键活动：关键路径上的活动称为关键活动。 显然，完成整个工程的最短时间就是AOE网中关键路径的长度，也就是AOE网中各关键活动所持续时间的总和。 例：找出前图所示的AOE网中的关键路径。 解：在AOE网中，从源点v0到汇点v9共有15条路径，分别计算这15条路径的长度，得到最大路径长度为31。最大路径长度对应的关键路径为(v0,v2,v3,v4,v6,v9) 和(v0,v2,v3,v4,v7,v9)。

3．几个参数的定义 活动的持续时间dut(<j, k>)：对于有向边<j, k>代表的活动，dut(<j, k>)是该有向边<j, k>的权值。 事件可能的最早开始时间υe(k)：对于顶点υk代表的事件，υe(k)是从源点到该顶点的最大路径长度。在一个有n+1个事件的AOE网中, 源点υ0的最早开始时间υe(0)等于0。事件υk（k=1,2,3,…,n）可能的最早开始时间υe(k)可用递推公式表示为： υe(k)= 0 顶点k=0为源点 Max{ υe(j)+dut(<j,k>) }| <j,k>为网中的有向边 } 其他顶点

事件允许的最晚发生时间υl(k)：对于顶点υk代表的事件，υl(k)是在保证按时完成整个工程的前提下，该事件最晚必须发生的时间。在一个有n+1个事件的AOE网中,汇点υn的最晚发生时间υl(n)为工程最后的完成时间，即υl(n)等于υe(n)。所以，事件υk（k=0,1,2,…,n-1）的最迟发生时间υl(k)可用递推公式表示为： υl(k)= υe(n) 顶点k=n为汇点 Min{ υl(j)- dut(<k, j >) } 其他顶点 <k, j >为网中的有向边

活动可能的最早开始时间e(i)：对于有向边ai代表的活动，e(i)是该活动的弧尾事件可能的最早发生时间。假设活动ai代表的是有向边<j,k>，即ai是关联事件j和事件k的的活动，则e(i) =υe(j)。 活动允许的最晚开始时间l(i)：对于有向边ai代表的活动，l(i)是该活动的弧头事件允许的最晚发生时间减去该活动持续的时间。l(i)是在不推迟整个工程完成的前提下，活动ai必须开始的时间。假设活动ai代表的是有向边<j,k>，即ai是关联事件j和事件k的的活动，则l(i) = υl(k) - dut(<j, k>)。 这样，每个活动允许的时间余量就是l(i) - e(i)。而关键活动就是l(i) - e(i) = 0的那些活动，即可能的最早开始时间e(i)等于允许的最晚开始时间l(i)的那些活动就是关键活动。

4．寻找关键活动的算法 求AOE网中关键活动的算法步骤为： （1）建立包含n+1个顶点、e条有向边的AOE网。其中，顶点v0为源点，顶点vn为汇点； （2）根据有向图的拓扑排序算法，求出AOE网的拓扑序列。如果AOE网中存在环，拓扑序列不存在，则无法得到AOE网的关键活动，算法失败退出； （3）从源点v0开始，令源点v0的最早开始时间ve[0]=0，按拓扑序列求其余各顶点k(k=1,2,3,…,n)的最早开始时间ve[k]； （4）从汇点vn开始，令汇点vn的最晚发生时间vl[n]=ve[n]，按逆拓扑序列求其余各顶点k(k=n-1,n-2,…,2,1,0)的最晚发生时间vl[k]； （5）计算每个活动的最早开始时间e[k] (k=1,2,3,…,e)； （6）计算每个活动的最晚开始时间l[k] (k=1,2,3,…,e)； （7）找出所有e[k]= l[k]的活动k，这些活动即为AOE网的关键活动。

5．AOE网的应用 实践证明，用AOE网来估算工程的完成时间是非常有用的。另外，根据前面的讨论可知，AOE网中的关键活动的持续时间是限制整个工程进度的主要因素，要缩短整个工程的时间进度，就要力争缩短关键活动的持续时间。

（1）计算各个事件vk的最早开始时间υe(k) （2）给出整个工程最少需要的时间； （3）计算各个事件vk的最晚发生时间υl(k)； 例9-7 对于图9-19所示的AOE网，要求： （1）计算各个事件vk的最早开始时间υe(k) （2）给出整个工程最少需要的时间； （3）计算各个事件vk的最晚发生时间υl(k)； （4）计算各个活动ai的最早开始时间e(i)； （5）计算各个活动ai的最晚开始时间l(i)； （6）找出所有的关键活动和关键路径。 a9=6 a6=4 a2=7 a1=5 a3=3 a4=6 a5=3 a7=5 a8=4 a10=5 a11=8 a14=9 a12=2 a13=8 a15=3 v0 v3 v1 v4 v7 v6 v8 v5 v2 v9

计算过程： （1）从源点v0开始，令源点v0的最早开始时间ve[0]=0，按拓扑序列求其余各顶点k(k=1,2,3,…,n)的最早开始时间ve[k]； （2）从汇点vn开始，令汇点vn的最晚发生时间vl[n]=ve[n]，按逆拓扑序列求其余各顶点k(k=n-1,n-2,…,2,1,0)的最晚发生时间vl[k]； （3）计算每个活动的最早开始时间e[k] (k=1,2,3,…,e)； （4）计算每个活动的最晚开始时间l[k] (k=1,2,3,…,e)； （5）找出所有e[k]= l[k]的活动k，这些活动即为AOE网的关键活动。 所以，关键活动有a2,a4,a6,a9,a10,a13,a14。 从源点v0到汇点v9的只经过关键活动的路径就是关键路径。 所以，关键路径为(v0,v2,v3,v4,v6,v9) 和(v0,v2,v3,v4,v7,v9)。

作业 1) 习题9-1，9-2 ，9-3 ，9-11 2) 习题9-4 ，9-6 ，9-16 ，9-17 3) 习题9-5，9-15 4)举例说明拓扑排序的应用 叙述拓扑排序算法 阅读理解例9-7