数据结构第八章：图

Abstract：图。

8.1 图的基本概念

图状结构：比树形结构更复杂的非线性结构。

• 结点间的邻接关系任意
• 用于描述各种复杂的数据对象

8.1.1 图的定义和术语

1.图的定义

图（Graph）：由非空顶点集合 + 一个描述顶点间关系——边的集合组成；形式化定义为：G = （V，E）；V = {vi| vi ∈ dataobject}; E = {(vi, vj) | vi ∈ V ∧P(vi, vj)}; G表示图，V是顶点的集合，E是边的集合。

2.图的相关术语：

• 无向图：(vi, vj)无序；
• 有向图：（vi, vj）∈E 有序；
• 顶点：vi
• 边：（vi, vj），一般称无向图中的连线为边
• 弧：有序偶对表示，一般称有向图中的连线为弧
• 始点/弧尾：有序偶对的第一个结点vi，在图中就是不带箭头的一端
• 终点/弧头: 有序偶对的第二个结点vj 被称为终点（或弧头），在图中就是带箭头的一端
• 有向完全图：任意两顶点之间都有方向互反的两条弧相连接；在一个含有n 个顶点的有向完全图中，有n(n-1)条边。
• 无向完全图：无向图中，任意两顶点都有一条直接边相连接；在一个含有n 个顶点的无向完全图中，有n(n-1)/2 条边。
• 稠密图、稀疏图：若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图。
• 权weight：与边有关的数据信息
• 网图/网络network：边上带权的图
• 路径：顶点vp 到顶点vq 之间的路径（path）是指顶点序列vp,vi1,vi2, …,vim,vq.。其中，（vp,vi1），(vi1,vi2)，…,(vim,.vq)分别为图中的边。路径上边的数目称为路径长度。
• 简单路径：序列中顶点不重复出现的路径
• 简单回路(环)：除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路
• 子图：对于图G=（V，E），G’=（V’，E’），若存在V’是V 的子集，E’是E的子集，则称图G’是G 的一个子图。

• 连通的、连通图、连通分量。在无向图中，如果从一个顶点vi 到另一个顶点vj(i≠j)有路径，则称顶点vi 和vj 是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量。
• 强连通图、强连通分量：对于有向图来说，若图中任意一对顶点vi 和vj(i≠j)均有从一个顶点vi 到另一个顶点vj 有路径，也有从vj 到vi 的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。
• 生成树：连通图G 的生成树，是G 的包含其全部n 个顶点的一个极小连通子图；必定包含且仅包含G 的n-1 条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。
• 生成森林。在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。

8.1.2 图的基本操作

（1） CreatGraph（G）输入图G 的顶点和边，建立图G 的存储。
（2）DestroyGraph（G）释放图G 占用的存储空间。
（3）GetVex（G，v）在图G 中找到顶点v，并返回顶点v 的相关信息。
（4）PutVex（G，v，value）在图G 中找到顶点v，并将value 值赋给顶点v。
（5）InsertVex（G，v）在图G 中增添新顶点v。
（6）DeleteVex（G，v）在图G 中，删除顶点v 以及所有和顶点v 相关联的边或弧。
（7）InsertArc（G，v，w）在图G 中增添一条从顶点v 到顶点w 的边或弧。
（8）DeleteArc（G，v，w）在图G 中删除一条从顶点v 到顶点w 的边或弧。
（9）DFSTraverse（G，v）在图G 中，从顶点v 出发深度优先遍历图G。
（10）BFSTtaverse（G，v）在图G 中，从顶点v 出发广度优先遍历图G。
在一个图中，顶点是没有先后次序的，但当采用某一种确定的存储方式存储后，存储结构中顶点的存储次序构成了顶点之间的相对次序，这里用顶点在图中的位置表示该顶点的存储顺序；同样的道理，对一个顶点的所有邻接点，采用该顶点的第i 个邻接点表示与该顶点相邻接的某个顶点的存储顺序，在这种意义下，图的基本操作还有：

（11）LocateVex（G，u）在图G 中找到顶点u，返回该顶点在图中位置。
（12）FirstAdjVex（G，v）在图G 中，返回v 的第一个邻接点。若顶点在G 中没有邻接顶点，则返回“空”。
（13）NextAdjVex（G，v，w）在图G 中，返回v 的（相对于w 的）下一个邻接顶点。若w 是v 的最后一个邻接点，则返回“空”。

8.1.2 图的基本操作

（1） CreatGraph（G）输入图G 的顶点和边，建立图G 的存储。
（2）DestroyGraph（G）释放图G 占用的存储空间。
（3）GetVex（G，v）在图G 中找到顶点v，并返回顶点v 的相关信息。
（4）PutVex（G，v，value）在图G 中找到顶点v，并将value 值赋给顶点v。
（5）InsertVex（G，v）在图G 中增添新顶点v。
（6）DeleteVex（G，v）在图G 中，删除顶点v 以及所有和顶点v 相关联的边或弧。
（7）InsertArc（G，v，w）在图G 中增添一条从顶点v 到顶点w 的边或弧。
（8）DeleteArc（G，v，w）在图G 中删除一条从顶点v 到顶点w 的边或弧。
（9）DFSTraverse（G，v）在图G 中，从顶点v 出发深度优先遍历图G。
（10）BFSTtaverse（G，v）在图G 中，从顶点v 出发广度优先遍历图G。
在一个图中，顶点是没有先后次序的，但当采用某一种确定的存储方式存储后，存储结构中顶点的存储次序构成了顶点之间的相对次序，这里用顶点在图中的位置表示该顶点的存储顺序；同样的道理，对一个顶点的所有邻接点，采用该顶点的第i 个邻接点表示与该顶点相邻接的某个顶点的存储顺序，在这种意义下，图的基本操作还有：

（11）LocateVex（G，u）在图G 中找到顶点u，返回该顶点在图中位置。
（12）FirstAdjVex（G，v）在图G 中，返回v 的第一个邻接点。若顶点在G 中没有邻接顶点，则返回“空”。
（13）NextAdjVex（G，v，w）在图G 中，返回v 的（相对于w 的）下一个邻接顶点。若w 是v 的最后一个邻接点，则返回“空”。

8.1.2 图的基本操作

（1） CreatGraph（G）输入图G 的顶点和边，建立图G 的存储。
（2）DestroyGraph（G）释放图G 占用的存储空间。
（3）GetVex（G，v）在图G 中找到顶点v，并返回顶点v 的相关信息。
（4）PutVex（G，v，value）在图G 中找到顶点v，并将value 值赋给顶点v。
（5）InsertVex（G，v）在图G 中增添新顶点v。
（6）DeleteVex（G，v）在图G 中，删除顶点v 以及所有和顶点v 相关联的边或弧。
（7）InsertArc（G，v，w）在图G 中增添一条从顶点v 到顶点w 的边或弧。
（8）DeleteArc（G，v，w）在图G 中删除一条从顶点v 到顶点w 的边或弧。
（9）DFSTraverse（G，v）在图G 中，从顶点v 出发深度优先遍历图G。
（10）BFSTtaverse（G，v）在图G 中，从顶点v 出发广度优先遍历图G。
在一个图中，顶点是没有先后次序的，但当采用某一种确定的存储方式存储后，存储结构中顶点的存储次序构成了顶点之间的相对次序，这里用顶点在图中的位置表示该顶点的存储顺序；同样的道理，对一个顶点的所有邻接点，采用该顶点的第i 个邻接点表示与该顶点相邻接的某个顶点的存储顺序，在这种意义下，图的基本操作还有：

