数据结构图的算法的毕业论文

更新时间：2024-04-08 08:57:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

图

图形结构是一种比树形结构更复杂的非线性结构。树形结构中的结点之间具有明显的层次关系，且每一层上的结点只能和上一层中的一个结点相关，但可能和下一层的多个结点相关。在图形结构中，任意两个结点之间都可能相关，即结点与结点之间的邻接关系可以是任意的。因此，图形结构可用来描述更加复杂的对象。

1 图的基本概念和存储结构

1.1 图的定义

图（Graph）是由非空的顶点集合V与描述顶点之间关系——边（或者弧）的集合E组成，其形式化定义为：

G=(V, E)

如果图G中的每一条边都是没有方向的，则称G为无向图。无向图中边是图中顶点的无序偶对。无序偶对通常用圆括号“( )”表示。例如，顶点偶对(vi,vj)表示顶点vi和顶点vj相连的边，并且(vi,vj)与(vj,vi)表示同一条边。

如果图G中的每一条边都是有方向的，则称G为有向图。有向图中的边是图中顶点的有序偶对，有序偶对通常用尖括号“< >”表示。例如，顶点偶对表示从顶点vi指向顶点vj的一条有向边；其中，顶点vi称为有向边的起点，顶点vj称为有向边的终点。有向边也称为弧；对弧来说，vi为弧的起点，称为弧尾；vj为弧的终点，称为弧头。

图是一种复杂的数据结构，表现在不仅各顶点的度可以不同，而且顶点之间的逻辑关系也错综复杂。从图的定义可知：一个图的信息包括两个部分：图中顶点的信息以及描述顶点之间的关系——边或弧的信息。因此无论采取什么方法来建立图的存储结构，都要完整、准确地反映这两部分的信息。为适于用C语言描述，从本节起顶点序号由0开始，即图的顶点集的一般形式为：V={v0,v1,?,vn-1}。

下面介绍几种常用的图的存储结构。 1.2 邻接矩阵

所谓邻接矩阵存储结构，就是用一维数组存储图中顶点的信息，并用矩阵来表示图中各顶点之间的邻接关系。假定图G=(V, E)有n个顶点，即V={v0,v1,?,vn-1}，则表示G中各顶点相邻关系需用一个n×n的矩阵，且矩阵元素为：

A[i][j]= 1 若(vi,vj)或是E中的边

0 若(vi,vj)或不是E中的边若G是带权图（网），则邻接矩阵可定义为：

A[i][j]= wij 若(vi,vj)或是E中的边

0或∞ 若(vi,vj)或不是E中的边其中，wij表示(vi,vj)或上的权值；∞则为计算机上所允许的大于所有边上权值

的数值。无向图的邻接矩阵表示如图7-6所示。

图7-6 无向图及邻接矩阵表示

有向图的邻接矩阵表示如图7-7所示。

图7-7 有向图及邻接矩阵表示

带权图的邻接矩阵表示如图7-8所示。

图7-8 带权图及邻接矩阵表示

从图的邻接矩阵可以看出以下特点：

（1）无向图（包括带权图）的邻接矩阵一定是一个按对角线对称的对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。

（2）对于无向图，邻接矩阵的第i行或第i列的非零元素（或非∞元素）个数正好是第i个顶点的度D(vi)。

（3）对有向图，邻接矩阵的第i行非零元素（或非∞元素）的个数正好是第i个顶点的出度OD(vi)，第i列非零元素（或非∞元素）的个数正好是第i个顶点的入度ID(vi)。（4）用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中具体有多少条边，则必须按行、按列对每一个元素进行查找后方能确定，因此花费的时间代价较大，这也是用邻接矩阵存储图的局限性。

在采用邻接矩阵方式表示图时，除了用一个二维数组存储用于表示顶点相邻关系的

邻接矩阵之外，还需要用一个一维数组存储顶点信息。这样，一个图在顺序存储结构下的类型定义为；

typedef struct {

char vertex[MaxNum]; /*顶点为字符型且顶点表的长度小于MaxNum*/ int edges[MaxNum][MaxNum]; /*边为整型且edges为邻接矩阵*/

} MGraph; /*MGraph为采用邻接矩阵存储的图类型*/

建立一个无向图的邻接矩阵程序如下：

#include #include #define MAXSIZE 30 typedef struct {

char vertex[MAXSIZE]; //顶点为字符型且顶点表的长度小于MAXSIZE int edges[MAXSIZE][MAXSIZE]; //边为整型且edges为邻接矩阵 }MGraph; //MGraph为采用邻接矩阵存储的图类型

void CreatMGraph(MGraph *g,int e,int n)

{ //建立无向图的邻接矩阵g->egdes，n为顶点个数，e为边数 int i,j,k;

printf(\ for(i=0;i

g->vertex[i]=i; //读入顶点信息 for(i=0;i

g->edges[i][j]=0; //初始化邻接矩阵 for(k=1;k<=e;k++) //输入e条边*/ {

printf(\ scanf(\ g->edges[i][j]=1; g->edges[j][i]=1;

} }

void main() { int i,j,n,e;

MGraph *g; //建立指向采用邻接矩阵存储图类型指针 g=(MGraph *)malloc(sizeof(MGraph)); //生成采用邻接矩阵存储图类型的存储空间 printf(\ //输入邻接矩阵的大小 scanf(\

printf(\ //输入邻接矩阵的边数 scanf(\

CreatMGraph(g,e,n); //生成存储图的邻接矩阵 printf(\ //输出存储图的邻接矩阵 for(i=0;i

【说明】

无向图的邻接矩阵表示如图15-1所示。

0 V V 3 0 1 0 1

A= 1 0 1 1 0 1 0 0 V 1 V 1 1 0 0 2

图15-1 无向图及邻接矩阵表示

对图15-1所示的无向图，程序执行如下：

输入： Input size of MGraph: 4↙

Input number of edge: 4↙ Input data of vertexs(0~n-1): Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙

输出： Output MGraph:

0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0

Press any key to continue

1.3 邻接表

邻接表是图的一种顺序存储与链式存储相结合的存储方法。邻接表表示法类似于树的孩子表示法。也即，对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表；然后，将所有顶点的邻接表表头指针放入到一个一维数组中，就构成了图的邻接表。用邻接表表示的图有两种结构，如图7-9所示。顶点域邻接表表头指针邻接点域指针域 vertex firstedge adjvex next 顶点表结点邻接表结点

图7-9 邻接表表示的结点结构

一种是用一维数组表示的顶点表的结点（即数组元素）结构，它由顶点域（vertex）和指向该顶点第一条邻接边的指针域（firstedge）（也即，这个指针指向该顶点的邻接表）所构成。另一种是邻接表结点（边结点），它由邻接点域(adjvex)和指向下一条邻接边的指针域（next）所构成。对带权图（网）的邻接表结点则需增加一个存储边上权值信息的这样一个域。因此，带权图的邻接表结点结构如图7-10所示。 adjvex info next

图7-10 带权图（网）的邻接表结点结构

图7-11给出了图7-6所示的无向图所对应的邻接表表示。

图7-11 无向图的邻接表表示

邻接表表示下的类型定义为：

typedef struct node /*邻接表结点*/ {

int adjvex; /*邻接点域*/

struct node *next; /*指向下一个邻接边结点的指针域*/ }EdgeNode; /*邻接表结点类型*/ typedef struct vnode /*顶点表结点*/ {

int vertex; /*顶点域*/

EdgeNode *firstedge; /*指向邻接表第一个邻接边结点的指针域*/ }VertexNode /*顶点表结点类型*/

建立一个无向图的邻接表存储算法如下：

void CreatAdjlist（VetexNode g[],int e,int n）

{/*建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点*/ EdgeNode *p; int i,j,k;

printf(“Input date of vetex(0~n-1);\\n”);

for(i=0;i

g[i].vertex=i; /*读入顶点i信息*/

g[i].firstedge=NULL; /*初始化指向顶点i的邻接表表头指针*/ }

for(k=1;k<=e;k++) /*输入e条边*/

{

printf(\ scanf(\

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjex=j; /*在顶点vi的邻接表中添加邻接点为j的结点*/ p->next=g[i].firstedge; /*插入是在邻接表表头进行的*/ g[i].firstedge=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=i; /*在顶点vj的邻接表中添加邻接点为i的结点*/ p->next=g[j].firstedge; /*插入是在邻接表表头进行的*/ g[i].firstedge=p; } }

2 图的遍历

图的遍历是指从图中的任一顶点出发，按照事先确定的某种搜索方法依次对图中所有顶点进行访问且仅访问一次的过程。图的遍历要比树的遍历复杂得多，其复杂性主要表现在以下4个方面：

（1）在图结构中，没有象树根结点那样 “自然” 的首结点，即图中的任何一个顶点都可以作为第一个被访问的结点。

（2）在非连通图中，从一个顶点出发只能访问它所在的连通分量上的所有顶点；因此，还需考虑如何选取下一个未被访问的顶点来继续访问图中其余的连通分量。

（3）在图结构中如果有回路存在，则一个顶点被访问后有可能沿回路又回到该顶点。（4）在图结构中一个顶点可以和其它多个顶点相邻，当该顶点访问过后则存在如何从众多相邻顶点中选取下一个要访问的顶点问题。

图的遍历是图的一种基本操作，它是求解图的连通性问题、拓扑排序以及求关键路径等算法的基础。图的遍历通常采用深度优先搜索（Depth First Search,DFS）和广度优先搜索（Breadth First Search,BFS）两种方式，这两种方式对无向图和有向图的遍历都适用。

2.1 深度优先搜索

深度优先搜索对图的遍历类似于树的先根遍历，是树的先根遍历的一种推广；也即，搜索顶点的次序是沿着一条路径尽量向纵深发展。深度优先搜索的基本思想是：假设初始状态是图中所有顶点都未曾访问过，则深度优先搜索可以从图中某个顶点v出发即先访问v，然后依次从v的未曾访问过的邻接点出发，继续深度优先搜索图，直至图中所有和v有路径相通的顶点都被访问过；若此时图中尚有顶点未被访问过，则另选一个未曾访问过的顶点作为起始点，重复上述深度优先搜索的过程，直到图中的所有顶点都被访问过为止。

我们以图7-18的无向图为例进行图的深度优先搜索。假定从顶点v0出发，在访问了顶点v0后选择邻接点v1作为下一个访问的顶点；由于v1未曾访问过，则访问v1并继续由v1开始搜索下一个邻接点v3作为访问顶点；v3同样没有访问过，则访问v3并继续搜索下一个邻接点v6；v6也未访问过，则访问v6再继续搜索下一个邻接点v4；v4未曾访问过，则访问v4并继续搜索下一个邻接点v1，此时由于v1已被访问过则回退至v4继续搜索v4的下一个邻接点；由于v4已无未被访问过的邻接点，则继续回退到v6再搜索v6的未被访问邻接点；?这种回退一直持续到v0，此时可搜索到v0的未被访问邻接点v2，即访问v2并继续搜索下一个邻接点v5；由于v5未被访问，则访问v5并继续搜索v5的邻接点；因v5已无未被访问过的邻接点故回退至v2，继续搜索v2的未被访问邻接点，但v2

已无未被访问过的邻接点，则回退至v0，而v0也无未被访问的邻接点。由于v0为搜索图时的出发结点，故到此搜索结束。由此得到深度优先搜索遍历图的结点序列为：

v0→v1→v3→v6→v4→v2→v5

图7-18 无向图深度优先搜索示意

显然，深度优先搜索遍历图的过程是一个递归过程，我们可以用递归算法来实现。在算法中为了避免在访问过某顶点后又沿着某条回路回到该顶点这种重复访问的情况出现，就必须在图的遍历过程中对每一个访问过的顶点进行标识，这样才可以避免一个顶点被重复访问的情况出现。所以，我们在遍历算法中对n个顶点的图设置了一个长度为n的访问标志数组visited[n]，每个数组元素被初始化0，一旦某个顶点i被访问则相应的visited[i]就置为1来做为访问过的标志。

对以邻接表为存储结构的图（可为非连通图）进行深度优先搜索的程序如下： #include #include #define MAXSIZE 30

typedef struct node //邻接表结点 {

int adjvex; //邻接点域

struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n)

{//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 EdgeNode *p; int i,j,k;

printf(\

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 }

for(k=1;k<=e;k++) //输入e条边 {

printf(\ scanf(\

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点

p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } }

int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量 void DFS(VertexNode g[],int i) {

EdgeNode *p;

printf(\ //输出顶点i信息，即访问顶点i visited[i]=1; //置顶点i为访问过标志 p=g[i].firstedge;

//根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=NULL) //当邻接边结点不为空时 {

if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 DFS(g,p->adjvex); //对这个边结点进行深度优先搜索 p=p->next; //查找顶点i的下一个邻接边结点 } }

void DFSTraverse(VertexNode g[],int n)

{//深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数 int i;

for(i=0;i

visited[i]=0; //访问标志置0

for(i=0;i

void main() { int e,n;

VertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf(\ //输入图中结点个数 scanf(\

printf(\ //输入图中边的个数 scanf(\

printf(\ CreatAdjlist(g,e,n); //建立无向图的邻接表 printf(\

DFSTraverse(g,n); //深度优先遍历以邻接表存储的无向图 printf(\}

【说明】

对图15-1所示的无向图，程序执行如下：

输入： Input number of node:

4↙

Input number of edge:

4↙

Make adjlist:

Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙

输出： DFSTraverse:

0 3 1 2

Press any key to continue

2.2 广度优先搜索

广度优先搜索遍历图类似于树的按层次遍历。广度优先搜索的基本思想是：从图中某顶点v出发，访问顶点v后再依次访问与v相邻接的未曾访问过的其余邻接边结点v1，v2，?，vk；接下来再按上述方法访问与v1邻接的未曾访问过的各邻接边结点、与v2邻接的未曾访问过的各邻接边结点、?、与vk邻接的未曾访问过的各邻接边结点；?这样逐层下去直至图中的全部顶点都被访问过。广度优先搜索遍历图的特点是尽可能先进行横向搜索，即先访问的顶点其邻接边结点也先访问，后访问的顶点其邻接边结点也后访问。

例如，对图7-19所示的无向图进行广度优先搜索遍历，首先访问v0，然后访问v0

未被访问的邻接边结点v1和v3（注意，先是v1然后才是v3），接下来访问v1未被访问的邻接边结点v4，再访问v3未被访问邻接边结点v2（v3的邻接边结点v4已被访问过）。此时，图中所有顶点都被访问过即完成了图的遍历，所得到的顶点访问序列为：

v0→v1→v3→v4→v2

为了实现图的广度优先搜索，必须引入队列结构来保存已访问过的顶点序列；即从指定的顶点开始，每访问一个顶点就同时使该顶点进入队尾；然后由队头取出一个顶点并访问该顶点的所有未被访问过的邻接边结点并且使该邻接边结点进入队尾，?如此进行下去直到队空时为止，则图中所有由开始顶点所能到达的全部顶点均已访问过。对以邻接表为存储结构的图进行广度优先搜索的程序如下： #include #include #define MAXSIZE 30

typedef struct node1 //邻接表结点 {

int adjvex; //邻接点域

struct node1 *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n)

{//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 EdgeNode *p; int i,j,k;

printf(\

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 }

for(k=1;k<=e;k++) //输入e条边 {

printf(\ scanf(\

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } }

typedef struct node {

int data;

struct node *next; }QNode; //链队列结点的类型 typedef struct {

QNode *front,*rear; //将头、尾指针纳入到一个结构体的链队列 }LQueue;

void Init_LQueue(LQueue **q) //创建一个带头结点的空队列 {

QNode *p;

*q=(LQueue *)malloc(sizeof(LQueue));//申请带头、尾指针的结点 p=(QNode*)malloc(sizeof(QNode)); //申请链队列的头结点 p->next=NULL; //头结点的next指针置为空 (*q)->front=p; //队头指针指向头结点 (*q)->rear=p; //队尾指针指向头结点 }

int Empty_LQueue(LQueue *q) //判队空 {

if(q->front==q->rear) //队为空 return 1; else

return 0; }

void In_LQueue(LQueue *q,int x) //入队 {

QNode *p;

p=(QNode *)malloc(sizeof(QNode)); //申请新链队列结点 p->data=x;

p->next=NULL; //新结点作为队尾结点时其next域为空 q->rear->next=p; //将新结点*p链到原队尾结点之后 q->rear=p; //使队尾指针指向新的队尾结点*p }

void Out_LQueue(LQueue *q,int *x) //出队 {

QNode *p;

if(Empty_LQueue(q))

printf(\ //队空，出队失败 else {

p=q->front->next; //指针p指向链队列第一个数据结点（即队头结点） q->front->next=p->next;

//头结点的next指针指向链队列第二个数据结点（即删除第一个数据结点） *x=p->data; //将删除的队头结点数据经由x返回 free(p);

if(q->front->next==NULL) //出队后队为空，则置为空队列 q->rear=q->front; } }

int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量 void BFS(VertexNode g[],LQueue *Q,int i)

{//广度优先搜索遍历邻接表存储的图，g为顶点表，Q为队指针，i为第i个顶点 int j,*x=&j; EdgeNode *p;

printf(\ //输出顶点i信息，即访问顶点i visited[i]=1; //置顶点i为访问过标志 In_LQueue(Q,i); //顶点i入队Q while(!Empty_LQueue(Q)) //当队Q非空时 {

Out_LQueue(Q,x); //队头顶点出队并送j（暂记为顶点j） p=g[j].firstedge;//根据顶点j的表头指针查找其邻接表的第一个邻接边结点 while(p!=NULL) {

if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 {

printf(\输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送入队Q }

p=p->next; //在顶点j 的邻接表中查找j的下一个邻接边结点 } } }

void main() { int e,n;

VertexNode g[MAXSIZE]; //定义顶点表结点类型数组g LQueue *q; printf(\ //输入图中结点个数 scanf(\

printf(\ //输入图中边的个数 scanf(\

printf(\ CreatAdjlist(g,e,n); //建立无向图的邻接表 Init_LQueue(&q); //队列q初始化 printf(\

BFS(g,q,0); //广度优先遍历以邻接表存储的无向图 printf(\}

【说明】

对图15-1所示的无向图，程序执行如下：

输入： Input number of node:

4↙

Input number of edge: 4↙

Make adjlist:

Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙

输出： BFSTraverse:

0 3 1 2

Press any key to continue

2.3图的连通性问题

判断一个图的连通性是图的应用问题，我们可以利用图的遍历算法来求解这一问题。

1. 无向图的连通性

在对无向图进行遍历时，对连通图仅需从图中任一顶点出发进行深度优先搜索或广度优先搜索，就可访问到图中的所有顶点；对于非连通图，则需要由不连通的多个顶点开始进行搜索，且每一次从一个新的顶点出发进行搜索过程中得到的顶点访问序列，就是包含该出发顶点的这个连通分量中的顶点集。

因此，要想判断一个无向图是否为连通图，或者有几个连通分量，则可增加一个计数变量count并设其初值为0，在深度优先搜索算法DFSTraverse函数里的第二个for循环中，每调用一次DFS就给count增1；这样当算法执行结束时的count值即为连通分量的个数。

无向图连通分量的计算程序如下

#include #include #define MAXSIZE 30

typedef struct node1 //邻接表结点 {

int adjvex; //邻接点域

struct node1 *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n)

{//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 EdgeNode *p; int i,j,k;

printf(\

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 }

for(k=1;k<=e;k++) //输入e条边 {

printf(\ scanf(\

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } }

int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量 void DFS(VertexNode g[],int i) //图的深度优先遍历 {

EdgeNode *p;

printf(\ //输出顶点i信息，即访问顶点i visited[i]=1; //置顶点i为访问过标志 p=g[i].firstedge;

//根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=NULL) //当邻接边结点不为空时 {

if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 DFS(g,p->adjvex); //对这个边结点进行深度优先搜索 p=p->next; //查找顶点i的下一个邻接边结点 } }

int count=0; //连通分量计数count初值为0

void ConnectEdge(VertexNode g[],int n) //求图的连通分量

{//深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数 int i;

for(i=0;i

visited[i]=0; //访问标志置0

for(i=0;i

DFS(g,i); //从未访问过的顶点i开始遍历 count++; //访问过一个连通分量则count加1 } }

void main() { int e,n;

VertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf(\ //输入图中结点个数 scanf(\

printf(\ //输入图中边的个数 scanf(\

printf(\ CreatAdjlist(g,e,n); //建立无向图的邻接表 printf(\

ConnectEdge(g,n); //求图的连通分量 printf(\输出连通分量 }

【说明】

图15-2无向图示意

对图15-2所示的无向图，程序执行如下：

输入： Input number of node:

8↙

Input number of edge: 7↙

Make adjlist:

Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,2↙ Input edge of(i,j): 0,4↙

Input edge of(i,j): 1,3↙ Input edge of(i,j): 2,3↙ Input edge of(i,j): 5,6↙ Input edge of(i,j): 5,7↙

输出： DFSTraverse:

0 4 2 3 1 5 7 6 Number of connect is 2 Press any key to continue

3 生成树与最小生成树 3.1 生成树和生成森林

对于连通的无向图和强连通的有向图G=(V, E)，如果从图中任一顶点出发遍历图时，必然会将图中边的集合E(G)分别为两个子集T(G)和B(G)；其中，T(G)为遍历中所经过的边的集合，而B(G)为遍历中未经过的边的集合。显然，T(G)和图G中所有顶点一起构成了连通图G的一个极小连通子图；也即，G'=(V, T)是G的一个子图。按照生成树的定义，图G'为图G的一棵生成树。

连通图的生成树不是唯一的。从不同顶点出发进行图的遍历，或者虽然从图的同一个顶点出发但图的存储结构不同都可能得到不同的生成树。当一个连通图具有n个顶点时，该连通图的生成树就包含图中的全部n个顶点但却仅有连接这n个顶点的n-1条边。生成树不具有回路，在生成树G'=(V, T)中任意添加一条属于B(G)的边则必定产生回路。我们将由深度优先搜索遍历图所得到的生成树称为深度优先生成树，将由广度优先搜索遍历图所得到的生成树称为广度优先生成树。图7-22(b)和图7-22(c)就是由图7-22(a)所得到的深度优先生成树和广度优先生成树；图中虚线为集合B(G)中的边，而实线为集合T(G)中的边。

图7-22 无向图及其生成树示意

对非连通图，通过对各连通分量的遍历将得到一个生成森林。

深度优先生成树求解可在DFS算法中添加一条语句得到，因为在DFS(g,i)中递归调用DFS(g,p->adjvex)时，i是刚访问过顶点vi的序号，而p->adjvex是vi未被访问过且正准备访问的邻接边结点序号。所以，只要在DFS算法中的if语句里，在递归调用DFS(g,p->adjvex)语句之前将边“(i,p->adjvex)”输出即可。同样也可在BFS算法中插入输出边的语句即可求得广度优先生成树算法。深度优先生成树程序如下：

#include #include #define MAXSIZE 30

typedef struct node //邻接表结点 {

int adjvex; //邻接点域

struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n)

{//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 EdgeNode *p; int i,j,k;

printf(\

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 }

for(k=1;k<=e;k++) //输入e条边 {

printf(\ scanf(\

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } }

int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量 void DFSTree(VertexNode g[],int i) //图的深度优先遍历 {

EdgeNode *p;

visited[i]=1; //置顶点i为访问过标志 p=g[i].firstedge;

//根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=NULL) //当邻接边结点不为空时 {

if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 {

printf(\ //输出生成树中的一条边 DFSTree(g,p->adjvex); //对这个边结点进行深度优先搜索 }

p=p->next; //查找顶点i的下一个邻接边结点 } }

void DFSTraverse(VertexNode g[],int n) //生成深度优先生成树

{//深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数

int i;

for(i=0;i

visited[i]=0; //访问标志置0*/

for(i=0;i

void main() { int e,n;

VertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf(\ //输入图中结点个数 scanf(\

printf(\ //输入图中边的个数 scanf(\

printf(\ CreatAdjlist(g,e,n); //建立无向图的邻接表 printf(\

DFSTraverse(g,n); //生成深度优先生成树 printf(\} 【说明】

对图15-1所示的无向图，程序执行如下：

输入： Input number of node:

4↙

Input number of edge: 4↙

Make adjlist:

Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙

输出： DFSTraverse:

(0,3),(3,1),(1,2),

Press any key to continue

广度优先生成树程序如下： #include #include #define MAXSIZE 30 typedef struct {

int data[MAXSIZE]; /*队中元素存储空间*/

int rear,front; /*队尾和队头指针*/ }SeQueue;

void Int_SeQueue(SeQueue **q) {

*q=(SeQueue*)malloc(sizeof(SeQueue)); (*q)->front=0; (*q)->rear=0; }

int Empty_SeQueue(SeQueue *q) //判队空 {

if(q->front==q->rear)

return 1; //队空 else

return 0; //队不空 }

void In_SeQueue(SeQueue *q,int x) //入队 {

if((q->rear+1)%MAXSIZE==q->front) printf(\ //队满，入队失败 else {

q->rear=(q->rear+1)%MAXSIZE; //队尾指针加1 q->data[q->rear]=x; //将元素x入队 } }

void Out_SeQueue(SeQueue *q,int *x) //出队 {

if(q->front==q->rear)

printf(\ //队空，出队失败 else {

q->front=(q->front+1)%MAXSIZE; //队头指针加1

*x=q->data[q->front]; //队头元素出队并由x返回队头元素值 } }

typedef struct node //邻接表结点 {

int adjvex; //邻接点域

struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n)

{//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点

EdgeNode *p; int i,j,k;

printf(\

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 }

for(k=1;k<=e;k++) //输入e条边 {

printf(\ scanf(\

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } }

int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量 void BFSTree(VertexNode g[],int i) //生成广度优先生成树

{//广度优先搜索遍历邻接表存储的图，g为顶点表，Q为队指针，i为第i个顶点 int j,*x=&j; SeQueue *q; EdgeNode *p;

visited[i]=1; //置顶点i为访问过标志 Int_SeQueue(&q);

In_SeQueue(q,i); //顶点i入队q

while(!Empty_SeQueue(q)) //当队q非空时 {

Out_SeQueue(q,x); //队头顶点出队并送j（暂记为顶点j） p=g[j].firstedge;//根据顶点j的表头指针查找其邻接表的第一个邻接边结点 while(p!=NULL) {

if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 {

printf(\ //输出生成树中的一条边

visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_SeQueue(q,p->adjvex); //将该邻接边结点送入队q }

p=p->next; //在顶点j 的邻接表中查找j的下一个邻接边结点 } }

}

void main() { int e,n;

VertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf(\ //输入图中结点个数 scanf(\

printf(\ //输入图中边的个数 scanf(\

printf(\ CreatAdjlist(g,e,n); //建立无向图的邻接表 printf(\

BFSTree(g,0); //由顶点0开始生成广度优先生成树 printf(\}

【说明】

对图15-1所示的无向图，程序执行如下：

输入： Input number of node:

4↙

Input number of edge: 4↙

Make adjlist:

Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input edge of(i,j): 0,3↙ Input edge of(i,j): 1,3↙ Input edge of(i,j): 1,2↙

输出： DFSTraverse:

(0,3),(0,1),(1,2),

Press any key to continue

3.2 最小生成树与构造最小生成树的Prim算法

由于生成树的不唯一性，即从不同的顶点出发可能得到不同的生成树，对不同的存储结构从同一顶点出发也可能得到不同的生成树。在连通网中边是带权值的，则连通网的生成树各边也是带权值的，我们把生成树各边权值总和称为生成树的权；那么，对无向连通图构成的连通网，则它的所有生成树中必有一棵边的权值总和为最小的生成树，我们称这棵生成树为最小生成树。

最小生成树有许多重要的应用，如以尽可能低的总造价建立n个城市间的通讯网络。我们可以用连通网来表示n个城市以及n个城市之间可能设置的通讯线路；其中网的顶点表示城市、边表示两城市之间的线路，边的权值表示该线路的造价。要想使总的造价最低，实际上就是寻找该网络的最小生成树。

构造最小生成树必须解决好以下两个问题：

（1）尽可能选取权值小的边，但不能构成回路。

（2）选取合适的n-1条边将连通网的n个顶点连接起来。

构造最小生成树的算法主要是利用最小生成树的一种简称为MST的性质：设G=(V，E)是一个连通网络，U是顶点集合V的一个真子集。若(u,v)是G的所有边中一个顶点在U(即u?U)里，而另一个顶点不在U(即v?V-U)里且具有最小权值的一条边，则最小生成树必然包含边(u,v)。

普里姆（Prim）算法就是一种依据MST性质构造最小生成树的方法。假设G=(V，E)为一连通网，其中V为网中所有顶点的集合，E为网中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U={u0}（假设构造最小生成树时是从顶点u0出发），集合T的初值为T={}。Prim算法的思想是：在连通网中寻找一个顶点落入U集、另外一个顶点落入V-U集且权值最小的边加入到集合T中，并且将该边的属于V-U集的这个顶点加入到U集中，然后继续上述寻找一顶点在U集而另一顶点在V-U集且权值最小的边；如此不断重复直到U=V时，最小生成树就已经生成，这时集合T中包含了最小生成树中的所有边。

Prim算法能够实现最小生成树构造的理由如下：（1）构造过程中对正在生成的最小生成树来说，处于U集中的顶点都是有边相连的顶点，而V-U集中的顶点都是没有边相连的顶点，故一个顶点在V-U集的边则保证了这个顶点是第一次连接，因此不产生回路；另一个顶点在U集，则保证了生成树构造的连通性，即不会出现不连通的情况。

（2）最小生成树的构造过程要进行到U集等于V集为止，即此时U集中的顶点已包含连通网中的全部顶点，由(1)可知这些顶点都有边相连且又不产生回路，故必为一生成树。

（3）在保证（1）的前提下每次都是选取权值最小的边来构造生成树，故最终生成的树为最小生成树。

Prim算法可用下述过程描述(wuv表示连接顶点u与顶点v的这条边上的权值)：（1） U={u0}，T={ }；（2） while(U≠V)

{(u,v)=min{wuv；u?U，v?V-U} T=T+{(u,v)} U=U+{v} }

（3）结束。

为实现Prim算法，需要设置两个一维数组lowcast和closevertex；其中，数组lowcost用来保存集合V-U中各顶点与集合U中各顶点所构成的边中具有最小权值的边的权值，并且一旦将lowcost[i]置为0，则表示顶点i已加入到集合U中，即该顶点不再作为寻找下一个最小权值边的顶点（只能在V-U集中寻找），否则将形成回路；也即，数组lowcost有两个功能：一个是记录边的权值，一个是标识U集中的顶点。数组closevertex用来保存依附于该边在集合U中的顶点，即若closevertex[i]的值为j，则表示边(i,j)中的顶点j在集合U中；数组closevertex同时也保存构造最小生成树过程中产生的每一条边，如closevertex[i]的值为j，则边(i,j)即为最小生成树的一条边。

我们先设定初始状态U={u0}（u0为出发的顶点），这时置lowcost[0]为0则表示顶点u0已加入到U集中，数组lowcost其它的数组元素值则为顶点u0到其余各顶点边的权值（没有边相连则取一个极大值），同时初始化数组closevertex[i]所有数组元素值为0（即先假定所有顶点包括u0都与u0有一条边）。然后不断选取权值最小的边(ui,uk)（ui?U，

uk?V-U），每选取一条边就将lowlost[k]置为0，表示顶点uk已加入到集合U中。由于uk从集合V-U进入到集合U，故这两个集合中的顶点发生了变化，所以需要依据这些变化修改数组lowcost和数组closevertex中的相关内容。最终数组closevertex中的边即构成一个最小生成树。

当连通网采用二维数组存储邻接矩阵时，Prim算法实现的程序如下： #include

#define MAXNODE 30 #define MAXCOST 32767

void Prim(int gm[][6],int closevertex[],int n)

{/*从存储序号为0的顶点出发建立连通网的最小生成树，gm是邻接矩阵，n为顶点个数（即有0～n-1个顶点）最终建立的最小生成树存于数组closevertex中*/ int lowcost[MAXNODE]; int i,j,k,mincost;

for(i=1;i

lowcost[i]=gm[0][i]; //边(u0,ui)的权值送lowcost[i] closevertex[i]=0; //假定顶点ui到顶点u0有一条边 }

lowcost[0]=0;//从序号为0的顶点u0出发生成最小生成树，此时u0已经进入U集 closevertex[0]=0;

for(i=1;i

mincost=MAXCOST; //MAXCOST为一个极大的常量值 j=1;k=0;

while(j

if(lowcost[j]!=0&& lowcost[j]

mincost=lowcost[j]; //记下最小权值边的权值

k=j; //记下最小权值边在V-U集中的顶点序号j } j++; }

printf(\ //输出最小生成树的边与权值

lowcost[k]=0; //顶点k进入U集 for(j=1;j

if(lowcost[j]!=0&&gm[k][j]< lowcost[j]) { /*若顶点k进入U集后使顶点k和另一顶点j（在V-U集中）构成的边权值变小则改变lowcost[j]为这个小值，并将此最小权值的边（j,k）记入closevertex数组*/ lowcost[j]=gm[k][j]; closevertex[j]=k; } } }

void main()

{

int closevertex[MAXNODE]; //存放最小生成树所有边的数组 int g[6][6]={{100,6,1,5,100,100},{6,100,5,100,3,100},{1,5,100,5,6,4} ,{5,100,5,100,100,2},{100,3,6,100,100,6},{100,100,4,2,6,100}}; Prim(g,closevertex,6); //生成最小生成树 }

【说明】

图15-3 连通网及其对应的邻接矩阵

主函数main中已存放了图6-3所示连通网的数据，程序执行如下：

输出： Edge:(2,0),Wight:1

Edge:(5,2),Wight:4 Edge:(3,5),Wight:2 Edge:(1,2),Wight:5 Edge:(4,1),Wight:3

Press any key to continue

3.3 构造最小生成树的Kruskal算法

克鲁斯卡尔（Kruskal）算法是一种按照连通网中边的权值递增的顺序构造最小生成树的方法。Kruskal算法的基本思想是：假设连通网G=(V, E)，令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择权值最小的边，若该边依附的顶点落在T中不同的连通分量中，则将此边加入到T中；否则，舍去此边而选下一条权值最小的边；依此类推，直到T中所有顶点都在同一个连通分量上（此时含有n-1边）为止，这时的T就是一棵最小生成树。

注意，初始时T的连接分量为顶点个数n，在每一次选取最小权值的边加入到T时一定要保证使T的连通分量减1；也即选取最小权值边所连接的两个顶点必须位于不同的连通分量上，否则舍去此边而再选取下一条最小权值的边。

Kruskal算法能够实现最小生成树的理由如下：

（1）边的两个顶点落在T的不同分量保证了在最小生成树的构造中没有回路产生。（2）每次选择边加入T时要同时保证使T的连通分量减1，这是为了确保所构造的树是连通的。

（3）在保证（1）和（2）的前提下选取权值最小的边来构造生成树，则最终生成的树为最小生成树。

实现Kruskal算法的关键是如何判断所选取的边是否与生成树中已保留的边形成回路，这可通过判断边的两个顶点所在的连通分量的方法来解决。为此设置一个辅助数组vest（数组元素下标为0～n-1），它用于判断两顶点之间是否连通，数组元素vest[i]（其初值为i）代表序号为i的顶点所在连通分量的编号；当选中不连通的两个顶点相连的这条边时，则它们分属的两个顶点集合（即两个连通分量），此时按其中的一个编号重新统一编号（即合并成一个连通分量））。因此，当两个顶点的集合（连通分量）编号不同时，则加入这两个顶点所构成的边到最小生成树中就一定不会形成回路，因为这两个顶点分属于不同的连通分量。

在实现Kruskal算法时，需要用一个数组E来存放图G中的所有边，并要求它们是按权值由小到大的顺序排列的；为此先从图G的邻接矩阵中获取所有边集E（注意，在连接矩阵中顶点i和顶点j存在着（i，j）和（j，i）两条边，故只取i

后再用冒泡排序法对边集E按权值递增排序。Kruskal算法实现程序如下： #include #define MAXSIZE 30 #define MAXCOST 32767 typedef struct {

int u; //边的起始顶点 int v; //边的终止顶点 int w; //边的权值 }Edge;

void Bubblesort(Edge R[],int e) //冒泡排序 { //对数组R中的e条边按权值递增排序 Edge temp; int i,j,swap;

for(i=0;i

swap=0; //置未交换标志 for(j=0;jR[j+1].w) {

temp=R[j];R[j]=R[j+1]; R[j+1]=temp; //交换R[j]和R[j+1] swap=1; //置有交换标志 }

if(swap==0) break;//本趟比较中未出现交换则结束排序（已排好） } }

void Kruskal(int gm[][6],int n)

{ //在顶点为n的连通网中构造最小生成树，gm为连通网的邻接矩阵 int i,j,u1,v1,sn1,sn2,k; int vest[MAXSIZE];

Edge E[MAXSIZE]; //MAXSIZE为可存放边数的最大常量值 k=0;

for(i=0;i

if(i

E[k].u=i; E[k].v=j;

E[k].w=gm[i][j]; k++; }

Bubblesort(E,k); //采用冒泡排序对数组E中的k条边按权值递增排序 for(i=0;i

vest[i]=i; //给每个顶点置不同连通分量编号，即初始时有n个连通分量 k=1; //k表示当前构造生成树的第n条边，初值为1 j=0; //数组E中元素的下标，初值为0 while(k

{

u1=E[j].u;v1=E[j].v; //取一条边的头尾顶点 sn1=vest[u1];

sn2=vest[v1]; //分别得到这两个顶点所属的集合（连通分量）编号 if(sn1!=sn2) {//两顶点分属于不同集合（连通分量）则该边为最小生成树的一条边 printf(\ k++; //生成的边数增加1 for(i=0;i

if(vest[i]==sn2) //集合编号为sn2的第i号边其编号改为sn1 vest[i]=sn1; }

j++; //扫描下一条边 } }

void main() {

int g[6][6]={{100,6,1,5,100,100},{6,100,5,100,3,100},{1,5,100,5,6,4} ,{5,100,5,100,100,2},{100,3,6,100,100,6},{100,100,4,2,6,100}}; Kruskal(g,6); //生成最小生成树 }

【说明】

主函数main中已存放了图15-3所示连通网的数据，程序行如下：

输出： Edge:(0,2),Wight:1

Edge:(3,5),Wight:2 Edge:(1,4),Wight:3 Edge:(2,5),Wight:4 Edge:(1,2),Wight:5

Press any key to continue

4 最短路径

如果用带权图（网）表示一个公路交通网，图中的每个顶点代表一个地方（如城市、车站等），边代表两地之间有一条可达的公路，边上的权值表示公路的长度或者表示通过这段公路所花费的时间或费用；那么，从一个地方到另一个地方的路径长度则为该路径上各边的权值之和。如果要从A地到达B地，则我们所关心的问题是：（1）从A地到B地是否有路可达？

（2）如果从A地到B地有多条路径，那么哪一条路径最短？

上述问题可归结为在带权图（网）里求点A到点B所有路径中边的权值之和为最短的那一条路径，这条路径就是两点之间的最短路径；并称路径上的第一个顶点为源点（Sourse），最后一个顶点为终点（Destination）。在无权图中，最短路径则是指两点之间经历的边数最少的路径。实际上，只要把无权图上的每条边都看成是权值为1的边，那么无权图和带权图的最短路径是一致的。下面讨论两种最常见的最短路径问题。

4.1 从一个源到其它各点的最短路径

给定一个带权有向图G=(V, E)，指定图G中的某一个顶点的v为源点，求出从v到

其它各顶点之间的最短路径；这个问题称为单源点最短路径问题。

迪杰斯特拉（Dijkstra）根据若按长度递增的次序生成从源点v0到其它顶点的最短路径，则当前正在生成的最短路径上除终点之外，其余顶点的最短路径均已生成这一思想，提出了按路径长度递增的次序产生最短路径的算法（在此，路径长度为路径上边或弧的权值之和）。Dijkstra算法的思想是：对带权有向图G=(V, E)，设置两个顶点集合S和T=V-S；凡以v0为源点并已确定了最短路径的终点（顶点）都并入到集合S，集合S的初态只含有源点v0；而未确定其最短路径的顶点均属于集合T，初态时集合T包含除源点v0之外的其余顶点。按照各顶点与v0间最短路径长度递增的次序，逐个把集合T中的顶点加入到集合S中去，使得从源点v0到集合S中各顶点的路径长度始终不大于v0到集合T中各顶点的路径长度。并且，集合S中每加入一个新的顶点u，都要修改源点v0到集合T中剩余顶点的最短路径长度；也即，集合T中各顶点v新的最短路径长度值是原来最短路径长度值或者是顶点u的最短路径长度值再加上顶点u到顶点v的路径长度值这二者中的较小值。这种把集合T中的顶点加入到集合S中的过程不断重复直到集合T的顶点全部加入到集合S中为止。

注意，在向集合S中添加顶点时，总是保持从源点v0到集合S中各顶点的最短路径长度不大于从源点v0到集合T中任何顶点的最短路径长度。例如，若刚向集合S中添加的是顶点vk，对于集合T中的每一个顶点vu，如果顶点vk到vu有边（设权值为w2），且原来从顶点v0到顶点vu的路径长度（设权值为w3）大于从顶点v0到顶点vk的路径长度（设权值为w1）与边(vk,vu)的权值w2之和，即w3>w1+w2（如图7-28所示）。则将v0→vk→vu这一路径作为vu新的最短路径。

图7-28 顶点v0到顶点vu不同路径长度的比较

Dijkstra算法的实现是以二维数组gm作为n个顶点带权有向图G=(V, E)的存储结构的，并设置一个一维数组s（下标由0～n-1）用来标记集合S中已找到最短路径的顶点，而且规定：如果s[i]为0，则表示未找到源点v0到顶点vi的最短路径，也即此时vi在集合T中；如果s[i]为1，则已找到源点v0到顶点vi的最短路径（此时vi在集合S中）。除了数组s外，还设置了一个数组dist（下标由0～n-1），且dist[i]用来保存从源点v0到终点vi的当前最短路径长度，它的初值为边上的权值；若v0到vi没有边，则权值为∞；此后每当有一个新的顶点进入集合S中。则dist[i]值可能被修改变小。一维数组path（下标由0～n-1）用于保存最短路径长度中路径上边所经过的顶点序列；其中，path[i]保存从源点v0到终点vi当前最短路径中前一个顶点的编号，它的初值是：如果v0到vi有边则置path[i]为v0的编号；如果v0到vi没有边则置path[i]为-1。

Dijkstra算法实现程序如下： #include

#define MAXSIZE 6 //带权有向图中顶点的个数 #define INF 32767

void Ppath(int path[],int i,int v0)

{ //先序递归查找最短路径（源点为v0）上的顶点 int k; k=path[i];

if(k!=v0) //顶点vk不是源点v0时 {

Ppath(path,k,v0); //递归查找顶点vk的前一个顶点 printf(\ //输出顶点vk

} }

void Dispath(int dist[],int path[],int s[],int v0,int n)

{ //输出最短路径的函数 int i;

for(i=0;i

if(s[i]==1) //顶点vi在集合S中 {

printf(\从%d到%d的最短路径长度为:%d, 路径为：\ printf(\ //输出路径上的源点v0 Ppath (path,i,v0); //输出路径上的中间顶点vi printf(\ //输出路径上的终点 } else

printf(\从%d到%d不存在路径\\n\}

void Dijkstra(int gm[][MAXSIZE],int v0,int n) {

int dist[MAXSIZE],path[MAXSIZE],s[MAXSIZE]; int i,j,k,mindis; for(i=0;i

dist[i]=gm[v0][i]; //v0到vi的最短路径初值赋给dist[i] s[i]=0; //s[i]=0表示顶点vi属于T集

if(gm[v0][i]

path[i]=-1; //v0到vi没有边 }

s[v0]=1;path[v0]=0; //v0并入集合S且v0的当前最短路径中无前一个顶点 for(i=0;i

mindis=INF;

for(j=0;j

k=j;

mindis=dist[j]; }

s[k]=1; //顶点vk加入集合S中

for(j=0;j

if(gm[k][j]

{ //当v0到vj的路径长度小于v0到vk和vk到vj的路径长度时 dist[j]=dist[k]+gm[k][j];

path[j]=k; //vk是当前最短路径中vj的前一个顶点 }

}

Dispath(dist,path,s,v0,n); //输出最短路径 }

void main() {

int g[MAXSIZE][ MAXSIZE]={{INF,20,15,INF,INF,INF},{2,INF,INF,INF,10,30},

{INF,4,INF,INF,INF,10},{INF,INF,INF,INF,INF,INF},{INF,INF,INF,15,INF,INF}, {INF,INF,INF,4,10,INF}}; //定义邻接矩阵g并给邻接矩阵g赋值 Dijkstra(g,0,6); //求顶点0的最短路径 }

【说明】

图15-4 带权有向图及邻接矩阵示意

主函数main中已存放了图15-4所示的带权有向图，程序执行如下：

输出：从0到0的最短路径长度为:32767, 路径为：0,0

从0到1的最短路径长度为:19, 路径为：0,2,1 从0到2的最短路径长度为:15, 路径为：0,2 从0到3的最短路径长度为:29, 路径为：0,2,5,3 从0到4的最短路径长度为:29, 路径为：0,2,1,4 从0到5的最短路径长度为:25, 路径为：0,2,5 Press any key to continue

4.2 每一对顶点之间的最短路径

若要找到每一对顶点之间的最短路径，则可采取这种方法，即每次以一个顶点为源点执行Dijkstra算法，n个顶点共重复执行n次Dijkstra算法，这样就可求得每一对顶点的最短路径。这种方法下算法的时间复杂度为O(n3)。

该问题的另一种解法是弗洛伊德（Floyd）算法，其算法的时间复杂性也是O(n3)，但形式上却相对简单。

假设带权有向图G=(V, E)并采用邻接矩阵gm存储，另外设置一个二维数组A用于存放当前顶点之间的最短路径长度，数组元素A[i][j]表示当前顶点vi到顶点vj的最短路径长度。Floyd算法的基本思想是递推产生一个矩阵序列：A0,A1,?,Ak,?,An，其中Ak[i][j]表示从顶点vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度。

初始时置A-1[i][j]=gm[i][j]。当求从顶点vi到顶点vj的路径上所经过的顶点编号不大于k+1的最短路径长度时要分两种情况考虑：一种情况是该路径不经过顶点编号为k+1的顶点，此时该路径长度与从顶点vi到顶vj的路径上所经过的顶点编号不大于k的最短路径长度相同；另一种情况是从顶点vi到顶点vj的最短路径上经过编号为k+1的顶点，那么该路径可分为两段，一段是从顶点vi到顶点vk+1的最短路径，另一段是从顶点vk+1到顶点vj的最短路径，此时最短路径长度等于这两段路径长度之和。这两种情况中的较小值就是所求的从顶点vi到顶点vj的路径上所经过的顶点编号不大于k+1的最短路径。

Floyd思想可用下式描述： A-1[i][j]=gm[i][j]

Ak+1[i][j]=min{Ak[i][j]，Ak[i][k+1]+Ak[k+1][j]} -1≤k≤n-2

该式是一个迭代公式，Ak表示已考虑顶点0、1、?、k等k+1个顶点之后各顶点之间的最短路径，即Ak[i][j]表示由vi到vj已考虑顶点0、1、?、k等k+1个顶点的最短路

径；在此基础上再考虑顶点k+1并求出各顶点在考虑顶点k+1后最短路径，即得到Ak+1。每迭代一次，在从vi到vj的最短路径上就多考虑了一个顶点；经过n次迭代后所得到的An-1[i][j]值，就是考虑所有顶点后从vi到vj的最短路径，也就是最终的解。

若Ak[i][j]已经求出且顶点i到顶点j的路径长度为Ak[i][j]，则顶点i到顶点k+1的路径长度为Ak[i][k+1]，顶点k+1到顶点j 的路径长度为Ak[k+1][j]。现在考虑顶点k+1，如图7-31所示，如果Ak[i][k+1]＋Ak[k+1][j]＜Ak[i][j]，则将原来顶点i到顶点j的路径改为：顶点i到顶点k+1，再由顶点k+1到顶点j；对应的路径长度为：Ak+1[i][j]＝Ak[i][k+1]＋Ak[k+1][j]；否则无需修改顶点i到顶点j的路径。

图7-31 若Ak[i][k+1]＋Ak[k+1][j]＜Ak[i][j]则修改路径

与Dijkstra算法类似，我们用二维数组path来保存最短路径，它与当前迭代的次数有关。在求Ak[i][j]时用path[i][j]来存放从顶点vi到顶点vj的中间顶点编号不大于k的最短路径上前一个顶点的编号。在算法结束时，由二维数组path的值向前查找就可得到从顶点vi到顶点vj的最短路径；若path[i][j]值为-1则表示没有中间顶点。

Floyd算法实现程序如下： #include

#define MAXSIZE 6 //带权有向图中顶点的个数 #define INF 32767

void Ppath(int path[][MAXSIZE],int i,int j)

{ //前向递归查找路径上的顶点，MAXV为常数 int k;

k=path[i][j];

if(k!=-1) //顶点vk不是起点 {

Ppath(path,i,k); //找顶点vi的前一个顶点vk printf(\ //输出顶点vk序号k

Ppath(path,k,j); //找顶点vk的前一个顶点vj } }

void Dispath(int A[][MAXSIZE],int path[][MAXSIZE],int n) { //输出最短路径的函数 int i,j;

for(i=0;i

if(A[i][j]==INF) //INF为一极大常数 { if(i!=j) printf(\从%d到%d没有路径!\\n\ else

{ //从vi到vj有最短路径

printf(\从%d到%d的路径长度:%d,路径:\ printf(\ //输出路径上的起点序号i Ppath(path,i,j); //输出路径上的各中间点序号 printf(\ //输出路径上的终点序号j } }

void Floyd(int gm[][MAXSIZE],int n) //Floyd算法 {

int A[MAXSIZE][MAXSIZE],path[MAXSIZE][MAXSIZE]; int i,j,k;

for(i=0;i

A[i][j]=gm[i][j]; //A-1[i][j]置初值

path[i][j]=-1; //初始时表示没有中间顶点 }

for(k=0;k

if(A[i][j]>A[i][k]+A[k][j]) {

A[i][j]=A[i][k]+A[k][j]; //从vi到vj经过vk时路径长度更短 path[i][j]=k; //记录中间顶点vk的编号 }

Dispath(gm,path,n); //输出最短路径 }

void main() {

int g[MAXSIZE][MAXSIZE]={{INF,20,15,INF,INF,INF},{2,INF,INF,INF,10,30},

{INF,4,INF,INF,INF,10},{INF,INF,INF,INF,INF,INF},{INF,INF,INF,15,INF,INF}, {INF,INF,INF,4,10,INF}}; //定义邻接矩阵g并给邻接矩阵g赋值 Floyd(g,MAXSIZE); //求每一对顶点之间的最短路径 }

【说明】

主函数main中已存放了图15-4所示的带权有向图，程序执行如下：

输出：从0到1的路径长度:20,路径:0,2,1

从0到2的路径长度:15,路径:0,2 从0到3没有路径! 从0到4没有路径! 从0到5没有路径!

从1到0的路径长度:2,路径:1,0 从1到2没有路径! 从1到3没有路径!

从1到4的路径长度:10,路径:1,4 从1到5的路径长度:30,路径:1,0,2,5 从2到0没有路径!

从2到1的路径长度:4,路径:2,1 从2到3没有路径! 从2到4没有路径!

从2到5的路径长度:10,路径:2,5 从3到0没有路径!

从3到1没有路径! 从3到2没有路径! 从3到4没有路径! 从3到5没有路径! 从4到0没有路径! 从4到1没有路径! 从4到2没有路径!

从4到3的路径长度:15,路径:4,3 从4到5没有路径! 从5到0没有路径! 从5到1没有路径! 从5到2没有路径!

从5到3的路径长度:4,路径:5,3 从5到4的路径长度:10,路径:5,4 Press any key to continue

5 拓扑排序和关键路径

5.1 AOV网与拓扑排序 1. AOV网

在工程中，一个大的工程通常被划分为许多较小的子工程，这些较小的子工程被称为活动；当这些子工程完成时整个工程也就完成了。我们可以用有向图来描述工程，即在有向图中以顶点来表示活动，用有向边（弧）表示活动之间的优先关系，并称这样的有向图为以顶点表示活动的网（Activity on vertex network），简称AOV网。

在AOV网中，若从顶点vi到顶点vj之间存在一条有向路径，则称顶点vi是顶点vj

的前驱，顶点vj是顶点vi的后继。若是网中的一条弧，则称顶点vi是顶点vj的直接前驱，顶点vj是顶点vi的直接后继。AOV网中的弧表示了活动之间的优先关系，也即前后制约关系。例如，计算机专业的学生必须完成一系列规定的基础课和专业课学习。学生按怎样的顺序来学习这些课程可以看作是一个大的工程，其活动就是学习每一门课程。这些课程的名称与相应的代号如表7.3所示。

表7.3 计算机专业课程设置及其关系

课程代号 C0 C1 C2 C3 C4 课程名称高等数学程序设计基础离散数学数据结构程序设计语言先修课程代号无无 C0, C1 C2, C4 C1 课程代号 C5 C6 C7 C8 课程名称编译原理操作系统普通物理计算机原理先修课程代号 C3, C4 C3, C8 C0 C7 表7.3 中，C0、C1是独立于其它课程的基础课，而学习其它课程时必须其先修的课

程均已学完，比如在学习过离散数学和程序设计语言课程后才能学习数据结构课程。这

些先修条件规定了各课程之间的优先关系；并且，这种优先关系可以用图7-32的有向图来表示；其中，顶点表示课程，有向边表示前提条件。若课程i为课程j的先修课程则必然存在有向边，在安排学习顺序时，必须保证在学习某门课程之前已经学习了该课程的全部先修课程。

图7-32 课程设置及其关系的AOV网

2. 拓扑排序

拓扑排序是将AOV网中所有顶点排成一个线性序列，该线性序列满足下述性质：（1）在AOV网中，若顶点vi到顶点vj有一条路径，则在该线性序列中顶点vi必定在顶点vj之前。

（2）对于网中没有路径的顶点vi与顶点vj，在线性序列中也建立了一个先后关系；或者顶点vi优先于顶点vj；或者顶点vj优先与顶点vi。

例如，我们对图7-32的AOV网进行拓扑排序，至少可得到如下两个（可有多个）拓扑序列：

（1） C0,C1,C2,C4,C3,C5,C7,C8,C6 （2） C0,C7,C8,C1,C4,C2,C3,C6,C5

注意，AOV网中不应该出现回路，否则意味着某项活动是以自身的任务完成为先决条件的，这显然是错误的。因此，检测一个工程是否可行必须先检查对应的AOV网是否存在回路；不存在回路的AOV网称为有向无环图或DAG（Directed Acycline Graph）图。检测是否存在回路的方法是对有向图构造其顶点的拓扑有序序列，若图中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在回路。图7-33给出了DAG图与有向图的区别。

图7-33 DAG图与有向图的区别

构造拓扑序列的过程称为拓扑排序，拓扑排序的序列可能不唯一。若某个AOV网中所有顶点都在它的拓扑序列中，则说明该AOV网不存在回路。显然，对于任何一项工程中各个活动的安排，必须按照拓扑序列中的顺序进行才是可行的。

3. 拓扑排序算法

假设AOV网代表一个工程计划，则AOV网的一个拓扑排序就是这个工程顺利完成的可行方案。对AOV网进行拓扑排序的算法如下：

（1）在AOV网中选择一个入度为零（没有前驱）的顶点输出。（2）删除AOV网中该顶点以及与该顶点有关的所有弧。（3）重复（1）、（2）直至网中不存在入度为零的顶点为止。如果算法结束时所有顶点均已输出，则整个拓扑排序完成并说明AOV网中不存在回路；否则表明AOV网中存在回路。图7-42给出了一个AOV网的拓扑排序过程，所得到的拓扑序列为：0,5,3,2,1,4。

图7-34 一个AOV网的拓扑排序过程

为了实现拓扑排序算法，对AOV网采用邻接表存储结构，但是在邻接表中的顶点结点里增加一个记录顶点入度的数据域，即顶点表结点结构为：

indegree vertex firstedge

其中，vertex、firstedge如7.2.2节邻接表所述，而indegree为记录顶点入度的数据域。邻接表结点也同7.2.2节所述。顶点表结点结构为：

typedef struct vnode /*顶点表结点*/ {

int indegree; /*顶点入度*/

int vertex; /*顶点域*/

EdgeNode *firstedge; /*指向邻接表第一个邻接边结点的指针域*/

}VertexNode; /*顶点表结点类型*/

算法中可设置一个堆栈，凡网中入度为0的顶点都将其入栈。拓扑排序的算法实现步骤为：

（1）将入度indegreee值为0（没有前驱）的顶点压栈。

（2）从栈中弹出栈顶元素（顶点）输出并删去该顶点所有的出边，即把它的各个邻接边结点的入度indegreee值减1。

（3）将新的入度indegreee值为0的顶点再压栈。

（4）重复（2）～（3）直到栈空为止。此时或者已经输出了AOV网的全部顶点；或者剩下的顶点中没有入度为0的顶点，即AOV网存在回路。

由上面的步骤可知：栈的作用只是保存当前入度为0的顶点，并使之处理有序；这种有序可以是先进后出，也可以是先进先出，因此也可以用队列实现。在下面算法实现中，并不真正设置一个栈空间来存放入度为0的顶点，而是设置一个栈顶位置指针top将当前所有未处理过的入度为0顶点链接起来，形成一个链栈。

拓扑排序算法实现程序如下： #include #include #define MAXSIZE 30

typedef struct node //邻接表结点 {

int adjvex; //邻接点域

struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int indegree; //顶点入度 int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n)

{//建立有向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 EdgeNode *p; int i,j,k;

printf(\

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 g[i].indegree=0; }

for(k=1;k<=e;k++) //输入e条边 {

printf(\ scanf(\

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p;

g[j].indegree=g[j].indegree+1; } }

void Top_Sort(VertexNode g[],int n) //拓扑排序

{//用带有入度域的邻接表存储AOV网并输出一种拓扑排序，n为顶点个数 int i,j,k,top,m=0; EdgeNode *p;

top=-1; //栈顶指针初始化，-1为链尾标志 for(i=0;i

g[i].indegree=top; top=i; }

while(top!=-1) //链栈不为空时 {

j=top; //取出栈顶入度为0的一个顶点（暂记为j） top=g[top].indegree; //栈顶指针指向弹栈后的下一个入度为0顶点 printf(\ //输出刚弹栈出来的顶点j信息

m++; //m记录已输出拓扑序列的顶点个数

p=g[j].firstedge;//根据顶点j的firstedge指针查其邻接表的第一个邻接边结点 while(p!=NULL) //删去顶点j的所有出边 {

k=p->adjvex;

g[k].indegree--; //将顶点j的邻接边结点k入度减1

if(g[k].indegree==0) //顶点k入度减1后若其值为0则将该顶点k链入链栈 {

g[k].indegree=top; top=k; }

p=p->next; //查找顶点j的下一个邻接边结点 } }

if(m

void main() {

int e,n;

VertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf(\ //输入图中结点个数 scanf(\

printf(\ //输入图中边的个数

scanf(\

printf(\

CreatAdjlist(g,e,n); //建立无向图的邻接表 printf(\

Top_Sort(g,n); //拓扑排序 printf(\}

【说明】

图15-5 AOV网示意

对图15-5所示的AOV网，程序执行如下：

输入： Input number of code:

9↙

Input number of edge: 11↙

Make adjlist:

Input date of vetex(0~n-1); Input edge of(i,j): 0,7↙ Input edge of(i,j): 0,2↙ Input edge of(i,j): 1,2↙ Input edge of(i,j): 1,4↙ Input edge of(i,j): 2,3↙ Input edge of(i,j): 4,3↙ Input edge of(i,j): 4,5↙ Input edge of(i,j): 7,8↙ Input edge of(i,j): 8,6↙ Input edge of(i,j): 3,6↙ Input edge of(i,j): 3,5↙

输出 Top Sort:

1,4,0,7,8,2,3,6,5,

Press any key to continue

5.2 AOE网与关键路径 1. AOE网

在带权有向图G中以顶点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则此带权有向图称为用边表示活动的网，简称AOE（Activity on edge network）网。

用AOE网表示一项工程计划时，顶点所表示的事件实际上就是指该顶点所有进入边（到达该顶点的边）所表示的活动均已完成，而该顶点的出发边所表示的活动均可开始的一种状态。AOE网中至少有一个开始顶点（称为源点），其入度为0；同时应有一个结束顶点（称为终点），其出度为0；网中不存在回路，否则整个工程将无法完成。

AOE网具有以下两个性质：

（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边（弧）所代表的活动才能开始。

（2）只有在进入某一顶点的各有向边（弧）所代表的活动都已结束，该顶点所代表的事件才能发生。

与AOV网不同，AOE网所关心的问题是：（1）完成该工程至少需要多少时间？

（2）哪些活动是影响整个工程进度的关键？

图7-37给出了AOE网示例。v0,v1,?,v8分别表示一个事件；< v0,v1>,< v0,v2>,?,< v7,v8>分别表示一个活动，我们用a0,a1,?,a10代表这些活动。v0是整个工程的开始点，称为源点且入度为0，v8是整个工程的结束点，称为终点且出度为0。

图7-37 AOE网示意

2. 关键路径与关键路径的确定

由于AOE网中的某些活动能够并行进行，所以完成整个工程所需的时间是从源点到终点的最大路径长度（此处的路径长度是指该路径上的各个活动所需时间之和）。具有最大路径长度的路径称为关键路径；关键路径上的所有活动均是关键活动；关键路径长度是整个工程的最短工期。缩短关键活动的时间可以缩短整个工程的工期。利用AOE网进行工程管理要解决的主要问题是：（1）计算完成整个工程的最短周期。

（2）确定关键路径以找出哪些活动是影响工程进度的关键。现将涉及关键活动的计算说明如下：（1）顶点事件的最早发生时间ve[k]

ve[k]是指从源点v0到顶点vk的最大路径长度（时间），这个时间决定了所有从顶点vk发出的弧所代表的活动能够开工的最早时间。根据AOE网的性质，只有进入vk的所有活动都结束时，vk代表的事件才能发生；而活动的最早结束时间为：ve[j]+dut。所以计算vk的最早发生时间公式如下： ve[0]=0 ve[k]=max{ve[j]+dut()} ∈p[k]，0≤j＜n-1

其中，p[k]表示所有到达vk的有向边的集合；dut 为弧上的权值。（2）顶点事件的最迟发生时间vl[k]

vl[k]是指在不推迟整个工程完成时间的前提下，事件vk所允许的最晚发生时间。对一个工程来说，计划用多长时间完成该工程可以从AOE网求得，其数值为终点vn-1的最早发生时间ve[n-1]，而这个时间同时也就是vl[n-1]；其余顶点事件的vl则应从终点开始逐步向源点方向递推求得。因此vl[k]的计算公式如下：

vl[n-1]=ve[n-1]

vl[k]=min{vl[j]-dut()} ∈s[k]，0≤j＜n-1

其中，s[k]为所有从vk出发的弧的集合。显然vl[j]的计算必须在顶点vj的所有后继顶点的最迟发生时间全部求出之后才能进行。（3）边活动ai的最早开始时间e[i]

e[i]是指该边所表示活动ai的最早开工时间。若活动ai是由弧表示，则根据AOE网的性质：只有事件vk发生了，活动ai才能开始。也就是说，活动ai的最早开始时间应等于顶点事件vk的最早发生时间，即有：

e[i]=ve[k] （4）边活动ai的最晚开始时间l[i]

l[i]是指在不推迟整个工程的完成时间这一前提下所允许的该活动最晚开始的时间。若活动ai由弧表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后，即有：

l[i]=v[j]-dut()

一个活动ai的最晚开始时间l[i]和最早开始时间e[i]的差额：d[i]=l[i]-e[i]是该活动ai

完成时间的余量，它是在不增加整个工程完成时间情况下，活动ai可以延迟的时间。若e[i]=l[i]，则表明活动ai最早可开工时间与整个工程计划允许活动ai的最晚开工时间一致，也即施工时间一点也不允许拖延，否则将延误工期；这也同时说明了活动ai是关键活动。

由关键活动组成的路径就是关键路径。按照上述计算关键活动的方法，就可以求出AOE网的关键路径。

3. 关键路径算法

根据关键路径的确定方法得到求关键路径算法的步骤如下：（1）输入e条弧，建立AOE网的存储结构；

（2）从源点v0出发并令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[i]（0≤i＜n）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在回路而无法求出关键路径，即算法终止；否则执行（3）。

（3）从终点vn-1出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间v[i]（n-2≥i＞0）。

（4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e[s]和最晚开始时间l[s]。若某条弧s满足e[s]=l[s]则为关键活动。

为了实现关键路径算法，对AOE网采用邻接表存储结构，邻接表中的顶点结点同7.2.2节所述，但邻接边结点结构为7.2.2节中图7-10所示的结构。邻接边结点结构为：

typedef stuct node {

int adjvex; /*邻接点域*/ int info; /*邻接边权值域*/

struct node *next; /*指向下一个邻接边结点的指针域*/ }EdgeNode;

下面算法中，Stack为栈的存储类型，函数FindInDegree(g,indegree)用于求AOE网中各顶点的入度，并将所求的入度存放于一维数组indegree中；T为拓扑序列顶点栈，S为零入度顶点栈。

关键路径算法实现程序如下： #include #include #define MAXSIZE 30

typedef struct node //邻接表结点 {

int adjvex; //邻接点域 int info;

struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int indegree; //顶点入度 int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 typedef struct {

char data[MAXSIZE]; int top; }SeqStack;

void Init_SeqStack(SeqStack **s) //栈初始化 {

*s=(SeqStack*)malloc(sizeof(SeqStack));//在主调函数中申请栈空间 (*s)->top=-1; //置栈空标志 }

int Empty_SeqStack(SeqStack *s) //判栈空 {

if(s->top==-1) //栈为空时 return 1; else

return 0; }

void Push_SeqStack(SeqStack *s,int x) //入栈 {

if(s->top==MAXSIZE-1)

printf(\ //栈已满 else {

s->top++;

s->data[s->top]=x; //元素x压入栈*s中 } }

void Pop_SeqStack(SeqStack *s,int *x) //出栈

{ //将栈*s中的栈顶元素出栈并通过参数x返回给主调函数 if(s->top==-1)

printf(\ //栈为空 else {

*x=s->data[s->top]; //栈顶元素出栈 s->top--; } }

void print(VertexNode g[],int ve[],int vl[],int n) {

int i,j,e,l,dut; char tag;

EdgeNode *p;

printf(\最早开始时间最晚开始时间关键活动\\n\ for(i=0;i

for(p=g[i].firstedge;p!=NULL;p=p->next) {

j=p->adjvex; dut=p->info; e=ve[i]; l=vl[j]-dut; tag=(e==l)?'*':' '; printf(\ }

for(i=0;i

void CreatAdjlist(VertexNode g[],int e,int n)

{//建立有向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 EdgeNode *p; int i,j,k,w;

printf(\

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 g[i].indegree=0; }

for(k=1;k<=e;k++) //输入e条边 {

printf(\ scanf(\

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->info=w; p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p;

g[j].indegree=g[j].indegree+1; } }

void Toplogicalorder(VertexNode g[], int n)

{//AOE网用邻接表存储，求各顶点事件的最早发生时间ve（为全局变量数组） int i,j,k,dut,count,*x=&j;

int ve[MAXSIZE],vl[MAXSIZE]; EdgeNode *p; SeqStack *s,*t;

Init_SeqStack(&s); //创建零入度顶点栈s Init_SeqStack(&t);

count=0; //顶点个数计数器，初值为0 for(i=0;i

for(i=0;i

Push_SeqStack(s,i);

while(!Empty_SeqStack(s)) //零入度顶点栈s不为空时 {

Pop_SeqStack(s,x); //弹出零入度顶点（暂记为j） Push_SeqStack(t,j); //将顶点j压入拓扑序列顶点栈t count++; //对进入栈t的顶点计数 p=g[j].firstedge;

//根据顶点j的firstedge指针查其邻接表中的第一个邻接边结点 while(p!=NULL) //删除顶点j的所有出边 {

k=p->adjvex;

g[k].indegree--; //顶点j的邻接边结点k的入度减1 if(g[k].indegree==0)

Push_SeqStack(s,k);//顶点k入度减1后若其值为0则压入零入度顶点栈s

if(ve[j]+p->info>ve[k])

ve[k]=ve[j]+p->info; //计算顶点事件的最早发生时间ve[k] p=p->next; //查找顶点j的下一个邻接边结点 } }

if(count

for(i=0;i

while(!Empty_SeqStack(t)) //按拓扑排序的逆序求各顶点的vl值 { Pop_SeqStack(t,x); //弹出拓扑序列顶点栈t中的顶点经由*x赋给j for(p=g[j].firstedge;p!=NULL;p=p->next) { //计算顶点事件的最迟发生时间vl[j] k=p->adjvex; dut=p->info; if(vl[k]-dut

print(g,ve,vl,n); L1: ; }

void main() {

int e,n;

VertexNode g[MAXSIZE]; //定义顶点表结点类型数组g printf(\ //输入图中结点个数 scanf(\

printf(\ //输入图中边的个数 scanf(\

printf(\

CreatAdjlist(g,e,n); //建立无向图的邻接表 Toplogicalorder(g,n); //拓扑排序并求出关键路径 printf(\} 【说明】

图15-6 AOE网示意

对图15-5所示的AOE网，程序执行如下：

输入： Input number of node:

9↙

Input number of edge: 11↙

Make adjlist:

Input date of vetex(0~n-1); Input edge of(i,j): 0,1↙ Input weight of (0,1): 6↙ Input edge of(i,j): 0,2↙ Input weight of (0,2): 4↙ Input edge of(i,j): 0,3↙ Input weight of (0,3): 5↙ Input edge of(i,j): 1,4↙ Input weight of (1,4): 1↙ Input edge of(i,j): 2,4↙ Input weight of (2,4): 1↙ Input edge of(i,j): 3,7↙ Input weight of (3,7): 2↙ Input edge of(i,j): 4,5↙ Input weight of (4,5): 9↙ Input edge of(i,j): 4,6↙ Input weight of (4,6): 7↙ Input edge of(i,j): 7,8↙ Input weight of (7,8): 4↙ Input edge of(i,j): 5,8↙ Input weight of (5,8): 2↙ Input edge of(i,j): 6,8↙ Input weight of (6,8): 4↙

输出： (vi,vj) dut 最早开始时间最晚开始时间关键活动

(0,3) 5 0 7 (0,2) 4 0 2

(0,1) 6 0 0 * (1,4) 1 6 6 *

(2,4) 1 4 6 (3,7) 2 5 12

(4,6) 7 7 7 * (4,5) 9 7 7 * (5,8) 2 16 16 * (6,8) 4 14 14 * (7,8) 4 7 14

顶点0的最早发生时间和最迟发生时间: 0 0 顶点1的最早发生时间和最迟发生时间: 6 6 顶点2的最早发生时间和最迟发生时间: 4 6 顶点3的最早发生时间和最迟发生时间: 5 12 顶点4的最早发生时间和最迟发生时间: 7 7 顶点5的最早发生时间和最迟发生时间: 16 16 顶点6的最早发生时间和最迟发生时间: 14 14 顶点7的最早发生时间和最迟发生时间: 7 14 顶点8的最早发生时间和最迟发生时间: 18 18

Press any key to continue

6 图的应用

6.1 邻接矩阵转换为邻接表

程序如下：

#include #include #define MAXSIZE 30

typedef struct //图在顺序存储结构下的类型定义 {

char vertex[MAXSIZE]; //顶点为字符型且顶点表的长度小于MAXSIZE int edges[MAXSIZE] [MAXSIZE]; //边为整型且edges为邻接矩阵 }MGraph; // MGraph为采用邻接矩阵存储的图类型 typedef struct node //邻接表结点 {

int adjvex; //邻接点域

struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatMGraph(MGraph *g,int e,int n)

{ //建立无向图的邻接矩阵g->egdes，n为顶点个数，e为边数 int i,j,k;

printf(\ for(i=0;i

g->vertex[i]=i; //读入顶点信息

for(i=0;i

g->edges[i][j]=0; //初始化邻接矩阵 for(k=1;k<=e;k++) //输入e条边 {

printf(\ scanf(\ g->edges[i][j]=1; g->edges[j][i]=1; } }

void Graphlinklist(MGraph *G,int n, VertexNode g[]) //邻接矩阵转换为邻接表 {

EdgeNode *p; int i,j;

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 }

for(i=0;i

if(G->edges[i][j]!=0) //邻接矩阵中边(i,j)存在 {

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p; } }

int visited[MAXSIZE]; //MAXSIZE为大于或等于无向图顶点个数的常量 void DFS(VertexNode g[],int i) {

EdgeNode *p;

printf(\ //输出顶点i信息，即访问顶点i visited[i]=1; //置顶点i为访问过标志 p=g[i].firstedge;

//根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=NULL) //当邻接边结点不为空时 {

if(!visited[p->adjvex]) //如果邻接的这个边结点未被访问过 DFS(g,p->adjvex); //对这个边结点进行深度优先搜索 p=p->next; //查找顶点i的下一个邻接边结点 } }

void DFSTraverse(VertexNode g[],int n)

{//深度优先搜索遍历以邻接表存储的图，其中g为顶点表，n为顶点个数

int i;

for(i=0;i

visited[i]=0; //访问标志置0

for(i=0;i

void main() { int i,j,n,e; MGraph *g;

VertexNode g1[MAXSIZE]; g=(MGraph *)malloc(sizeof(MGraph)); //生成邻接矩阵的存储空间 printf(\输入邻接矩阵的大小（即图的顶点数） scanf(\

printf(\ //输入图中边的个数 scanf(\

CreatMGraph(g,e,n); //生成图的邻接矩阵 printf(\ ///输出该图对应的邻接矩阵 for(i=0;i

Graphlinklist(g,n,g1); //将邻接矩阵转化为邻接表 printf(\

DFSTraverse(g1,n); //深度优先遍历以邻接表存储的无向图 printf(\}

6.2 求无向连通图中距顶点v0路径长度为k的所有结点

程序中必须用广度优先遍历的层次特性来求解，也即要以v0为起点调用BFS算法输出第k+1层上的所有顶点。因此，在访问顶点时需要知道层数，而每个顶点的层数是由其前驱决定的（起点除外）。所以，可以从第一个顶点开始，每访问到一个顶点就根据其前驱的层次计算该顶点的层次，并将层数值与顶点编号一起入队、出队。实际上可增加一个队列来保存顶点的层数值，并且将层数的相关操作与对应顶点的操作保持同步，即一起置空、出队和入队。实现程序如下： #include #include #define MAXSIZE 30 typedef struct node {

int data;

struct node *next; }QNode; //链队列结点类型

typedef struct {

QNode *front,*rear; //将头、尾指针纳入到一个结构体的链队列 }LQueue; //链队列类型

void Init_LQueue(LQueue **q) //创建一个带头结点的空队列 {

QNode *p;

int Empty_LQueue(LQueue *q) //判队空 {

if(q->front==q->rear) //队为空 return 1; else

return 0; }

void In_LQueue(LQueue *q,int x) //入队 {

QNode *p;

p=(QNode *)malloc(sizeof(QNode)); //申请新链队列结点 p->data=x;

p->next=NULL; //新结点作为队尾结点时其next域为空 q->rear->next=p; //将新结点*p链到原队尾结点之后 q->rear=p; //使队尾指针指向新的队尾结点*p }

void Out_LQueue(LQueue *q,int *x) //出队 {

QNode *p;

if(Empty_LQueue(q))

printf(\ //队空，出队失败 else {

p=q->front->next; //指针p指向链队列第一个数据结点（即队头结点） q->front->next=p->next;

//头结点的next指针指向链队列第二个数据结点（即删除第一个数据结点） *x=p->data; //将删除的队头结点数据经由x返回 free(p);

if(q->front->next==NULL) //出队后队为空，则置为空队列 q->rear=q->front; } }

typedef struct node1 //邻接表结点 {

int adjvex; //邻接点域

struct node1 *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n)

{//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 EdgeNode *p; int i,j,k;

printf(\

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 }

for(k=1;k<=e;k++) //输入e条边 {

printf(\ scanf(\

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=j; //在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge; //插入是在邻接表表头进行的 g[i].firstedge=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->adjvex=i; //在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge; //插入是在邻接表表头进行的 g[j].firstedge=p; } }

int visited[MAXSIZE];

void BFS_klevel(VertexNode g[],int v0,int k,int n)

{ //查找从顶点v0开始路径长度为k的所有结点 int i,j,*x=&j,level,*y=&level; EdgeNode *p; LQueue *Q,*Q1;

Init_LQueue(&Q); //队列Q初始化 Init_LQueue(&Q1); //队列Q1初始化

for(i=0;i

visited[v0]=1; //对起点v0置访问过标志 level=1; //置v0的层数为1 In_LQueue(Q,v0); //顶点v0进入队列Q

In_LQueue(Q1,level); //顶点v0的层数进入队列Q1

while(!Empty_LQueue(Q)&&level

{

Out_LQueue(Q,x); //队头的顶点出队并经x赋给j（暂记为顶点j） Out_LQueue(Q1,y); //队头顶点的层数出队并经y赋给level p=g[j].firstedge; //p指向刚出队的顶点j的第一个邻接边结点 while(p!=NULL) //p不为空时 {

if(!visited[p->adjvex]) //若该邻接边结点未访问过 {

if(level==k) //若该邻接边结点层数为k

printf(\ \输出该邻接边结点信息 visited[p->adjvex]=1; //置该邻接边结点已访问过标志 In_LQueue(Q,p->adjvex); //该邻接边结点入队Q

In_LQueue(Q1,level+1); //该邻接边结点的层数入队Q1 }

p=p->next; //在顶点j的邻接表中查找j的下一个邻接边结点 } } }

void main() {

int e,k,n;

VertexNode g[MAXSIZE];

printf(\ //输入图的顶点个数 scanf(\

printf(\ //输入图的边数 scanf(\

printf(\ //生成图的邻接表 CreatAdjlist(g,e,n);

printf(\ //输入路径长度 scanf(\

BFS_klevel(g,0,k,n); //查找从顶点0开始路径长度为k的所有结点 printf(\}

6.3 用深度优先搜索对图中所有顶点进行拓扑排序

对无向图来说，若深度优先遍历过程中遇到回边则必定存在环；而对有向图来说，这条回边有可能是指向深度优先森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v出发进行遍历，并在DFS(v)结束之前出现一条从顶点u到顶点v的回边，因u在生成树上是v的子孙，而此时又出现v是u的子孙，所以在有向图中必定存在包含顶点v和顶点u的环。

实现程序如下： #include #include #define MAXSIZE 30

typedef struct node //邻接表结点 {

int adjvex; //邻接点域

struct node *next; //指向下一个邻接边结点的指针域 }EdgeNode; //邻接表结点类型 typedef struct vnode //顶点表结点 {

int indegree; //顶点入度 int vertex; //顶点域

EdgeNode *firstedge; //指向邻接表第一个邻接边结点的指针域 }VertexNode; //顶点表结点类型 void CreatAdjlist(VertexNode g[],int e,int n)

{//建立有向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点 EdgeNode *p; int i,j,k;

printf(\

for(i=0;i

g[i].vertex=i; //读入顶点i信息

g[i].firstedge=NULL; //初始化指向顶点i的邻接表表头指针 g[i].indegree=0; }

for(k=1;k<=e;k++) //输入e条边 {