（11）LocateVex（G，u）在图G 中找到顶点u，返回该顶点在图中位置。
（12）FirstAdjVex（G，v）在图G 中，返回v 的第一个邻接点。若顶点在G 中没有邻接顶点，则返回“空”。
（13）NextAdjVex（G，v，w）在图G 中，返回v 的（相对于w 的）下一个邻接顶点。若w 是v 的最后一个邻接点，则返回“空”。

8.1.2 图的基本操作

（1） CreatGraph（G）输入图G 的顶点和边，建立图G 的存储。
（2）DestroyGraph（G）释放图G 占用的存储空间。
（3）GetVex（G，v）在图G 中找到顶点v，并返回顶点v 的相关信息。
（4）PutVex（G，v，value）在图G 中找到顶点v，并将value 值赋给顶点v。
（5）InsertVex（G，v）在图G 中增添新顶点v。
（6）DeleteVex（G，v）在图G 中，删除顶点v 以及所有和顶点v 相关联的边或弧。
（7）InsertArc（G，v，w）在图G 中增添一条从顶点v 到顶点w 的边或弧。
（8）DeleteArc（G，v，w）在图G 中删除一条从顶点v 到顶点w 的边或弧。
（9）DFSTraverse（G，v）在图G 中，从顶点v 出发深度优先遍历图G。
（10）BFSTtaverse（G，v）在图G 中，从顶点v 出发广度优先遍历图G。
在一个图中，顶点是没有先后次序的，但当采用某一种确定的存储方式存储后，存储结构中顶点的存储次序构成了顶点之间的相对次序，这里用顶点在图中的位置表示该顶点的存储顺序；同样的道理，对一个顶点的所有邻接点，采用该顶点的第i 个邻接点表示与该顶点相邻接的某个顶点的存储顺序，在这种意义下，图的基本操作还有：

（11）LocateVex（G，u）在图G 中找到顶点u，返回该顶点在图中位置。
（12）FirstAdjVex（G，v）在图G 中，返回v 的第一个邻接点。若顶点在G 中没有邻接顶点，则返回“空”。
（13）NextAdjVex（G，v，w）在图G 中，返回v 的（相对于w 的）下一个邻接顶点。若w 是v 的最后一个邻接点，则返回“空”。

8.2 图的存储表示——邻接矩阵

图的信息：包括图中顶点的信息以及描述顶点之间的关系――边或者弧的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。

邻接矩阵Adjacency Matrix：一维数组表示各顶点的邻接关系，矩阵表示各顶点的邻接关系；假设图G＝（V，E）有n 个确定的顶点，即V＝{v0,v1,…,vn-1},则表示G 中各顶点相邻关系为一个n×n 的矩阵，矩阵的元素为：

wij 表示边(vi,vj)或上的权值；∞表示一个计算机允许的、大于所有边上权值的数。

邻接矩阵特点：

① 无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。
② 对于无向图，邻接矩阵的第i 行（或第i 列）非零元素（或非∞元素）的个数正好是第i 个顶点的度TD(vi)。
③ 对于有向图，邻接矩阵的第i 行（或第i 列）非零元素（或非∞元素）的个数正好是第i 个顶点的出度OD(vi)（或入度ID(vi)）。
④用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。

在用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外还有图的顶点数和边数。故可将其形式描述如下：

#define MaxVertexNum 100                                        /*最大顶点数设为100*/
typedef char	VertexType;                                     /*顶点类型设为字符型*/
typedef int	EdgeType;                                       /*边的权值设为整型*/
typedef struct {
	VertexType	vexs[MaxVertexNum];                     /*顶点表*/
	EdeType		edges[MaxVertexNum][MaxVertexNum];      /*邻接矩阵，即边表*/
	int		n, e;                                   /*顶点数和边数*/
}Mgragh;                                                        /*Maragh 是以邻接矩阵存储的图类型*/
建立 一 个 图的邻接矩阵存储的算法如 ：
void CreateMGraph( MGraph *G )
{                                                               /*建立有向图G 的邻接矩阵存储*/
	int	i, j, k, w;
	char	ch;
	printf( "请输入顶点数和边数(输入格式为:顶点数,边数):\n" );
	scanf( "%d,%d", &(G->n), &(G->e) );                     /*输入顶点数和边数*/
	printf( "请输入顶点信息(输入格式为:顶点号<CR>):\n" );
	for ( i = 0; i < G->n; i++ )
		scanf( "\n%c", &(G->vexs[i]) );                 /*输入顶点信息，建立顶点表*/
	for ( i = 0; i < G->n; i++ )
		for ( j = 0; j < G->n; j++ )
			G->edges[i][j] = 0;
	                                                        /*初始化邻接矩阵*/
	printf( "请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n" );
	for ( k = 0; k < G->e; k++ )
	{
		scanf( "\n%d,%d", &i, &j );                     /*输入e 条边，建立邻接矩阵*/
		G->edges[i][j] = 1;                             /*若加入G->edges[j][i]=1;，*/
/*则为无向图的邻接矩阵存储建立*/
	}
} /*CreateMGraph*/

8.2 图的存储表示—邻接表

邻接表(Adjacency List)：图的一种顺序存储与链式存储结构组合的存储方法。类似树的孩子链表表示法。

• 对于图G 中的每个顶点vi，将所有邻接于vi 的顶点vj 链成一个单链表，这个单链表就称为顶点vi 的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。

一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成，另一种是边表（即邻接表）结点，它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。对于网图的边表需再增设一个存储边上信息（如权值等）的域（info），网图的边表结构如图：

＃ define MaxVerNum 100                                                                  /*最大顶点数为100*/
typedef struct node {                                                                   /*边表结点*/
	int		adjvex;                                                         /*邻接点域*/
	struct node	* next;                                                         /*指向下一个邻接点的指针域*/
/*若要表示边上信息，则应增加一个数据域info*/
}EdgeNode;
typedef struct vnode {                                                                  /*顶点表结点*/
	VertexType	vertex;                                                         /*顶点域*/
	EdgeNode	* firstedge;                                                    /*边表头指针*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];                                               /*AdjList 是邻接表类型*/
typedef struct {
	AdjList adjlist;                                                                /*邻接表*/
	int	n, e;                                                                   /*顶点数和边数*/
}ALGraph;                                                                               /*ALGraph 是以邻接表方式存储的图类型*/
建立 一 个 向 图的邻接表存储的算法如 ：
void CreateALGraph( ALGraph *G )
{                                                                                       /*建立有向图的邻接表存储*/
	int		i, j, k;
	EdgeNode	* s;
	printf( "请输入顶点数和边数(输入格式为:顶点数,边数)：\n" );
	scanf( "%d,%d", &(G->n), &(G->e) );                                             /*读入顶点数和边数*/
	printf( "请输入顶点信息(输入格式为:顶点号<CR>)：\n" );
	for ( i = 0; i < G->n; i++ )                                                    /*建立有n 个顶点的顶点表*/
	{
		scanf( "\n%c", &(G->adjlist[i].vertex) );                               /*读入顶点信息*/
		G->adjlist[i].firstedge = NULL;                                         /*顶点的边表头指针设为空*/
	}
	printf( "请输入边的信息(输入格式为:i,j)：\n" );
	for ( k = 0; k < G->e; k++ )                                                    /*建立边表*/
	{
		scanf( "\n%d,%d", &i, &j );                                             /*读入边<Vi,Vj>的顶点对应序号*/
		s			= (EdgeNode *) malloc( sizeof(EdgeNode) );      /*生成新边表结点s*/
		s->adjvex		= j;                                            /*邻接点序号为j*/
		s->next			= G->adjlist[i].firstedge;                      /*将新边表结点s 插入到顶点Vi 的边表头部*/
		G->adjlist[i].firstedge = s;
	}
} /*CreateALGraph*/

若无向图中有n 个顶点、e 条边，则它的邻接表需n 个头结点和2e 个表结点。显然，在边稀疏(e<<n(n-1)/2)的情况下，用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。

在无向图的邻接表中，顶点vi 的度恰为第i 个链表中的结点数；而在有向图中，第i个链表中的结点个数只是顶点vi 的出度，为求入度，必须遍历整个邻接表。在所有链表中其邻接点域的值为i 的结点的个数是顶点vi 的入度。有时，为了便于确定顶点的入度或以顶点vi 为头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi 建立一个链接以vi为头的弧的链表。例如图8.12 所示为有向图G2（图8.2）的邻接表和逆邻接表。

在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的复杂度为O（n+e），否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O（n·e）。

在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点（vi 和vj）之间是否有边或弧相连，则需搜索第i 个或第j 个链表，因此，不及邻接矩阵方便。

8.2 图的存储表示—十字链表

十字链表（Orthogonal List）是有向图的一种存储方法，它实际上是邻接表与逆邻接表的结合，即把每一条边的边结点分别组织到以弧尾顶点为头结点的链表和以弧头顶点为头顶点的链表中。在十字链表表示中，顶点表和边表的结点结构分别如图：

在弧结点中有五个域：其中尾域(tailvex)和头(headvex)分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink 指向弧头相同的下一条弧，链域tlink 指向弧尾相同的下一条弧，info 域指向该弧的相关信息。弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。它们的头结点即为顶点结点，它由三个域组成：其中vertex 域存储和顶点相关的信息，如顶点的名称等；firstin 和firstout 为两个链域，分别指向以该顶点为弧头或弧尾的第一个弧结点。

十字链表形式描述：

#define MAX_VERTEX_NUM 20
typedef struct ArcBox {
	int		tailvex, headvex;       /*该弧的尾和头顶点的位置*/
	struct ArcBox	* hlink, tlink; / 分 别 为 弧 头 相 和 弧 尾 相 财 的 弧 的链域 * /
	InfoType info;                          /*该弧相关信息的指针*/
}ArcBox;
typedef struct VexNode {
	VertexType vertex :
	ArcBox fisrin, firstout;                /*分别指向该顶点第一条入弧和出弧*/
}VexNode;
typedef struct {
	VexNode xlist[MAX_VERTEX_NUM];          /*表头向量*/
	int	vexnum, arcnum;                 /*有向图的顶点数和弧数*/
}OLGraph;

下面给出建立一个有向图的十字链表存储的算法。通过该算法，只要输入n 个顶点的信息和e 条弧的信息，便可建立该有向图的十字链表，其算法内容如下。

void CreateDG(LOGraph **G)
/*采用十字链表表示，构造有向图G(G.kind=DG)*/
{ scanf (&(*G->brcnum),&(*G->arcnum),&IncInfo); /*IncInfo 为0 则各弧不含其实信息*/
for (i=0;i<*G->vexnum;++i) /*构造表头向量*/
{ scanf(&(G->xlist[i].vertex)); /*输入顶点值*/
*G->xlist[i].firstin=NulL;*G->xlist[i].firstout =NULL; /*初始化指针*/
}
for(k=0;k<G.arcnum;++k) /*输入各弧并构造十字链表*/
{ scanf(&v1,&v2); /*输入一条弧的始点和终点*/
i=LocateVex(*G,v1); j=LocateVex(*G,v2); /*确定v1 和v2 在G 中位置*/
p=(ArcBox*) malloc (sizeof(ArcBox)); /*假定有足够空间*/
*p={ i,j,*G->xlist[j].fistin,*G->xlist[i].firstout,NULL} /*对弧结点赋值*/
/*{tailvex,headvex,hlink,tlink,info}*/
*G->xlist[j].fisrtin=*G->xlist[i].firstout=p; /*完成在入弧和出弧链头的插入*/
if (IncInfo) Input( p->info); /*若弧含有相关信息，则输入*/
}
}/*CreateDG*/

在十字链表中既容易找到以为尾的弧，也容易找到以vi 为头的弧，因而容易求得顶点的出度和入度（或需要，可在建立十字链表的同时求出）。同时，由上述算法可知，建立十字链表的时间复杂度和建立邻接表是相同的。在某些有向图的应用中，十字链表是很有用的工具。

8.3 图的遍历

图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。

由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：

① 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。

图的遍历通常有深度优先搜索和广度优先搜索两种方式。

8.3.1 深度优先搜索（Depth_Fisrst Search）

深度优先搜索（Depth_Fisrst Search）遍历类似于树的先根遍历，是树的先根遍历的推广。

访问过程：

• 假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点发v 出发，访问此顶点
• 然后依次从v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到；
• 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止【递归过程】。

为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[0:n-1], ，其初值为FALSE ，一旦某个顶点被访问，则其相应的分量置为TRUE。

从图的某一点v 出发，递归地进行深度优先遍历的过程如算法8.4 所示。
void DFS(Graph G,int v )
{ /*从第v 个顶点出发递归地深度优先遍历图G*/
visited[v]=TRUE;VisitFunc(v); /*访问第v 个顶点*/
for(w=FisrAdjVex(G,v);w; w=NextAdjVex(G,v,w))
if (!visited[w]) DFS(G,w); /*对v 的尚未访问的邻接顶点w 递归调用DFS*/
}
算法8.4

算法8.5 和算法8.6 给出了对以邻接表为存储结构的整个图G 进行深度优先遍历实现的C 语言描述。

void DFSTraverseAL(ALGraph *G)
{/*深度优先遍历以邻接表存储的图G*/
int i;
for (i=0;i<G->n;i++)
visited[i]=FALSE; /*标志向量初始化*/
for (i=0;i<G->n;i++)
if (!visited[i]) DFSAL(G,i); /*vi 未访问过，从vi 开始DFS 搜索*/
}/*DFSTraveseAL*/
算法8.5

void DFSAL(ALGraph *G,int i)
{/*以Vi 为出发点对邻接表存储的图G 进行DFS 搜索*/
EdgeNode *p;
printf("visit vertex:V%c\n",G->adjlist[i].vertex);/*访问顶点Vi*/
visited[i]=TRUE; /*标记Vi 已访问*/
p=G->adjlist[i].firstedge; /*取Vi 边表的头指针*/
while(p) /*依次搜索Vi 的邻接点Vj，j=p->adjva*/
{if (!visited[p->adjvex]) /*若Vj 尚未访问，则以Vj 为出发点向纵深搜索*/
DFSAL(G,p->adjvex);
p=p->next; /*找Vi 的下一个邻接点*/
}
}/*DFSAL*/
算法8.6

分析上述算法，在遍历时，对图中每个顶点至多调用一次DFS 函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。

其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O(n2) ，其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e) 。

8.3.2 广度优先搜索（Breadth_First Search）

• 类似于树的按层次遍历的过程（一个层次遍历完再遍历下一个层次）
• 假设从图中某顶点v 出发，在访问了v 之后依次访问v 的各个未曾访问过和邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到
• 广度优先搜索遍历图的过程中以v 为起始点，由近至远，依次访问和v 有路径相通且路径长度为1,2,…的顶点。

和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1、2、… 的顶点。

从图的某 一 点v 出发 递 归地进行 广 度 优 先遍历的过 如算法8 .7 所 示 。
void BFSTraverse( Graph G, Status (*Visit)( int v ) )
{                                                       /*按广度优先非递归遍历图G。使用辅助队列Q 和访问标志数组visited*/
	for ( v = 0; v < G, vexnum; ++v )
		visited[v] = FALSE
			     InitQueue( Q );            /*置空的国债队列Q*/
	if ( !visited[v] )                              /*v 尚未访问*/
	{
		EnQucue( Q, v );                        /*v 入队列*/
		while ( !QueueEmpty( Q ) )
		{
			DeQueue( Q, u );                /*队头元素出队并置为u*/
			visited[u] = TRUE; visit( u );  /*访问u*/
			for ( w = FistAdjVex( G, u ); w; w = NextAdjVex( G, u, w ) )
				if ( !visited[w] )
					EnQueue( Q, w );
			                                /*u 的尚未访问的邻接顶点w 入队列Q*/
		}
	}
} /*BFSTraverse*/


算法8 .7

算法8 .8 和算法8 .9 给出了对以邻接矩阵 为 存储结构的整 个 图G 进行深度 优 先遍历实现的C 语 言 描述 。
void BFSTraverseAL( MGraph *G )
{                                                                               /*广度优先遍历以邻接矩阵存储的图G*/
	int i;
	for ( i = 0; i < G->n; i++ )
		visited[i] = FALSE;                                             /*标志向量初始化*/
	for ( i = 0; i < G->n; i++ )
		if ( !visited[i] )
			BFSM( G, i );
	                                                                        /* vi 未访问过，从vi 开始BFS 搜索*/
} /*BFSTraverseAL*/


算法8 .8

void BFSM( MGraph *G, int k )
{                                                                               /*以Vi 为出发点，对邻接矩阵存储的图G 进行BFS 搜索*/
	int		i, j;
	CirQueue	Q;
	InitQueue( &Q );
	printf( "visit vertex:V%c\n", G->vexs[k] );                             /*访问原点Vk*/
	visited[k] = TRUE;
	EnQueue( &Q, k );                                                       /*原点Vk 入队列*/
	while ( !QueueEmpty( &Q ) )
	{
		i = DeQueue( &Q );                                              /*Vi 出队列*/
		for ( j = 0; j < G->n; j++ )                                    /*依次搜索Vi 的邻接点Vj*/
			if ( G->edges[i][j] == 1 && !visited[j] )               /*若Vj 未访问*/
			{
				printf( "visit vertex:V%c\n", G->vexs[j] );     /*访问Vj */
				visited[j] = TRUE;
				EnQueue( &Q, j );                               /*访问过的Vj 入队列*/
			}
	}
} /*BFSM*/


算法8 .9

分析上述算法，每个顶点至多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。

8.4 图的连通性——无向图的连通性

在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

要想判定一个无向图是否为连通图，或有几个连通分量，就可设一个计数变量count，初始时取值为0，在算法8.5 的第二个for 循环中，每调用一次DFS，就给count 增1。这样，当整个算法结束时，依据count 的值，就可确定图的连通性了。

8.4 图的连通性—有向图的连通性

连通图

• 在无向图中，如果一个顶点到另一个顶点存在至少一条路径，称它们之间是连通的。 如果图中任意两个顶点之间都是连通的，则此图为连通图。
• 如果一个图本身不是连通图，但是图中某个子图是连通图，那么这个子图又被称为“连通分量”。
• 注意：这里的“子图”指的是无向图中最大的连通子图。
• 在有向图中，如果任意一对顶点 Vi 和 Vj，从 Vi 到 Vj 和从 Vj 到 Vi 都含有至少一条通路，那么称此图为强连通图。如果有向图的连通分量也具有此特征，则为强连通分量。

有向图的连通性不同于无向图的连通性，可分为弱连通、单侧连通和强连通。

深度优先搜索是求有向图的强连通分量的一个有效方法。假设以十字链表作有向图的存储结构，则求强连通分量的步骤如下：

（1）在有向图G 上，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成(即退出DFS 函数)的顺序将顶点排列起来。此时需对8.3.1中的算法作如下两点修改：（a）在进入DFSTraverseAL 函数时首先进行计数变量的初始化，即在入口处加上count=0 的语句；（b）在退出函数之前将完成搜索的顶点号记录在另一个辅助数组finished[vexnum] 中，即在函数DFSAL 结束之前加上finished[++count]=v 的语句。

（2）在有向图G 上，从最后完成搜索的顶点（即finished[vexnum-1]中的顶点）出发，沿着以该顶点为头的弧作逆向的深度搜索遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先搜索遍历，依次类推，直至有向图中所有顶点都被访问到为止。此时调用DFSTraverseAL 时需作如下修改：
函数中第二个循环语句的边界条件应改为v 从finished[vexnum-1]至finished[0]。

由此，每一次调用DFSAL 作逆向深度优先遍历所访问到的顶点集便是有向图G 中一个强连通分量的顶点集。

上述求强连通分量的第二步，其实质为：
（1）构造一个有向图Gr，设G=(V,{A})，则Gr=(Vr，{Ar})对于所有< vi,,vj>∈A，必有< vj, vi >∈Ar。即Gr 中拥有和G 方向相反的弧；
（2）在有向图Gr 上，从顶点finished[vexnum-1] 出发作深度优先遍历。可以证明，在Gr 上所得深度优先生成森林中每一棵树的顶点集即为G 的强连通分量的顶点集。

显然，利用遍历求强连通分量的时间复杂度亦和遍历相同。

8.4 图的连通性—生成树和生成森林

对于非连通图，通过这样的遍历，将得到的是生成森林。例如，图8.20 (b) 所示为图8.20 (a)的深度优先生成森林，它由三棵深度优先生成树组成。

假设以孩子兄 弟 链表 作 生 成 森林的存储结构 则 算法8 .10 生 成 非 连 通 图的深度 优 先 生 成 森林 其 中 DFSTree 函数如算法8 .11 所 示 。 显 然 算法8 .10 的时间 杂度和遍历相 。
void DESForest( Graph G, CSTree *T )
{                                                                                       /*建立无向图G 的深度优先生成森林的孩子兄弟链表T*/
	T = NULL;
	for ( v = 0; v < G.vexnum; ++v )
		if ( !visited[v] = FALSE;
		     for ( v = 0; v < G.vexnum; ++v )
			     if ( !visited[v] )                                         /*顶点v 为新的生成树的根结点*/
			     {
				     p = (CSTree) malloc( sixeof( CSNode ) );           /*分配根结点*/
				     p = { GetVex( G, v ).NULL, NULL };                 /*给根结点赋值*/
				     if ( !T )
					     (*T) = p;                                  /*T 是第一棵生成树的根*/
				     else q->nextsibling = p;                           /*前一棵的根的兄弟是其它生成树的根*/
				     q = p;                                             /*q 指示当前生成树的根*/
				     DFSTree( G, v, &p );                               /*建立以p 为根的生成树*/
			     }
		     }
		     算法8 .10

		     void DFSTree( Graph G, int v, CSTree * T )
		     {                                                                  /*从第v 个顶点出发深度优先遍历图G，建立以*T 为根的生成树*/
			     visited[v] = TRUE;
			     first = TRUE;
			     for ( w = FirstAdjVex( G, v ); w; w = NextAdjVex( G, v, w ) )
				     if ( !visited[w] )
				     {
					     p = (CSTree) malloc( sizeof ) CSNode) );   /*分配孩子结点*/
					     *p = { GetVex( G, w ), NULL, NULL };
					     if ( first )                               /*w 是v 的第一个未被访问的邻接顶点，作为根的左孩子结点*/
					     {
						     T->lchild = p;
						     first = FALSE;
					     }else  {                                   /*w 是v 的其它未被访问的邻接顶点，作为上一邻接顶点的右兄弟*/
						     q->nextsibling = p;
					     }
					     q = p;
					     DFSTree( G, w, &q );                       /*从第w 个顶点出发深度优先遍历图G，建立生成子树*q*/
				     }
		     }

8.4 图的连通性—关节点和重连通分量

关节点：假若在删去顶点v 以及和v 相关联的各边之后，将图的一个连通分量分割成两个或两个以上的连通分量，则称顶点v 为该图的一个关节点(articulation point) 。关节点亦称为割点。

一个没有关节点的连通图称为重连通图(biconnected graph) 。在重连通图上，任意一对顶点之间至少存在两条路径，则在删去某个顶点以及依附于该顶点的各边时也不破坏图的连通性。若在连通图上至少删去k 个顶点才能破坏图的连通性，则称此图的连通度为k。

一个表示通信网络的图的连通度越高，其系统越可靠，无论是哪一个站点出现故障或遭到外界破坏，都不影响系统的正常工作；又如，一个航空网若是重连通的，则当某条航线因天气等某种原因关闭时，旅客仍可从别的航线绕道而行；再如，若将大规模的集成电路的关键线路设计成重连通的话，则在某些元件失效的情况下，整个片子的功能不受影响，反之，在战争中，若要摧毁敌方的运输线，仅需破坏其运输网中的关节点即可。

求关节点的时间复杂度为O（n+e）。

利用深度优先搜索便可求得图的关节点，并由此可判别图是否是重连通的。

图8.21 (b)所示为从顶点A 出发深优先生成树，图中实线表示树边，虚线表示回边（即不在生成树上的边）。对树中任一顶点v 而言，其孩子结点为在它之后搜索到的邻接点，而其双亲结点和由回边连接的祖先结点是在它之前搜索到的邻接点。由深度优先生成树可得出两类关节点的特性：

（1）若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点。因为图中不存在联结不同子树中顶点的边，因此，若删去根顶点，生成树便变成生成森林。如图8.21(b)中的顶点A。
（2）若生成树中某个非叶子顶点v，其某棵子树的根和子树中的其它结点均没有指向v 的祖先的回边，则v 为关节点。因为，若删去v，则其子树和图的其它部分被分割开来。如图8.21(b)中的顶点B 和G 。

若对图Graph＝(V，{Edge}) 重新定义遍历时的访问函数visited，并引入一个新的函数low，则由一次深度优先遍历便可求得连通图中存在的所有关节点。

8.5 最小生成树—最小生成树的基本概念

• 无向连通图的生成树不唯一
• 连通图的一次遍历所经过的边的集合及图中所有顶点的集合 = 构成一棵生成树
• 对连通图的不同遍历可得到不同生成树

对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。

最小生成树：权值总和最小。

8.5 最小生成树—构造最小生成树的Prim算法

假设G＝（V，E）为一网图，其中V 为网图中所有顶点的集合，E 为网图中所有带权边的集合。设置两个新的集合U 和T，其中集合U 用于存放G 的最小生成树中的顶点，集合T 存放G 的最小生成树中的边。令集合U 的初值为U＝{u1}（假设构造最小生成树时，从顶点u1 出发），集合T 的初值为T＝{}。

Prim 算法的思想是，从所有u∈U，v∈V－U 的边中，选取具有最小权值的边（u，v），将顶点v 加入集合U 中，将边（u，v）加入集合T 中，如此不断重复，直到U＝V 时，最小生成树构造完毕，这时集合T 中包含了最小生成树的所有边。

图8.23 (a)所示的一个网图，按照Prim 方法，从顶点1 出发，该网的最小生成树的产生过程如图8.23 (b)、(c)、(d)、(e)、(f)和(g)所示。

为实现Prim 算法，需设置两个辅助一维数组lowcost 和closevert，其中lowcost 用来保存集合V－U 中各顶点与集合U 中各顶点构成的边中具有最小权值的边的权值；数组closevertex 用来保存依附于该边的在集合U 中的顶点。假设初始状态时，U＝{u1}(u1 为出发的顶点)，这时有lowcost[0]=0，它表示顶点u1 已加入集合U 中，数组lowcost 的其它各分量的值是顶点u1 到其余各顶点所构成的直接边的权值。然后不断选取权值最小的边（ui，uk）（ui∈U，uk∈V－U），每选取一条边，就将lowcost（k）置为0，表示顶点uk 已加入集合U 中。由于顶点uk 从集合V－U 进入集合U 后，这两个集合的内容发生了变化，就需依据具体情况更新数组lowcost 和closevertex 中部分分量的内容。最后closevertex 中即为所建立的最小生成树。

当无 向 网采 用二维数组存储的邻接矩阵存储时 Prim 算法的C 语 言 实现 为 ：
	 void Prim （ int gm[] [MAXNODE] int n int closevertex[]
	 {                                      /*用Prim 方法建立有n 个顶点的邻接矩阵存储结构的网图gm 的最小生成树*/
/*从序号为0 的顶点出发；建立的最小生成树存于数组closevertex 中*/
		 int lowcost[100], mincost;
		 int i, j, k;
		 for ( i = 1; i < n; i++ )      /*初始化*/
		 {
			 lowcost[i] = gm[0][i];
			 closevertex[i] = 0;
		 }
		 lowcost[0] = 0;                /*从序号为0 的顶点出发生成最小生成树*/
		 closevertex[0] = 0;
		 for ( i = 1; i < n; i++ )      /*寻找当前最小权值的边的顶点*/
		 {
			 mincost = MAXCOST;     /*MAXCOST 为一个极大的常量值*/
			 j = 1; k = 1;
			 while ( j < n )
			 {
				 if ( lowcost[j] < mincost && lowcost[j] != 0 )
				 {
					 mincost = lowcost[j];
					 k = j;
				 }
				 j++;
			 }
			 printf( “ 顶点的序号 ＝ % d 边的权 值 ＝ % d \ n ”, k, mincost );
			 lowcost[k] = 0;
			 for ( j = 1; j < n; j++ ) /*修改其它顶点的边的权值和最小生成树顶点序号*/
				 if ( gm[k][j] < lowcost[j] )
				 {
					 lowcost[j] = gm[k][j];
					 closevertex[j] = k;
				 }
		 }
	 }

图8.24 给出了在用上述算法构造网图8.23 (a)的最小生成树的过程中，数组closevertex、lowcost 及集合U，V－U 的变化情况，读者可进一步加深对Prim 算法的了解。

在Prim 算法中，第一个for 循环的执行次数为n－1，第二个for 循环中又包括了一个while 循环和一个for 循环，执行次数为2(n-1)2，所以Prim 算法的时间复杂度为O(n2)。

8.5 最小生成树—构造最小生成树的Kruskal算法

Kruskal 算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。

其基本思想是：设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G 的边集E 中的各条边。若被考察的边的两个顶点属于T 的两个不同的连通分量，则将此边作为最小生成树的边加入到T 中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。

n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。

设置一个结构数组Edges 存储网中所有的边，边的结构类型包括构成的顶点信息和边权值，定义如下：

#define MAXEDGE <图中的最大边数>
typedef struct {
elemtype v1;
elemtype v2;
int cost;
} EdgeType;
EdgeType edges[MAXEDGE];

下面用C 语言实现Kruskal 算法，其中函数Find 的作用是寻找图中顶点所在树的根结点在数组father 中的序号。需说明的是，在程序中将顶点的数据类型定义成整型，而在实际应用中，可依据实际需要来设定。
typedef int elemtype;
typedef struct {
	elemtype	v1;
	elemtype	v2;
	int		cost;
}EdgeType;
void Kruskal （ EdgeType edges[]  int n
/*用Kruskal 方法构造有n 个顶点的图edges 的最小生成树*/
{ int	father[MAXEDGE];
  int	i, j, vf1, vf2;
  for ( i = 0; i < n; i++ )
	  father[i] = -1;
  i = 0; j = 0;
  while ( i < MAXEDGE && j < n - 1 )
  {
	  vf1	= Find( father, edges[i].v1 );
	  vf2	= Find( father, edges[i].v2 );
	  if ( vf1 != vf2 )
	  {
		  father[vf2] = vf1;
		  j++;
		  printf( “ % 3d % 3d \ n ”, edges[i].v1, edges[i].v2 );
	  }
	  i++;
  }
}
算法8 .15

int Find （ int father[]  int v
/*寻找顶点v 所在树的根结点*/
{ int t;
  t = v;
  while ( father[t] >= 0 )
	  t = father[t];
  return(t); }

在Kruskal 算法中，第二个while 循环是影响时间效率的主要操作，其循环次数最多为MAXEDGE 次数，其内部调用的Find 函数的内部循环次数最多为n，所以Kruskal 算法的时间复杂度为O（n·MAXEDGE）。

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

网图中：边的权值之和最短的路径为最短路径；

非网图中：两点间经历的边数最少的路径。

一般情况下，下一条长度次短的最短路径的长度必是：

        D[j]=Min{D[i]| vi∈V-S}

其中，D[i] 或者弧（v, vi）上的权值，或者是D[k]( vk∈S 和弧（vk, vi）上的权值之和。

根据以上分析，可以得到如下描述的算法：

（1）假设用带权的邻接矩阵edges 来表示带权有向图，edges[i][j] 表示弧〈vi, vj〉上的权值。若〈vi, vj〉不存在，则置edges[i][j]为∞（在计算机上可用允许的最大值代替）。S 为已找到从v 出发的最短路径的终点的集合，它的初始状态为空集。那么，从v 出发到图上其余各顶点（终点）vi 可能达到最短路径长度的初值为：
D[i]= edges[Locate Vex(G,v)][i] vi∈V

（2）选择vj，使得
D[j]=Min{D[i]| vi∈V-S}
vj 就是当前求得的一条从v 出发的最短路径的终点。令
S＝S∪{j}

（3）修改从v 出发到集合V-S 上任一顶点vk 可达的最短路径长度。如果
D[j]+ edges[j][k]<D[k]
则修改D[k]为
D[k]=D[j]+ edges[j][k]
重复操作（2）、（3）共n-1 次。由此求得从v 到图上其余各顶点的最短路径是依路径长度递增的序列。

void ShortestPath_1( Mgraph G, int v0, PathMatrix *p, ShortPathTable *D )
{       /*用Dijkstra 算法求有向网G 的v0 顶点到其余顶点v 的最短路径P[v]及其路径长度D[v]*/
/*若P[v][w]为TRUE，则w 是从v0 到v 当前求得最短路径上的顶点*/
/*final[v] 为TRUE 当且仅当v∈S, ，即已经求得从v0 到v 的最短路径*/
/*常量INFINITY 为边上权值可能的最大值*/
	for ( v = 0; v < G.vexnum; ++v )
	{
		fianl[v] = FALSE; D[v] = G.edges[v0][v];
		for ( w = 0; w < G.vexnum; ++w )
			P[v][w] = FALSE;                                        /*设空路径*/
		if ( D[v] < INFINITY )
		{
			P[v][v0] = TRUE; P[v][w] = TRUE;
		}
	}
	D[v0] = 0; final[v0] = TRUE ；                                           /*初始化，v0 顶点属于S 集*/
/*开始主循环，每次求得v0 到某个v 顶点的最短路径，并加v 到集*/
			       for ( i = 1; i < G.vexnum; ++i )                 /*其余G.vexnum-1 个顶点*/
	{
		min = INFINITY;                                                 /*min 为当前所知离v0 顶点的最近距离*/
		for ( w = 0; w < G.vexnum; ++w )
			if ( !final[w] )                                        /*w 顶点在V－S 中*/
				if ( D[w] < min )
				{
					v = w; min = D[w];
				}
		final[v] = TRUE                                                 /*离v0 顶点最近的v 加入S 集合*/
			   for ( w = 0; w > G.vexnum; ++w )                     /*更新当前最短路径*/
			if ( !final[w] && (min + G.edges[v][w] < D[w]) )        /*修改D[w]和P[w],w∈V-S*/
			{
				D[w]	= min + G.edges[v][w];
				P[w]	= P[v]; P[w][v] = TRUE;                 /*P[w]=P[v]+P[w]*/
			}
	}
} /*ShortestPath._1*/

下面分析一下这个算法的运行时间。第一个for 循环的时间复杂度是O(n)，第二个for循环共进行n-1 次，每次执行的时间是O(n)。所以总是的时间复杂度是O(n2)。如果用带权的邻接表作为有向图的存储结构，则虽然修改D 的时间可以减少，但由于在D 向量中选择最小的分量的时间不变，所以总的时间仍为O(n2)。

如果只希望找到从源点到某一个特定的终点的最短路径，但是，从上面我们求最短路径的原理来看，这个问题和求源点到其它所有顶点的最短路径一样复杂，其时间复杂度也是O(n2)。

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

解决这个问题的一个办法是：每次以一个顶点为源点，重复招待迪杰斯特拉算法次。这样，便可求得每一结顶点的最短路径。总的执行时间为O(n3)。

这里要介绍由弗洛伊德(Floyd)提出的另一个算法。这个算法的时间复杂度也是O(n3),但形式上简单些。

弗洛伊德算法仍从图的带权邻接矩阵cost 出发，其基本思想是：
假设求从顶点vi 到vj 的最短路径。如果从vi 到vi 有弧，则从vi 到vj 存在一条长度为edges[i][j]的路径，该路径不一定是最短路径，尚需进行n 次试探。首先考虑路径（vi, v0,vj）是否存在（即判别弧（vi, v0）和(v0, vj)是否存在）。如果存在，则比较（vi, vj）和（vi,v0, vj）的路径长度取长度较短者为从vi 到vj 的中间顶点的序号不大于0 的最短路径。假如在路径上再增加一个顶点v1，也就是说，如果（vi, …, v1）和（v1, …, vj）分别是当前找到的中间顶点的序号不大于0 的最短路径，那么（vi, …, v1, … , vj） 就有可能是从vi 到vj 的中间顶点的序号不大于1 的最短路径。将它和已经得到的从vi 到vj 中间顶点序号不大于0 的最短路径相比较，从中选出中间顶点的序号不大于1 的最短路径之后，再增加一个顶点v2，继续进行试探。依次类推。在一般情况下，若（vi, …, vk）和（vk, …, vj）
分别是从vi 到vk 和从vk 到vj 的中间顶点的序号不大于k-1 的最短路径，则将（vi, …,vk, …, vj）和已经得到的从vi 到vj 且中间顶点序号不大于k-1 的最短路径相比较，其长度较短者便是从vi 到vj 的中间顶点的序号不大于k 的最短路径。这样，在经过n 次比较后，最后求得的必是从vi 到vj 的最短路径。

按此方法，可以同时求得各对顶点间的最短路径。

现定义一个n 阶方阵序列。
D(-1)，D(0)，D(1)，…，D(k)，D(n-1)
其中
D(-1)[i][j]=edges[i][j]
D( k)[i][j]=Min{D( k-1)[i][j], D( k-1)[i][k]+D( k-1)[k][j]} 0≦k≦n-1

从上述计算公式可见，D(1)[i][j]是从vi 到vj 的中间顶点的序号不大于1 的最短路径的长度；D( k)[i][j] 是从vi 到vj 的中间顶点的个数不大于k 的最短路径的长度；D( n-1)[i][j] 就是从vi 到vj 的最短路径的长度。

由 此得到求任 意 两顶点间的 最 短路径的算法8 .18 。
void ShortestPath_2( Mgraph G, PathMatrix *P[], DistancMatrix *D )
{                                                       /*用Floyd 算法求有向网G 中各对顶点v 和w 之间的最短路径P[v][w]及其带权长度D[v][w]。*/
/*若P[v][w][u]为TRUE，则u 是从v 到w 当前求得的最短路径上的顶点。*/
	for ( v = 0; v < G.vexnum; ++v )                /*各对顶点之间初始已知路径及距离*/
		for ( w = 0; w < G, vexnum; ++w )
		{
			D[v][w] = G.arcs[v][w];
			for ( u = 0; u < G, vexnum; ++u )
				P[v][w][u] = FALSE;
			if ( D[v][w] < INFINITY )       /*从v 到w 有直接路径*/
			{
				P[v][w][v] = TRUE;
			}
		}
	for ( u = 0; u < G.vexnum; ++u )
		for ( v = 0; v < G.vexnum; ++v )
			for ( w = 0; w < G.vexnum; ++w )
				if ( D[v][u] + D[u][w] < D[v][w] ) /*从v 经u 到w 的一条路径更短*/
				{
					D[v][w] = D[v][u] + D[u][w];
					for ( i = 0; i < G.vexnum; ++i )
						P[v][w][i] = P[v][u][i] || P[u][w][i];
				}
} /* ShortestPath_2*/

图8.28 给出了一个简单的有向网及其邻接矩阵。图8.29 给出了用Floyd 算法求该有向网中每对顶点之间的最短路径过程中，数组D 和数组P 的变化情况。

8.7 有向无环图（DAG）及其应用—有向无环图的概念

有向无环图是描述含有公共子式的表达式的有效工具。例如下述表达式：

    ((a+b)*(b*(c+d)+(c+d)*e)*((c+d)*e)

可以用第六章讨论的二叉树来表示，如图8.31 所示。仔细观察该表达式，可发现有一些相同的子表达式，如(c+d)和(c+d)*e 等，在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。例如图8.32 所示为表示同一表达式的有向无环图。

检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环；而对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v 出发的遍历，在dfs(v)结束之前出现一条从顶点u 到顶点v 的回边，由于u 在生成树上是v 的子孙，则有向图必定存在包含顶点v 和u 的环。

有向无环图是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外，几乎所有的工程（project）都可分为若干个称作活动（activity）的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。

对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行：二是估算整个工程完成所必须的最短时间。以下两小节将详细介绍这样两个问题是如何通过对有向图进行拓扑排序和关键路径操作来解决的。

8.7 有向无环图及其应用—AOV网（(Activity on vertex network)）与拓扑排序

1．AOV网(Activity on vertex network)

所有的工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。若以图中的顶点来表示活动，有向边表示活动之间的优先关系，则这样活动在顶点上的有向图称为AOV 网。在AOV 网中，若从顶点i 到顶点j 之间存在一条有向路径，称顶点i 是顶点j 的前驱，或者称顶点j 是顶点i 的后继。若是图中的弧，则称顶点i是顶点j 的直接前驱，顶点j 是顶点i 的直接后驱。

AOV 网中的弧表示了活动之间存在的制约关系。例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业。学生按照怎样的顺序来学习这些课程呢？这个问题可以被看成是一个大的工程，其活动就是学习每一门课程。这些课程的名称与相应代号如表8.1 所示。

表中，C1、C12 是独立于其它课程的基础课，而有的课却需要有先行课程，比如，学完程序设计导论和数值分析后才能学数据结构……，先行条件规定了课程之间的优先关系。这种优先关系可以用图8.33 所示的有向图来表示。其中，顶点表示课程，有向边表示前提条件。若课程i 为课程j 的先行课，则必然存在有向边〈i,j〉。在安排学习顺序时，必须保证在学习某门课之前，已经学习了其先行课程。

类似的AOV 网的例子还有很多，比如大家熟悉的计算机程序，任何一个可执行程序也可以划分为若干个程序段（或若干语句），由这些程序段组成的流程图也是一个AOV 网。

2．拓扑排序

偏序与全序：

• 若集合A 中的二元关系R 是自反的、非对称的和传递的，则R 是A 上的偏序关系。集合A 与关系R 一起称为一个偏序集合。
• 若R 是集合A 上的一个偏序关系，如果对每个a、b∈A 必有aRb 或bRa ，则R 是A上的全序关系。集合A 与关系R 一起称为一个全序集合。

偏序关系经常出现在我们的日常生活中。例如，若把A 看成一项大的工程必须完成的一批活动，则aRb 意味着活动a 必须在活动b 之前完成。比如，对于前面提到的计算机专业的学生必修的基础课与专业课，由于课程之间的先后依赖关系，某些课程必须在其它课程以前讲授，这里的aRb 就意味着课程a 必须在课程b 之前学完。

AOV 网所代表的一项工程中活动的集合显然是一个偏序集合。为了保证该项工程得以顺利完成，必须保证AOV 网中不出现回路；否则，意味着某项活动应以自身作为能否开展的先决条件，这是荒谬的。测试AOV 网是否具有回路（即是否是一个有向无环图）的方法，就是在AOV 网的偏序集合下构造一个线性序列，该线性序列具有以下性质：

1、在AOV 网中，若顶点i 优先于顶点j ，则在线性序列中顶点i 仍然优先于顶点j；
2、对于网中原来没有优先关系的顶点与顶点，如图8.33 中的C1 与C13，在线性序列中也建立一个先后关系，或者顶点i 优先于顶点j ，或者顶点j 优先于i。

满足这样性质的线性序列称为拓扑有序序列。构造拓扑序列的过程称为拓扑排序。也可以说拓扑排序就是由某个集合上的一个偏序得到该集合上的一个全序的操作。

若某个AOV 网中所有顶点都在它的拓扑序列中，则说明该AOV 网不会存在回路，这时的拓扑序列集合是AOV 网中所有活动的一个全序集合。以图8.21 中的AOV 网例，可以得到不止一个拓扑序列，C1、C12、C4、C13、C5、C2、C3、C9、C7、C10、C11、C6、C8 就是其中之一。显然，对于任何一项工程中各个活动的安排，必须按拓扑有序序列中的顺序进行才是可行的。

3.拓扑排序算法

对AOV 网进行拓扑排序的方法和步骤是：
1、从AOV 网中选择一个没有前驱的顶点（该顶点的入度为0）并且输出它；
2、从网中删去该顶点，并且删去从该顶点发出的全部有向边；
3、重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。

这样操作的结果有两种：一种是网中全部顶点都被输出，这说明网中不存在有向回路；另一种就是网中顶点未被全部输出，剩余的顶点均不前驱顶点，这说明网中存在有向回路。

这样得到一个拓扑序列：v2,v5,v1,v4,v3,v7,v6。

为了实现上述算法，对AOV 网采用邻接表存储方式，并且邻接表中顶点结点中增加一个记录顶点入度的数据域，即顶点结构设为：

顶点表结点结构的描述改为：
typedef struct vnode{ /顶点表结点/
int count /存放顶点入度/
VertexType vertex; /顶点域/
EdgeNode firstedge; /边表头指针*/
}VertexNode;

当然也可以不增设入度域，而另外设一个一维数组来存放每一个结点的入度。算法中可设置了一个堆栈，凡是网中入度为0 的顶点都将其入栈。为此，拓扑排序的算法步骤为：
1、将没有前驱的顶点（count 域为0）压入栈；
2、从栈中退出栈顶元素输出，并把该顶点引出的所有有向边删去，即把它的各个邻接顶点的入度减1；
3、将新的入度为0 的顶点再入堆栈；
4、重复②～④，直到栈为空为止。此时或者是已经输出全部顶点，或者剩下的顶点中没有入度为0 的顶点。

下面给出用C 语言描述的拓扑排序算法的实现。

从上面的步骤可以看出，栈在这里的作用只是起到一个保存当前入度为零点的顶点，并使之处理有序。这种有序可以是后进先出，也可以是先进先出，故此也可用队列来辅助实现。在下面给出用C 语言描述的拓扑排序的算法实现中，我们采用栈来存放当前未处理过的入度为零点的结点，但并不需要额外增设栈的空间，而是设一个栈顶位置的指针将当前所有未处理过的入度为零的结点连接起来，形成一个链式栈。

void Topo_Sort( AlGraph *G )
{                                               /*对以带入度的邻接链表为存储结构的图G，输出其一种拓扑序列*/
	int top = -1 ；                          /* 栈顶指针初始化*/
		  for ( i = 0 ； i < n ； i++ )   /* 依次将入度为0 的顶点压入链式栈*/
	{
		if ( G->adjlist[i].Count = = 0 )
		{
			G->adjlist[i].count			= top ；
							  top	= i ；
		}
	}
	for ( i = 0; i < n; i++ )
	{
		if ( t0p = -1 )
		{
			printf( “ The network has a cycle ” );
			return;
		}
		j	= top;
		top	= G->adjlist[top].count;                /* 从栈中退出一个顶点并输出*/
		printf( “ % c ”, G->adjlist[j].vertex );
		ptr = G->adjlist[j].firstedge;
		while ( ptr != null )
		{
			k = ptr->adjvex;
			G->adjlist[k].count--;                  /*当前输出顶点邻接点的入度减1*/
			if ( G->adjlist[k].count = = 0 )        /*新的入度为0 的顶点进栈*/
			{
				G->adjlist[k].count	= top;
				top			= k;
			}
			ptr = ptr->next;                        /*找到下一个邻接点*/
		}
	}
}

算法8.19

对一个具有n 个顶点、e 条边的网来说，整个算法的时间复杂度为O（e+n）。下面结合图8.34 (a)给出的AOV 网以及图8.35 所示的邻接表，观察算法的执行情况。

图8.36 给出了邻接表的顶点结点的变化情况。其中，图8.36 (a)示出了算法开始时堆栈的初始状态；图8.36（b）～（h）给出了每输出一个顶点后堆栈的状态。