一、图的定义

在图形结构中，结点之间的关系可以是任意的，图中任意两个元素之间都可能相关。

图：图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为:G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

对于图的定义，我们需要明确注意以下地方：

• 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex)。
• 在图结构中不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷且非空。
• 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层之间具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

1.1 各种图的定义

1.1.1 无向图

无向边:若顶点Vi到Vj为之间的边没有方向，则称这条边为无向边(Edge)，用无序偶对(Vi,Vj)来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图(Undirected graphs)。如图就是一个无向图，由于是无方向的，连接顶点A与D的边，可以表示成无序对(A,D)，也可以写成(D,A)。
对于无向图G1来说，G1=(V1,{E1}),其中定点集合V1 = {A,B,C,D}; 边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}

1.1.2 有向图

有向边：若从定点vi到vj的边有方向，则称这条边为有向边，也称为弧(Arc)。
用有序偶<Vi,Vj>来表示，Vi 称为弧尾，Vj称为弧头。如果图中任意两个定点之间的边都是有向边，则称该图为有向图(Directed graphs)。如图就是一个有向图。连接定点A到D的有向边就是弧，A就是弧尾，D就是弧头，<A,D>表示弧，注意不能写成<D,A>。

对于有向图G2来说，G2=(V2,{E2})，其中顶点集合V2={A,B,C,D};弧集合E2={<A,D>,<B,A>,<C,A>,<B,C>}。

1.1.3 简单图

在途中，若不存在定点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

这两个图都不属于简单图。

1.1.4 无向完全图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有(n*(n-1))/2条边。

如图就是无向完全图，因为每个顶点都要与除它自身以外的顶点相连，顶点A与BCD三个顶点连线，一共有四个顶点，自然是4x3，但由于顶点A与顶点B连线之后，计算B与A连线就是重复，因此要除整体除以2，共有6条边。

1.1.5 有向完全图

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有nx(n-1)条边。

从这也可以得到结论，对于具有n个顶点和e条边数的图，无向图0≤e≤nx(n-1)/2，有向图0≤e≤nx(n-1)。

1.1.6 其他图

• 有很少条边或弧的图称为稀疏图，反之称为稠密图。
• 有些图的边或弧具有与它相关的数字，这种与图的边或好相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或者耗费。这种带权的图通常称为网（Network）。
  
• 假设有两个图G=(V,{E})和G'=(V',{E'})，如果V'∈V，且E'∈E，则称G'为G的子图（Subgraph）。如图。
  

1.2 图的顶点与边间关系

• 路径的长度是路劲上的边或弧的数目。
• 第一个顶点到最后一个顶点相同的路径称为回路或者环。
• 序列中顶点不重复出现的路径称为简单路径。
• 除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或者简单环。如图，两个图的粗线都构成环，左侧的环因第一个顶点和最后一个顶点都是B，且C、D、A 没有重复出现，因此是一个简单环。而右侧的环，由于顶点C的重复，它就不是简单环了。
  

1.3 连通图相关术语

在无向图 G中，如果从顶点v到顶点v‘有路径，则称v和v'是连通的。如果对于图中任意两个顶点Vi、Vj ∈ E，vi和vj都是连通的，则称G是连通图(Connected Graph)。
图1，它的顶点A到顶点 B、C、D 都是连通的，但显然顶点 A与顶点E或F就无路径，因此不能算是连通图。而图2，顶点A、B、C、D 相互都是连通的，所以它本身是连通图。

无向图中的极大连通子图称为连通分量。注意连通分量的概念，它强调:

• 要是子图;
• 子图要是连通的;
• 连通子图含有极大顶点数;
• 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
  在有向图 G 中，如果对于每一对Vi、Vj ∈ V、Vi ≠ Vj,从 Vi 到 Vj 和从 Vj 到 Vi 都存在路径，则称 G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
  
  所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的 n-1 条边。图1 是一普通图，但显然不是生成树，当去掉两条构成环，比如图 2 和图3，就满足 n 个顶点 n-1 条边且连通的定义。它们都是一棵生成树。从这里也可知道，如果一个图有n 个顶点和小于 n-1 条边，则非连通图，如果它多于 n-1 边条，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图 2 和图 3，随便加哪两顶点的边都将构成环。不过 n-1 条边并不一定是生成树。
  

如果一个有向图恰有一个顶点的入度为 0，其余顶点的入度均为 1，则是一棵有向树。
对于有向树的理解比较容易，所谓入度为 0 其实就相当于树种的根结点，其余顶点入度为 1 就是说树的非根节点的双亲只有一个。
一个有向图的生成森林又若干棵有向树组成，含有图中全部定点，但只有足以构成若干棵不相交的有向树的弧。

如图是一棵有向图，去掉一些弧后，它可以分解为两棵有向树，这两棵就是图 1 的有向图的生成森林。

1.4 图的定义与术语总结

图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。

图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。

图上的边或弧上带权则称为网。

图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。

无向图中连通且 n 个顶点 n-1 条边叫生成树。有向图中一顶点入度为 0 ``其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

二、图的抽象数据类型

图的基本操作：

ADT 图(Graph)
Data
	顶点的有穷非空集合和边的集合。
Operation
	CreateGraph(*G, V, VR):按照顶点集 V 和边弧集 VR 的定义构造图 G。
	DestroyGraph(*G):图 G 存在则销毁。
	LocateVex(G,u):若图G 中存在顶点 u，则返回图中的位置。
	GetVex(G,v):返回图 G 中顶点 v 的值。
	PutVex(G,v,value):将图 G 中顶点 v 赋值 Value。
	FirstAdjVex(G,*v):返回顶点 v 的一个邻接顶点，若顶点在 G 中无邻接顶点返回空。
	NextAdjVex(G,v,*w):返回顶点 v 相对于顶点 w 的下一个邻接顶点，弱 w 是 v 的最后一个邻接点则返回“空”。
	InsertVex(*G,v):在图 G 中增添新顶点v。
	DeleteVex(*G,v,w):在图 G 中增添弧<v,w>,若 G 是无向图，还需要增添对称弧<w,v>。
	DFSTraverse(G):对图 G 中进行深度优先遍历，在遍历过程中对每个顶点调用。
	HFSTraverse(G):对图 G 中进行广度优先遍历，在遍历过程对每个顶点调用。
endADT

三、图的存储结构

图的存储结构相较线性表与树来说就更加复杂了。首先，我们口头上说的“顶点的位置”或“邻接点的位置”只是一个相对的概念。其实从图的逻辑结构定义来看，图上任何一个顶点都可被看成是第一个顶点，任一顶点的邻接点之间也不存在次序关系。比如图 中的四张图，仔细观察发现，它们其实是同一个图，只不过顶点的位置不同，就造成了表象上不太一样的感觉。

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，即图不能用简单的顺序存储结构来表示。
下面介绍五种实现物理存储的存储结构。

3.1 邻接矩阵

考虑到图是由顶点和边或弧两部分组成。合在一起比较困难，那就很自然地考虑到分两个结构来分别存储。顶点不分大小、主次，所以用一个一维数组来存储是很不错的选择。而边或弧由于是顶点与顶点之间的关系，一维搞不定，那就考虑用一个二维数组来存储。于是我们的邻接矩阵的方案就诞生了。

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

设图 G 有 n 个顶点，则邻接矩阵是一个 nxn的方阵，定义为：


我们可以设置两个数组，顶点数组为 vertex[4]={v0,v1,v2,v3},边数组 arc[4][4]为右图中的矩阵。对于主对角线的值，全为 0 是因为不存在顶点到自身的边，所以无向图的边数组是一个对称矩阵。

什么是对称矩阵
所谓对称矩阵就是 n 阶矩阵的元满足 aij=aji（0≤i,j ≤n）。即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的。

有了这个矩阵吗，我们可以轻易地知道图中的信息。

1. 我们要判定任意两顶点是否有边无边就非常容易了。
2. 我们要知道某个顶点的度，其实就是这个顶点 Vi在邻接矩阵中第i行(或第i列)的元素之和。比如顶点V1的度就是 1+0+1+0=2。
3. 求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1 就是邻接点。

实例：

顶点数组为 vertex[4]={ v0, v1, v2, v3}，弧数组 arc[4][4]为右图这样的一个矩阵。主对角线上数值依然为 0。但因为是有向图，所以此矩阵并不对称，比如由v1到 v0 有弧，得到 arc[1][0]=1，而 v0 到 v1没有弧，因此 arc[0][1]=0。
有向图讲究入度与出度，顶点 v1 的入度为 1，正好是第 v1 列各数之和。顶点 v1的出度为 2，即第行的各数之和。
与无向图同样的办法，判断顶点 vi 到 vj 是否存在弧，只需要查找矩阵中 arc[i][j] 是否为 1 即可。要求 vi 的所有邻接点就是将矩阵第 i 行元素扫描一遍，查找 arc[i][j] 为1的顶点。

什么是网图？
网的概念：每条边上带有权的图叫做网。
设图 G 是网图，有 n 个顶点，则邻接矩阵是一个 nxn 的方阵，定义为：

这里的 Wij 表示(Vi,Vj)或<Vi,Vj>上的权限。∞表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。如下图所示

邻接矩阵存储的结构代码：

typedef char VertexType;  /* 定点类型应由用户定义*/
typedef int EdgeType;  /* 边上的权值类型应由用户定义 */
#define MAXVEX 100   /* 最大顶点数，应由用户定义 */
#define INFINITY 65535  /* 用 65535 来代表 ∞ */
typedef struct
{
	VertexType vexs[MAXVEX];   /*定点表*/
	EdgeType arc[MAXVEX][MAXVEX];  /* 邻接矩阵，可看作编标*/
	int numVertexes, numEdges;  /* 图中当前的顶点数和边数 */
}MGraph;

创建无向图：

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *G)
{
	int i,j,l,w;
	printf("输入顶点数和边数：\n");
	scanf("%d,%d",&G->numVertexes, &G->numEdges);  /*输入顶点数和边数*/
	for(i = 0; i < G->numVertexes; i++)  /* 读入顶点信息，建立顶点表 */
		scanf(&G->vexs[i]);
	for(i = 0; j < G->numVertexes; j++)
		G->arc[i][j] = INFINITY;  /* 邻接矩阵初始化 */
	for(k = 0; k < G->numEdges; k++)  /*读入 numEdges 条边， 建立邻接矩阵*/
	{
		printf("输入边(vi,vj)上的下标 i ，下标 j 和权值 ： \n");
		scanf("%d,%d,%d",&i,&j,&w); /* 输入边(vi,vj)上的权 w */
		G->arc[i][j]=w;
		G->arc[j][i]= G->arc[i][j];  /*因为是无向图，矩阵对阵*/
	}
}

从代码中可以得到 n 个顶点和e 条边的无向网图的创建，时间复杂度为 O(n+n^2+e)，其中对邻接矩阵 Garc 的初始化耗费了 O(n^2);

3.2 邻接表

邻接矩阵是一种不错的图存储结构，但是，对于边相对顶点较少的图，用这个存储结构是一种浪费。因此我们考虑建数组与链表相结合的存储方式，称为邻接表（Adjacency List）。
邻接表的处理办法：

1. 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2. 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点 vi 的边表，有向图则称为顶点 vi 作为弧尾的出边表。
   

从图中我们知道，顶点表的各个结点由 data 和 firstedge 两个域表示，data 是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由 adjvex 和 next 两个域组成。adjvex 是邻接点域，存储某顶点的邻接点在顶点表中的下标，next 则存储指向边表中下一个结点的指针。比如v1顶点与 v0、v2互为邻接点，则在 v1 的边表中，adjvex 分别为 v0的0和 v2的 2。
这样的结构，对于我们要获得图的相关信息也是很方便的。比如我们要想知道某个顶点的度，就去查找这个顶点的边表中结点的个数。若要判断顶点到v是否存在边，只需要测试顶点v的边表中 adjvex 是否存在结点v的下标j就行了。若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的 adivex 域对应的顶点就是邻接点。
若是有向图，邻接表结构是类似的，比如下图中第一幅图的邻接表就是第二幅图。但要注意的是有向图由于有方向，我们是以顶点为弧尾来存储边表的，这样很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表，即对每个顶点都建立一个链接为v为弧头的表。

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。
对于带权值的网图，可以在边表结点定义中再增加一个 weight 的数据域，存储权值信息即可。

代码如下：

typedef char VertexType;  /*顶点类型应由用户定义 */
typedef int Edgerype; /*边上的权值类型应由用户定义*/

typedef struct EdgeNode  /*边表结点 */
{
	int adjvex;  /*邻接点域，存储该顶点对应的下标*/
	EdgeType weight; /*用于存储权值，对于非网图可以不需要 */
	struct EdgeNode *next;  /*链域，指向下一个邻接点*/
}EdgeNode;

typedef struct VertexNode  /* 顶点表结点 */
{
	VertexType data;   /* 顶点域，存储顶点信息*/
	EdgeNode *firstedge;  /* 边表头指针 */
}VertexNode,AdjList[MAXVEX];

typedef struct
{
	AdjList adjlist;
	int numVertexes,numEdges;  /* 图中当前顶点数和边数 */
}GraphAdjlist;

/* 建立图的邻接表结构 */
void CreateALGraph(GraphAdjList *G)
{
	int i,j,k;
	EdgeNode *e;
	printf("输入顶点数和边数:\n");
	scanf("号d,号d",&G->numVertexes,&G->numEdges);  /*输入顶点数和边数*/
	for(i =0;i<G->numVertexes;i++)  /*读入顶点信息，建立顶点表*/
	{
		scanf(&G->adjlistli].data);/*输入顶点信息 */
		G->adjlist[il.firstedge-NuLL;/*将边表置为空表 */
	}
	for(k = 0;k < G->numEdges;k++)/*建立边表 */
	{
		printf("输入边(vi,vj)上的顶点序号:n");
		scanf("%d,%d",&i,&j);/*输入边(vi,v)上的顶点序号 */
		e=(EdgeNode*)malloc(sizeof(EdgeNode));  /*向内存申请空间，生成边表结点 */
		e->adjvex=i;

/*邻接序号为i */

		e->next=G->adjList[j].firstedge;/*将e指针指向当前顶点指向的结点*/
		G->adjList[j].firstedge=e;/*将当前顶点的指针指向e */	}
}

时间复杂度：O(N+E)

3.3 十字链表法

那么对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢?答案是肯定的，就是把它们整合在一起。这就是我们现在要讲的有向图的一种存储方法:十字链表(0rthogonal List)。
我们重新定义顶点表结点结构如下：

其中 frstin 表示入边表头指针，指向该顶点的入边表中第一个结点，firstout 表示出边表头指针，指向该顶点的出边表中的第一个结点。

其中 tailvex 是指弧起点在顶点表的下标，headvex 是指弧终点在顶点表中的下标，headlink 是指入边表指针域，指向终点相同的下一条边，taillink 是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个 weight 城来存储权值。

我们重点需要来解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。对于v0 来说，它有两个顶点 v1 和 v2的入边。因此 v0的 firstin 指向顶点 v的边表结点中headvex 为0的结点，如图中的①。接着由入边结点的 headlink 指向下一个入边顶点 v2，如图中的②。对于顶点 v1，它有一个入边顶点 v2，所以它的 firstin 指向顶点 v2的边表结点中 headvex 为1 的结点，如图中的③。顶点 v2和 v3 也是同样有一个入边顶点，如图中④和⑤。
十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以 vi 为尾的弧，也容易找到以 vi 为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表是非常好的数据结构模型。

3.4 邻接多重表

如果无向图的邻接表在应用中更多侧重于顶点，如果是操作边，比如对已访问过的边做标记，删除某一条边，意味着需要找到这条边的两个边表结点进行操作。这实际上是比较麻烦的。

比如，若要删除左图的(vo,vz)这条边，需要对邻接表结构中右边表的阴影两个结点进行删除操作，显然这是比较烦琐的。

我们可以仿照十字链表的方式，对边表结点的结构进行一些改造，避免繁琐的边处理问题。

重新定义的编标结点结构如下：

其中 ivex 和 jvex 是与某条边依附的两个顶点在顶点表中下标。ilink 指向依附顶点 ivex 的下一条边，jlink 指向依附顶点 jvex 的下一条边。这就是邻接多重表结构。

我们来看结构示意图的绘制过程，理解了它是如何连线的，也就理解邻接多重表构造原理了。如图所示，左图告诉我们它有4 个顶点和 5 条边，显然，我们就应该先将 4 个顶点和 5 条边的边表结点画出来。由于是无向图，所以 ivex 是 0、jvex 是1还是反过来都是无所谓的，不过为了绘图方便，都将 ivex 值设置得与一旁的顶点下标相同。

我们开始连线，如下图。首先连线的②③④就是将顶点的 firstedge 指向一条边，顶点下标要与 ivex 的值相同，这很好理解。接着，由于顶点v0的(v0,v1)边的邻边有(v0,v3)和(v0,v2)。因此⑤⑥的连线就是满足指向下一条依附于顶点 v0的边的目标，注意 ilink 指向的结点的 jvex 一定要和它本身的 ivex 的值相同。同样的道理，连线⑦就是指(v1,v0)这条边，它是相当于顶点 v1 指向(v1,v2)边后的下一条。v2有三条边依附，所以在③之后就有了⑧⑨。连线⑩的就是顶点 v3 在连线④之后的下一条边。左图一共有5条边，所以右图有 10 条连线，完全符合预期。

到这里，大家应该可以明白，邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了，若要删除左图的(v0,v2)这条边，只需要将右图的⑥⑨的链接指向改为^即可。

3.5 边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成，如图所示。


其中 begin 是存储起点下标，end 是存储终点下标，weight 是存储权值。

显然边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。关于边集数组的应用我们将在克鲁斯卡尔(Kruskal)算法中有介绍，这里就不再详述了。

四、图的遍历

图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历(Traversing Graph)。
我们需要在遍历过程中把访问过的顶点打上标记，以避免访问多次而不自知。具体办法是设置一个访问数组 visited[n]，n 是图中顶点的个数，初值为 0，访问过后设置为 1。
对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。

4.1 深度优先遍历

深度优先遍历(Depth_First_Search)，也有称为深度优先搜索，简称为 DFS。

首先我们从顶点 A 开始，做上表示走过的记号后，面前有两条路，通向 B和F,我们给自己定一个原则，在没有碰到重复顶点的情况下，始终是向右手边走，于是走到了 B 顶点。整个行路过程，可参看右图。此时发现有三条分支，分别通向顶点 C、I、G，右手通行原则，使得我们走到了C顶点。就这样，我们一直顺着右手通道走，一直走到F顶点。当我们依然选择右手通道走过去后，发现走回到顶点 A了，因为在这里做了记号表示已经走过。此时我们退回到顶点F，走向从右数的第二条通道，到了G顶点，它有三条通道，发现B和D都已经是走过的，于是走到H，当我们面对通向 H的两条通道D和E时，会发现都已经走过了。
此时我们是否已经遍历了所有顶点呢?没有。可能还有很多分支的顶点我们没有走到，所以我们按原路返回。在顶点H处，再无通道没走过，返回到G，也无未走过通道，返回到F，没有通道，返回到 E，有一条通道通往 H 的通道，验证后也是走过的，再返回到顶点 D，此时还有三条道未走过，一条条来，H走过了，G走过了，I,哦，这是一个新顶点，没有标记，赶快记下来。继续返回，直到返回顶点 A，确认你已经完成遍历任务，找到了所有的 9 个顶点。
深度优先遍历其实就是一个递归过程，转换到右图后其实就像是一棵树的前序遍历。
它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。事实上，我们这里讲到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

用邻接矩阵的方式：

typedef int Boolean;  /*Boolean 是布尔类型，其值是 TRUE 或者 FALSE*/
Boolean visited[MAX];  /*访问标志的数组*/

/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph G,int i)
{
	int j;
	visited[i] = TRUE;
	printf("%c ", G.vexs[i]);    /* 打印顶点，也可以其他操作 */
	for(j = 0; j< G.numVertexes; j++)
		if(G.arc[i][j] == 1 && !visited[j])
			DFS(G, j);     /* 对为访问的邻接顶点递归调用 */
}

/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph G)
{
	int i;
	for(i = 0; i < G.numVertexes; i++)
		visited[i] = FALSE;   /* 初始所有顶点状态都是未访问过状态 */
	for(i = 0; i < G.numVertexes; i++)
		if(!visited[i])    /* 对未访问过的顶点调用 DFS，弱是连通图只会执行一次 */
			DFS(G,i);
}

如果图结构是邻接表结构，其 DFSTraverse 函数的代码是几乎相同的，只是在递归函数中因为将数组换成了链表而有所不同。

/*邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i)
{
	EdgeNode *p;
	visited[i] = TRUE;
	printf("%c ",GL->adjList[i].data);  /*打印顶点，也可以其他操作*/
	p = GL->adjList.firstedge;
	while(p)
	{
		if(!visited[p->adjvex])
			DS(GL, p->adjvex);  /* 对未访问的邻接顶点递归调用 */
		p = p->next;
	}
}

/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList GL)
{
	int i;
	for(i = 0; i < GL->numVertexes; i++)
		visited[i] = FALSE;  /* 初始所有顶点状态都是未访问过的状态 */
	for(i = 0; i < GL->numVertexes; i++)
		if(!visited[i])  /* 对未访问过的顶点调用 DFS，若是连通图，只会执行一次 */
			DFS(GL, i);
}

邻接矩阵由于是二维数组，需要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要 O(n^2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是 O(n+e)。对于点多边少的稀疏图，邻接表结构算法效率更高。

以上算法同样适用于有向图。

4.2 广度优先遍历

广度优先遍历(Breadth_First_Search)，又称为广度优先搜索，简称 BFS。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。我们将图中的第一幅图稍微变形，变形原则是顶点 A 放置在最上第一层，让与它有边的顶点 B、F 为第二层，再让与 B 和F 有边的顶点 C、I、G、E为第三层，再将这四个顶点有边的 D、H 放在第四层，如图的第二幅图所示。此时在视觉上感觉图的形状发生了变化，其实顶点和边的关系还是完全相同的。

void BFSTraverse(MGraph G)
{
	int i, j;
	Queue Q;
	for(i = 0; i < G.numVertexes; i++)
		visited[i] = FALSE;
	InitQueue(&Q);    /* 初始化一辅助用的队列 */
	for(i = 0; i < G.numVertexes; i++)
	{
		if(!visited[i])  /* 若是未访问过就处理 */
		{
			visited[i] = TRUE;   /* 设置当前顶点访问过 */
			printf("%c ",G.vexs[i]);  /* 打印结点，也可以执行其他操作 */
			EnQueue(&Q, i);  /* 将此顶点入队列 */
			while(!QueueEmpty(Q)) /* 若当前队列不为空 */
			{
				DeQueue(&Q,&i);   /* 将队中元素出队列，赋值给 i */
				for(j=0; j<G.numVertexes; j++)
				{
					/* 判断其他顶点弱与当前顶点存在边且未访问过 */
					if(G.arc[i][j] == 1 && !visited[j])
					{
						visited[j]=TRUE; /* 将找到的顶点标记为已访问 */
						printf("%c ",G.vexs[j]);  /*打印顶点*/
						EnQueue(&Q,j) /* 将找到的此顶点入队列 */
					}
				}
			}
		}
	}
}

对于邻接表的广度优先遍历算法：

void BFSTraverse(MGraph G)
{
	int i;
	EdgeNode *p;
	Queue Q;
	for(i = 0; i < GL->numVertexes; i++)
		visited[i] = FALSE;
	InitQueue(&Q);    /* 初始化一辅助用的队列 */
	for(i = 0; i < GL->numVertexes; i++)
	{
		if(!visited[i])  /* 若是未访问过就处理 */
		{
			visited[i] = TRUE;   /* 设置当前顶点访问过 */
			printf("%c ",GL->adjList[i].data);  /* 打印结点，也可以执行其他操作 */
			EnQueue(&Q, i);  /* 将此顶点入队列 */
			while(!QueueEmpty(Q)) /* 若当前队列不为空 */
			{
				DeQueue(&Q,&i);   /* 将队中元素出队列，赋值给 i */
				p = GL->adjList[i].firstedge;  /*找到当前顶点边表链表头指针*/
				while(p)
				{
					if(!visited[p->adjvex])
					{
						visited[p->adjvex]=TRUE; /* 将找到的顶点标记为已访问 */
						printf("%c ",GL->adjvex[p->adjvex].data);  /*打印顶点*/
						EnQueue(&Q,p->adjvex) /* 将找到的此顶点入队列 */
					}
					p = p->next;  /* 指针指向下一个结点 */
				}
			}
		}
	}
}

• 深度优先更适合目标比较明确，以找到目标为主要目的的情况，
• 广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

五、最小生成树

显然这是一个带权值的图，即网结构。所谓的最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并且使得权值的和最小。在这个例子里，每多一公里就多一份成本，所以只要让线路连线的公里数最少，就是最少成本了。

我们把构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)。
找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。

5.1 普里姆(Prim)算法

为了能讲明白这个算法，我们先构造图中的邻接矩阵，如右图所示。

也就是说，现在我们已经有了一个存储结构为 MGragh 的G。G有9 个顶点，它的 arc 二维数组如图 7-6-3 的右图所示。数组中的我们用65535 来代表∞。
于是普里姆(Prim)算法代码如下，左侧数字为行号。其中INFINITY 为权值极大值，不妨是 65535，MAXVEX 为顶点个数最大值，此处大于等于9即可。现在假设我们自己就是计算机，在调用 MiniSpanTree_Prim 函数，输入上述的邻接矩阵后，看看它是如何运行并打印出最小生成树的。

/* Prim 算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;
	int adjvex[MAXVEX];  /* 保存相关顶点下标 */
	int lowcost[MAXVEX];  /* 保存相关顶点间边的权值 */
	lowcost[0] = 0;  /*初始化第一个权值为 0，即 vo加入生成树1owcost的值为0，在这里就是此下标的顶点已经加入生成树*/
	adjvex[0] = 0;  /* 初始化第一个顶点下标为 0 */
	for(i = 1;i < G.numVertexes; i++)  /*循环除下标为0 外的全部顶点*/
	{
		lowcost[i] = G.arc[0][i];  /*将 v0 顶点与之有边的权值导入数组*/
		adjvex[0] = 0;  /* 初始化第一个顶点下标为 0 */
	}

	for(i=1; i < G.numVertexes; i++)
	{
		min = INFINITY;  /* 初始化最小权值为∞,通常设置为不可能的大数字入 32767,65535等 */
		j = 1; k = 0;
		while(j < G.numVertexes)  /* 循环全部顶点 */
		{
			if(lowcost[j]!=0 && lowcost[j] < min)
			{ /* 如果权值不为0 且 权值小于min */
				min = lowcost[j];  /*则让当前权值成为最小值*/
				k = j;  /* 将当前最小值的下标存入 k */
			}
			j++;
		}
		printf("(%d,%d)",adjvex[k],k);  /* 打印当前顶点边中权值最小边 */
		lowcost[k] = 0;  /* 将当前顶点的权值设置为 0， 表示此顶点已经完成任务 */
		for(j = 1;j < G.numVertexes; j++)  /* 循环所有顶点 */
		{
			if(lowcost[j]!=0 && G.arc[k][j] lowcost[j])
			{/*若下标为 k 顶点各边权值小于此前这些顶点未被加入生成树权值*/
				lowcost[j] = G.arc[k][j];  /* 将较小权值存入 lowcost*/
				adjvex[j] = k;  /* 将下标为 k 的顶点存入 adjvex */
			}
		}
	}
}

假设 N=(P{E})是连通网，TE 是 N 上最小生成树中边的集合。算法从 U={u0}(u0∈V)，TE=G}开始。重复执行下述操作:在所有u ∈U,v∈V-U 的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合 TE，同时 v0并入 U，直至 U=V 为止。此时 TE中必有 n-1 条边，则 T=(V，{TE})为 N 的最小生成树。
由算法代码中的循环嵌套可得知此算法的时间复杂度为 0(n^2)。

5.2 克鲁斯卡尔(Kruskal)算法

/*对边集数组 Edge 结构的定义 */
typedef struct
{
	int begin;
	int end;
	int weight;
}Edge;

克鲁斯卡尔(Kruskal)算法代码如下，左侧数字为行号。其中 MAXEDGE 为边数量的极大值，此处大于等于15 即可，MAXVEX 为顶点个数最大值，此处大于等于9即可。现在假设我们自己就是计算机，在调用 MiniSpanTree_Kruskal 函数，输入邻接矩阵后，看看它是如何运行并打印出最小生成树的。

/*Kruskal 算法生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)  /* 生成最小生成树 */
{
	int i, n, m;
	Edge edges[MAXEDGE];  /* 定义边集数组 */
	int parent[MAXVEX]; /* 定义一数组用来判断边与边是都形成环路，此处省略将邻接觉着你 G 转为边集数组 edges 并按权值由小到大排序的代码 */
	for(i = 0; i<G.numVertexes; i++)  /*循环每一条边*/
		parent[i] = 0;  /*初始化数组为 0*/
	for(i = 0; i<G.numEdges; i++)
	{
		n = Find(parent, edges[i].begin);
		m = Find(parent, edges[i].end);
		if(n != m)  /* 假如 n 与 m 不等，说明此边没有与现有生成树形成环路 */
		{
			parent[n] = m;/* 将此边的结尾顶点放入下标为起点的 parent 中 表示此顶点已经在生成树集合中 */
			printf("(%d, %d) %d ",edges[i].begin, edges[i].end, edges[i].weight);
		}
	}
}

int Find(int *parent, int f) /* 查找连线顶点的尾部下标 */
{
	while(parent[f]>0)
		f =  parent[f];
	return f;
}

假设 N=(V,{E})是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图 T={V,0}，图中每个顶点自成一个连通分量。在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。此算法的 Find 函数由边数e决定，时间复杂度为 O(loge)，而外面有一个 for 循环e次。所以克鲁斯卡尔算法的时间复杂度为 O(eloge)。总而言之为 O(nlogn)。

对比两个算法，克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势;而普里姆算法对于稠密图，即边数非常多的情况会更好一些。

六、最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径;而对于网图来说最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。显然，我们研究网图更有实际意义，就地图来说，距离就是两顶点间的权值之和。而非网图完全可以理解为所有的边的权值都为1 的网。

6.1 迪杰斯特拉(Dijkstra)算法

这是一个按路径长度递增的次序产生最短路径的算法。
思路讲解：
比如下图中顶点 v0到顶点 v1 的最短距离答案就是 1，路径就是直接 v0 到 v1 连线。

由于顶点 v1 还与 v2、v3、v4连线，所以此时我们同时求得了 v0→v1→v2=1+3=4,v0→v1→v3=1+7=8，v0→v1→V4=1+5=6。

现在，我问 v0到 v2的最短距离，如果你不假思索地说是 5，那就犯错了。因为边上都有权值，刚才已经有 v0→v1→v2的结果是 4，比5 还要小1个单位，它才是最短距离，如图所示。

由于顶点 v2还与 v4、v5连线，所以此时我们同时求得了 v0→v2→v4 其实就是 v0→v1→v2→v4=5 要比 v0→v1→v4=6还要小，所以 v0 到 v4 目前的最小距离是 5。如图所示。

当我们要求 v0 到 v3的最短距离时，通向 v3 的三条边，除了 v6 没有研究过外，vo→v1→v3的结果是 8，而 v0→v4→V3=5+2=7。因此，v0到 v3的最短距离是 7，如图所示。

迪杰斯特拉(Dijkstra)算法并不是一下子就求出了 v0到 v8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。
代码实现如下：

#define MAXVEX 9
#define INFINITY 65535
typedef int Pathmatirx[MAXVEX];  /* 用于存储最短路径下标的数组 */
typedef int ShortPathTable[MAXVEX];  /* 用于存储到各店最短路径的权值和 Dijkstra，求有向网 G 的 v0 顶点到其余顶点 v 最短路径 P[v]及带权长度 D[v] */
/* P[v]的值为前驱顶点的下标，D[v]表示 v0 到 v 的最短路径长度和。 */
void ShortestPath_Dijkstra(MGraph, int v0, Pathmatirx *p, ShortPathTable *D)
{
	int v,w,k,min;
	int final[MAXVEX];  /* final[w]=1 表示求的顶点 v0 至 vw 的最短路径 */
	for(v=0; v<G.numVertexes; v++)
	{
		min = INFINITY;    /* 当前所知离 v0 顶点的最近距离 */
		for(w=0; w<G.numVertexes; w++)  /* 寻找离 v0 最近的顶点 */
		{
			if(!final[w]  && (*D)[w]<min)
			{
				k=w;
				min = (*D)[w];  /* w 顶点离 v0 顶点更近 */
			}
		}
		final[k] = 1;  /* 将目前找到的最近的顶点置为 1 */
		for(w=0; w<G.numVertexes; w++)  /* 修正当前最短路径及距离 */
		{
			/*如果经过 v 顶点的路径比现在这条路径的长度短的话*/
			if(!final[w] && (min+G.matirx[k][w]<(*D)[w]))
			{
				/* 说明找到了更短的路径，修改 D[w]和 P[W] */
				(*D)[w] = min + G.matirx[k][w];  /* 修改当前路径长度 */
				(*p)[w] = k;
			}
		}
	}
}

算法实际运行过程：

1. 程序开始运行，第4 行 fnal 数组是为了v0到某顶点是否已经求得最短路径的标记，如果v0到 vw已经有结果，则final[w]=1。

2. 第 5~10 行，是在对数据进行初始化的工作。此时 final 数组值均为 0，表示所有的点都未求得最短路径。D数组为{65535,1,5,65535,65535,65535,65535,65535,65535}。因为 v0与v1和 v2的边权值为1 和 5。P 数组全为 0,表示目前没有路径。

3. 第 11 行，表示 v0到 v0自身，权值和结果为 0。D 数组为{0,1,5,65535,6553565535,65535,65535,65535}。第 12 行，表示 v0点算是已经求得最短路径，因此final[0]=1。此时 final 数组为{1,0,0,0,0,0,0,0,0}。此时整个初始化工作完成。

4. 第 13~33 行，为主循环，每次循环求得 v0与一个顶点的最短路径。因此v从1 而不是0开始。

5. 第 15~23 行，先令 min 为 65535 的极大值，通过 w 循环,与 D[w] 比较找到最小值 min=1，k=1。

6. 第 24 行，由 k=1，表示与 v0 最近的顶点是 v1，并且由 D[1]=1，知道此时 v0到 v1的最短距离是 1。因此将 v1 对应的 final[1] 设置为 1。此时 final 数组为{1,1,0,0,0,0,0,0.0}。

7. 第 25～32 行是一循环，次循环甚为关键。它的目的是在刚才已经找到 v0 与 v1 的最短路径的基础上，对 v1 与其他顶点的边进行计算，得到 v0 与它们的当前最短距离，如图所示。因为 min=1，所以本来 D[2]=5，现在 v0→v1→v2=D[2]=min+3=4，v0→V1→v3=D[3]=min+7=8，v0→v1→v4=D[4]=min+5=6,因此，D 数组当前值为{0,1,4,8,6,65535,65535,65535,65535}。而 P[2]=1,P[3]=1，P[4]=1，它表示的意思是 v0到 v2、v3、v4点的最短路径它们的前驱均是 v1。此时P数组值为:{0,0,1,1,1,0,0,0,0}。
   

8. 重新开始循环，此时 v=2。第 15~23 行，对 w 循环，注意因为 final[0]=1 和final[1]=1，由第 18 行的!fnal[w]可知，v0与v1并不参与最小值的获取。通过循环比较，找到最小值 min=4，k=2。

9. 第 24 行，由 k=2，表示已经求出 v0到 v2的最短路径，并且由 D[2]=4，知道最短距离是 4。因此将 v2 对应的 final[2] 设置为 1，此时 fnal 数组为:{1,1,1,0,0,0,0,0,0}。

10. 第 25~32 行。在刚才已经找到 v0与v2的最短路径的基础上，对 v2与其他顶点的边，进行计算，得到 v0与它们的当前最短距离，如图所示。因为 min=4，所以本来 D[4]=6，现在 v0→v2→v4=D[4]=min+1=5，v0→v2→v5=D[5]=min+7=11，因此，D 数组当前值为:{0,1,4,8,5,11,65535,6553565535}。而原本 P[4]=1，此时 P[4]=2，P[5]=2，它表示 v0 到 v4、v5 点的最短路径它们的前驱均是 v2。此时P数组值为:{0,0,1,1,2,2,0,0,0}。
    

11. 重新开始循环，此时 v=3。第 15~23 行，通过对 w 循环比较找到最小值min=5, k=4.

12. 第 24 行，由k=4，表示已经求出 v0到 v4的最短路径，并且由 D[4]=5，知道最短距离是 5。因此将 v4 对应的 final[4]设置为 1。此时 final 数组为:{1,1,1,0,1,0,0,0,0}。

13. 第 25~32 行。对 v4与其他顶点的边进行计算，得到 v0与它们的当前最短距离，如图所示。因为min=5，所以本来 D[3]=8，现在 v0→v4→v3=D[3]=min+2=7，本来 D[5]=11，现在 v0→v4→v5=D[5]=min+3=8，另外 v0→v4→v6=D[6]=min+6=11，v0→v→v,=D[7]=min+9=14，因此，D 数组当前值为:{0,1,4,7,5,8,11,14,65535}。而原本P[3]=1，此时 P[3]=4，原本P[5]=2，此时 P[5]=4，另外 P[6]=4，P[7]=4，它表示 v0到 v3、v5、v6、v7 点的最短路径它们的前驱均是 v4。此时 P 数组值为:{0,0,1,4,2,4,4,4,0}。
    
    其实最终返回的数组 D 和数组 P，是可以得到 v0 到任意一个顶点的最短路径和路径长度的。例如 v0到 v8的最短路径并没有经过 v5，但我们已经知道 v0到 v5的最短路径了。由 D[5]=8 可知它的路径长度为8，由 P[5]=4可知 v5的前驱顶点是 v4，所以 v0到v5的最短路径是 v0→v1→v2→v4→v5。
    也就是说，我们通过迪杰斯特拉(Dijksta)算法解决了从某个源点到其余各顶点的最短路径问题。从循环嵌套可以很容易得到此算法的时间复杂度为 0(n^2)，尽管有同学觉得，可不可以只找到从源点到某一个特定终点的最短路径，其实这个问题和求源点到其他所有顶点的最短路径一样复杂，时间复杂度依然是 0(n^2)。

6.2 弗洛伊德(Floyd)算法

左图是一个最简单的3个顶点连通网图。
我们先定义两个二维数组 D[3][3]和 P[3][3]，D 代表顶点到顶点的最短路径权值和的矩阵。P代表对应顶点的最小路径的前驱矩阵。在未分析任何顶点之前，我们将D命名为 D^-1，其实它就是初始的图的邻接矩阵。将P命名为 P^-1，初始化为图中所示的矩阵。
首先我们来分析，所有的顶点经过 v0后到达另一顶点的最短路径。因为只有三个顶点，因此需要査看 v1→v0→v2，得到 D^-1 [1][0]+D^-1 [0][2]=2+1=3。D^-1 [1][2]表示的是 v1→v2的权值为 5，我们发现 D^-1 [1][2]>D^-1 [1][0]+D^-1 [0][2]，通俗的话讲就是 v1→v0→v2 比直接 v1→v2 距离还要近。所以我们就让 D&-1 [1][2]= D^-1 [1][0]+D^-1[0][2]=3，同样的 D^-1 [2][1]=3，于是就有了 D^0 的矩阵。因为有变化，所以 P 矩阵对应的 P^-1 [1][2]和 P^-1 [2][1]也修改为当前中转的顶点 v0的下标 0，于是就有了 P^0。也就是说

接下来，其实也就是在 D^0和 P^0的基础上继续处理所有顶点经过 v1 和 v2 后到达另一顶点的最短路径，得到 D^1和 P^1、D^2和 P^2完成所有顶点到所有顶点的最短路径计算工作。

复杂网图下的弗洛伊德算法：
首先我们针对下图的左网图准备两个矩阵 D^-1和P^-1，D^-1就是网图的邻接矩阵，P^-1初设为 P[i][j]=j 这样的矩阵，它主要用来存储路径。

代码如下，注意因为是求所有顶点到所有顶点的最短路径，因此Pathmatrx和ShortPathTablke 都是二维数组。

typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* Floyd 算法，求网图 G 中个顶点 v 到其余顶点 w 最短路径 P[v][w]及带权长度 D[v][w] */
void ShortestPath_Floyd(MGraph G, Pathmatirx *P, ShortPathTable *D)
{
	int v,w,k;
	for(v=0; v<G.numVertexes; ++v)  /* 初始化 D 与 P */
	{
		for(w=0; w<G.numVertexes; ++w)
		{
			(*D)[v][w] = G.matirx[v][w];  /* D[v][w]即为对应点间的权值 */
			(*P)[v][w] = w;
		}
	}
	for(k=0; k<G.numVertexes; ++k)
	{
		for(v=0; v<G.numVertexes; ++v)
		{
			for(w=0; w<G.numVertexes; ++w)
			{
				if((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
				{
					/* 如果经过下标为 k 的顶点路径比原两点间路径更短，将当前两点间权值设置为更小的一个 */
					(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
					(*P)[v][w]=(*P)[v][k];  /* 路径设置经过下标为 k 的顶点 */
				}
			}
		}
	}
}

1. 程序开始运行，第 4~11 行就是初始化了 D 和 P，使得它们成为下图的两个矩阵。从矩阵也得到，v 0→v1路径权值是 1，v0→v2路径权值是 5，v0→v3无边连线，所以路径权值为极大值 65535
2. 第 12~25 行，是算法的主循环，一共三层嵌套，k 代表的就是中转顶点的下标。v代表起始顶点，w 代表结束顶点。
3. 当 K=0 时，也就是所有的顶点都经过 v0 中转，计算是否有最短路径的变化可惜结果是，没有任何变化，如图所示。
   
4. 当 K=1 时，也就是所有的顶点都经过 v1 中转。此时，当 v=0 时，原本D[0][2]=5，现在由于D[0][1]+D[1][2]=4。因此由代码的第 20 行，二者取其最小值，得到 D[0][2]=4，同理可得 D[0][3]=8、D[0][4]=6，当 v=2、3、4时，也修改了一些数据，请参考如图左图中虚线框数据。由于这些最小权值的修正，所以在路径矩阵P上，也要作处理，将它们都改为当前的P[v][k]值。
   
5. 接下来就是 k=2 一直到 8 结束，表示针对每个顶点做中转得到的计算结果，当然，我们也要清楚，D^0是以 D^-1为基础，D^1是以 D^0为基础，…...，D^8 是以D^7为基础，它们是有联系的，路径矩阵P也是如此。最终当 k=8 时，两矩阵数据如图所示。
   
   至此，我们的最短路径就算是完成了，你可以看到矩阵第 v0行的数值与迪杰斯特拉(Dijksta)算法求得的 D 数组的数值是完全相同，都是{0,1,4,7,5,8,10,12,16}。而且这里是所有顶点到所有顶点的最短路径权值和都可以计算出。

/* 求最短路径代码 */
for(v=0;v<G.numVertexes; ++v)
{
	for(w=v+l; w<G.numVertexes; w++)
	{
		printf("v%d-v%d weight: %d ",v,w,D[v][w]);
		k=P[v][w];  /* 获得第一个路径顶点下标 */
		printf(" path: %d",v);  /* 打印源点 */
		while(k!=w)  /*如果路径顶点下标不是终点*/
		{
			printf("-> %d",k);  /*打印路径顶点 */
			k=P[k][w];  /*获得下一个路径顶点下标 */
		}
		printf("-> %d\n",w);/*打印终点 */
	}
	printf("\n");
}

如果你面临需要求所有顶点至所有顶点的最短路径问题时，弗洛伊德(Floyd)算法应该是不错的选择。
另外，我们虽然对求最短路径的两个算法举例都是无向图，但它们对有向图依然有效，因为二者的差异仅仅是邻接矩阵是否对称而已。

七、拓扑排序

无环图的应用：
我们会把施工过程、生产流程、软件开发、教学安排等都当成一个项目工程来对待，所有的工程都可分为若干个“活动”的子工程。例如图是一张电影制作流程图，现实中可能并不完全相同，但基本表达了一个工程和若干个活动的概念。在这些活动之间，通常会受到一定的条件约束，如其中某些活动必须在另一些活动完成之后才能开始。就像电影制作不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中，场地都没有。这都会导致荒谬的结果。因此这样的工程图，一定是无环的有向图。

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为 AOV 网(Activity On VertexNetwork)。AOV 网中的弧表示活动之间存在的某种制约关系。比如演职人员确定了，场地也联系好了，才可以开始进场拍摄。另外就是 AOV 网中不能存在回路。刚才已经举了例子，让某个活动的开始要以自己完成作为先决条件，显然是不可以的。

设 G=(V,E)是一个具有 n个顶点的有向图，V 中的顶点序列 V1，V2，......，Vn满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环(回路)的 AOV 网;如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是 AOV 网。一个不存在回路的 AOV 网，我们可以将它应用在各种各样的工程或项目的流程图中，满足各种应用场景的需要，所以实现拓扑排序的算法就很有价值了。

7.1 拓扑排序算法

对 AOV 网进行拓扑排序的基本思路是:从 AOV 网中选择一个入度为 0 的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者 AOV 网中不存在入度为 0的顶点为止。
首先我们需要确定一下这个图需要使用的数据结构。前面求最小生成树和最短路径时，我们用的都是邻接矩阵，但由于拓扑排序的过程中，需要删除顶点，显然用邻接表会更加方便。因此我们需要为 AOV 网建立一个邻接表。考虑到算法过程中始终要查找入度为 0的顶点，我们在原来顶点表结点结构中，增加一个入度域in，结构如表所示，其中 in 就是入度的数字。

因此对于第一幅图 AOV 网，我们可以得到如第二幅图的邻接表数据结构。

拓扑排序算法代码如下：

typedef struct EdgeNode    /* 边表结点 */
{
	int adjvex;   /* 邻接点域 */
	int weight;   /* 用于存储权值，对于非网图可以不需要 */
	struct EdgeNode *next;  /* 链域 */
}EdgeNode;

typedef struct VertexNode  /* 顶点表结点 */
{
	int in;   /* 定点入度 */
	int data;   /* 顶点域，存储顶点信息 */
	EdgeNode *firstedge   /* 边表头指针 */
}VertexNode, AdjList[MAXVEX];

typedef struct
{
	AdjList adjList;
	int numVertexes,numEdges;  /* 图中当前顶点数和边数 */
}graphAdjList, *GraphAdjList;

在算法中，我们还需要辅助的数据结构——栈，用来存储处理过程中入度为 0 的顶点，目的是为了避免每个查找时都需要去遍历顶点表找有没有入度为 0的顶点。

/* 拓扑排序 */
Status TopologicalSort(GraphAdjList GL)
{
	EdgeNode *e;
	int i,k,gettop;
	int top=0;  /* 用于栈指针下标 */
	int count=0;   /* 用于统计输出顶点的个数 */
	int *stack;  /* 建栈存储入度为 0 的结点 */
	stack=(int *)malloc(GL->numVertexes * sizeof(int))
	for(i = 0; i< GL->numVertexes; i++)
		if(GL->adjList[i].in == 0)
			stack[++top]=i;  /* 将入度为 0 的顶点入栈 */
	while(top!=0)
	{
		gettop=stack[top--]; /* 出栈 */
		printf("%d -> ",GL->adjList[gettop].data);  /* 打印此顶点 */
		count++;   /* 统计输出顶点数 */
		for(e=GL->adjList[gettop].firstedge; e; e=e->next)
		{
			/* 对此顶点弧表遍历 */
			k=e->adjvex;
			if(!(--GL->adjList[k].in))  /* 将 k号顶点邻接点的入度减 1 */
				stack[++top]=k;  /* 若为 0 则入栈，以便于下次循环输出 */
		}
	}
	if(count < GL->numVertexes)  /* 如果 count小于顶点数，说明存在环 */
		return ERROR;
	else
		return OK;
}

1. 程序开始运行，第 3~7 行都是变量的定义，其中 stack是一个栈，用来存储整型的数字。

2. 第 8~10 行，作了一个循环判断，把入度为 0的顶点下标都入栈，从下图的右图邻接表可知，此时 stack 应该为:{0，1，3}，即 v0、v1、v3的顶点入度为 0。
   

3. 第 12~23 行，whie 循环，当栈中有数据元素时，始终循环。

4. 第 14~16 行，v3 出栈得到 gettop=3。并打印此顶点，然后 count 加 1。

5. 第 17~22 行，循环其实是对 v顶点对应的弧链表进行遍历，即图中的灰色部分，找到 v3连接的两个顶点 v和 v3，并将它们的入度减少一位，此时 v₂和 v3 的 in 值都为 1。它的目的是为了将 v3 顶点上的弧删除。
   

6. 再次循环，第 12~23 行。此时处理的是顶点 v1。经过出栈、打印、count=2后，我们对 v1 到 v2、v4、v8 的弧进行了遍历。并同样减少了它们的入度数,此时 v2, 入度为 0，于是由第 20~21 行知，v2入栈，如图所示。试想,如果没有在顶点表中加入 in 这个入度数据域，20 行的判断就必须要是循环,这显然是要消耗时间的，我们利用空间换取了时间。
   

7. 接下来，就是同样的处理方式了。下图 展示了 v2 v6 v0 v4 v5 v8的打印删除过程，后面还剩几个顶点都类似，就不图示了。
   
   

8. 最终拓扑排序打印结果为 3->1->2->6->0->4->5->8->7->12->9->10->13->11当然这结果并不是唯一的一种拓扑排序方案。

分析整个算法，对一个具有n 个顶点 e条弧的 AOV 网来说，第 8~10 行扫描顶点表，将入度为 0的顶点入栈的时间复杂为 O(n)，而之后的 whie 循环中，每个顶点进一次栈，出一次栈，入度减1的操作共执行了e次，所以整个算法的时间复杂度为O(n+e)。

八、关键路径

拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。比如说，造一辆汽车，我们需要先造各种各样的零件、部件，最终再组装成车，如图所示。这些零部件基本都是在流水线上同时生产的，假如造一个轮子需要 0.5 天时间，造一个发动机需要 3 天时间，造一个车底盘需要2天时间，造一个外壳需要2天时间，其他零部件时间需要2天，全部零部件集中到一处需要 0.5 天，组装成车需要 2天时间，请问，在汽车厂造一辆车，最短需要多少时间呢?

有人说时间就是全部加起来，这当然是不对的。我已经说了前提，这些零部件都是分别在流水线上同时生产的，也就是说，在生产发动机的3天里，可能已经生产了6 个轮子，1.5 个外壳和1.5 个底盘，而组装车是在这些零部件都生产好后才可以进行。因此最短的时间其实是零部件中生产时间最长的发动机3天+集中零部件 0.5天+组装车的 2 天，一共 5.5 天完成一辆汽车的生产。
因此，我们如果要对一个流程图获得最短时间，就必须要分析它们的拓扑关系，并且找到当中最关键的流程，这个流程的时间就是最短时间。

因此在前面讲了 AOV 网的基础上，我们来介绍一个新的概念。在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为 AOE 网(Actvity On EdgeNetwork)。我们把 AOE 网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。由于一个工程，总有一个开始，一个结束，所以正常情况下，AOE 网只有一个源点一个汇点。例如图就是一个 AOE 网。其中 v0即是源点，表示一个工程的开始，v9 是汇点，表示整个工程的结束，顶点 v0，v1,……，v9 分别表示事件，弧<v0,v1>，<v0,v2>，……，<v8,v9>都表示一个活动，用 a0，a1，……，a12 表示，它们的值代表着活动持续的时间，比如弧<v0,v1>就是从源点开始的第一个活动a0，它的时间是3个单位。

既然 AOE 网是表示工程流程的，所以它就具有明显的工程的特性。如有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始。只有在进入某顶点的各活动都已经结束，该顶点所代表的事件才能发生。
尽管 AOE 网与 AOV 网都是用来对工程建模的，但它们还是有很大的不同，主要体现在 AOV 网是顶点表示活动的网,，它只描述活动之间的制约关系，而 AOE 网是用边表示活动的网，边上的权值表示活动持续的时间，如图所示两图的对比。因此，AOE 网是要建立在活动之间制约关系没有矛盾的基础之上，再来分析完成整个工程至少需要多少时间，或者为缩短完成工程所需时间，应当加快哪些活动等问题。

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。显然就图中的 AOE 网而言，开始→发动机完成→部件集中到位→组装完成就是关键路径，路径长度为5.5。
如果我们需要缩短整个工期，去改进轮子的生产效率，哪怕改动成 0.1 也是无益于整个工期的变化，只有缩短关键路径上的关键活动时间才可以减少整个工期长度。例如如果发动机制造缩短为 2.5，整车组装缩短为 1.5，那么关键路径长度就为 4.5.整整缩短了一天的时间。
那么现在的问题就是如何找出关键路径。对人来说，上图这样的 AOE网，应该比较容易得出关键路径的，而对于源点汇点图中的 AOE 网，就相对麻烦一些，如果继续复杂下去，可能就非人脑该去做的事了。

8.1 关键路径算法原理

为了讲清楚求关键路径的算法，我们还是来举个例子。假设一个学生放学回家，除掉吃饭、洗漱外，到睡觉前有四小时空闲，而家庭作业需要两小时完成。不同的学生会有不同的做法，抓紧的学生，会在头两小时就完成作业，然后看看电视、读读课外书什么的;但也有超过一半的学生会在最后两小时才去做作业，要不是因为没时间，可能还要再拖延下去。下面的同学不要笑，像是在说你的是吧，你们是不是有过暑假两个月，要到最后几天才去赶作业的坏毛病呀?这也没什么好奇怪的，拖延就是人性几大弱点之一。
这里做家庭作业这一活动的最早开始时间是四小时的开始，可以理解为 0，而最晚开始时间是两小时之后马上开始，不可以再晚，否则就是延迟了，此时可以理解为2。显然，当最早和最晚开始时间不相等时就意味着有空闲。
接着，你老妈发现了你拖延的小秘密，于是买了很多的课外习题，要求你四个小时，不许有一丝空闲，省得你拖延或偷懒。此时整个四小时全部被占满，最早开始时间和最晚开始时间都是 0，因此它就是关键活动了。
也就是说，我们只需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。
为此，我们需要定义如下几个参数。

1. 事件的最早发生时间 etv(earliest time of vertex):即顶点 Vk的最早发生时间。
2. 事件的最晚发生时间 ltv(latest time of vertex):即顶点 Vk的最晚发生时间,也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。
3. 活动的最早开工时间 ete(earliest time ofedge): 即弧 ak的最早发生时间。
4. 活动的最晚开工时间 lte(latest time of edge):即弧 ak的最晚发生时间，也就是不推迟工期的最晚开工时间。
   我们是由1和2 可以求得3和4，然后再根据 ete[k]是否与 lte[k]相等来判断 ak是否是关键活动。

8.2 关键路径算法

我们将图的 AOE 网转化为邻接表结构如图所示，注意与拓扑排序时邻接表结构不同的地方在于，这里弧链表增加了 weight 域，用来存储弧的权值。

求事件的最早发生时间 etv 的过程，就是我们从头至尾找拓扑序列的过程，因此，在求关键路径之前，需要先调用一次拓扑序列算法的代码来计算 etv 和拓扑序列列表。为此，我们首先在程序开始处声明几个全局变量。

int *etv, *ltv;  /*事件最早发生时间和最迟发生时间数组*/
int *stack2;  /*用于存储拓扑序列的栈 */
int top2;  /*用于 stack2 的指针 */

其中 stack2 用来存储拓扑序列，以便后面求关键路径时使用。
下面是改进的拓扑排序算法：

/* 拓扑排序，用于关键路径计算 */
Status ToplogicalSort(GraphAdjList GL)
{
	EdgeNode *e;
	int i,k,gettop;
	int top=0;    /* 用于栈指针下标 */
	int count=0;  /* 用于统计输出顶点的个数 */
	int *stack;   /* 建栈将入度为 0 的顶点入栈 */
	stack=(int *)malloc(GL->numVertexes * sizeof(int));
	for(i = 0;i < GL-> numVertexes; i++){
		if(0 == GL->adjList[i].in)
			stack[++top]=i;
	}
	top2=0;    /*初始化为0*/
	etv=(int *)malloc(GL->numVertexes*sizeof(int));  /*事件最早发生时间*/
	for(int=0; i<GL->numVertexes; i++)
		etv[i]=0;  /* 初始化为0 */
	stack2=(int *)malloc(GL->numVertexes*sizeof(int));  /* 初始化 */
	while(top!=0)
	{
		gettop=stack[top--];
		count++;
		stack2[++top2]=gettop; /* 将弹出的顶点序号压入拓扑序列的栈 */
		for(e = GL->adjList[gettop].firstedge; e; e = e->next)
		{
			k=e->adjvex;
			if(!(--GL->adjList[k].in))
				stack[++top]=k;
			if((etv[gettop]+e->weight)>etv[k])  /*求各顶点事件的最早发生时间值*/
				etv[k]=etv[gettop] + e->weight;
		}
	}
	if(count < GL->numVertexes)
		return ERROR;
	else
		return OK;
}

代码中，除加粗部分外，与前面讲的拓扑排序算法没有什么不同。
第11~15 行为初始化全局变量etv数组、top2和stack2 的过程。第 21 行就是将本是要输出的拓扑序列压入全局栈sack2中。第 27~28 行很关键，它是求 etv 数组的每一个元素的值。比如说，假如我们已经求得顶点vo对应的 etv[0]=0，顶点v对应的 etv[1]=3，顶点 vz对应的 etv[2]=4，现在我们需要求顶点 v3对应的 etv[3]，其实就是求etv[1]+len<V1,V3>与etv[2]+len<V2,V3>的较大值。显然3+5<4+8，得到etv[3]=12，如图所示。在代码中 e->weight 就是当前弧的长度。

由此我们也可以得出计算顶点vk即求 etv[k]的最早发生时间的公式是:

其中P[K]表示所有到达顶点Vk的弧的集合。比如图中的P[3]就是<v1,v3>和<v2,v3>两条弧。len<Vi,Vk>是弧<Vi,Vk>上的权值。
下面我们来看求关键路径的算法代码。

/* 求关键路径，GL为有向图，输出GL的各项关键活动 */
void CriticalPath(GraphAdjList GL)
{
	EdgeNode *e;
	int i,gettop,k,j;
	int ete,lte;    /* 声明活动最早发生时间和最迟发生时间变量 */
	TopologicalSort(GL);    /* 求拓扑序列，计算数组etv和stack2的值 */
	ltv=(int *)malloc(GL->numVertexes*sizeof(int));    /* 事件最晚发生时间 */
	for(i=0; i<GL->numVertexes; i++)
		ltv[i] = etv[GL->numVertexes-1];    /* 初始化ltv */
	while(top2!=0)    /* 计算ltv */
	{
		gettop=stack2[top2--];    /* 将拓扑序列出栈，后进先出 */
		for(e = GL->adjList[gettop].firstedge; e; e = e->next)
		{
			/* 求各顶点事件的最迟发生时间ltv值 */
			k=e->adjvex;
			if(ltv[k]-e->weight<ltv[gettop])  /* 求各顶点事件最晚发生时间ltv */
				ltv[gettop] = ltv[k] - e->weight;
		}
	}	
	for(j=0; j<GL->numVertexes; j++)  /* 求ete,lte和关键活动 */
	{
		for(e = GL->adjList[j].firstedge; e; e=e->next)
		{
			k=e->adjvex;
			ete = etv[j];   /* 活动最早发生时间 */
			lte = ltv[k] - e->weight;    /* 活动最迟发生时间 */
			if(ete == lte)    /* 两者相等即在关键路径上 */
				printf("<v%d,v%d> length: %d , ", GL->adjList[j].data,GL->adjList[k].data,e->weight);
		}
	}
}

1. 程序开始执行。第5行，声明了ete和lte两个活动最早最晚发生时间变量。
2. 第6行，调用求拓扑序列的函数。执行完毕后，全局变量数组etv和栈stack的值如下图所示，top2=10。也就是说，对于每个事件的最早发生时间，我们已经计算出来了。
   
3. 第7~9行为初始化全局变量ltv数组，因为etv[9]=27，所以数组ltv当前的值为：{27，27，27，27，27，27，27，27，27，27}
4. 第 10~19 行为计算 ltv 的循环。第12行，先将 stack2 的栈头出栈，由后进先出得到 gettop=9。根据邻接表中，V9没有弧表，所以第 13~18 行循环体未执行。
5. 再次来到第12.行，gettop=8，在第13~18行的循环中，V8的弧表只有一条<V8,V9>，第15 行得到 k=9，因为ltv[9]-3<ltv[8]，所以 ltv[8]= Itv[9]-3=24，如图所示。
   
6. 再次循环，当gettop=7、5、6时，同理可算出 ltv 相对应的值为 19、25、13，此时ltv值为:{27，27，27，27，27，13，25，19，24，27}
7. 当 gettop=4 时，由邻接表可得到V4有两条弧<V4,V6>、<V4,V7>，通过第 13~18行的循环，可以得到ltv[4]=min(ltv[7]-4,ltv[6]-9)=min(19-4,25-9)=15，如图所示。
   
   此时你应该发现，我们在计算 ltv 时，其实是把拓扑序列倒过来进行的。因此我们可以得出计算顶点 vk即求ltv[k]的最晚发生时间的公式是:
   
   其中 S[K]表示所有从顶点 Vk 出发的弧的集合。比如上图 的 S[4]就是<V4,V6>和<V4,V7>两条弧，en<Vk,Vj>是弧<Vk,Vj>上的权值。
   当程序执行到第20行时，相关变量的值如图所示，比如etv[1] = 3 而 ltv[1] = 7，表示的意思就是如果时间单位是天的话，哪怕 v这个事件在第7天才开始，也可以保证整个工程的按期完成，你可以提前V1事件开始时间，但你最早也只能在第3天开始。跟我们前面举的例子，是先完成作业再玩还是先玩最后完成作业一个道理。
   
8. 第20~31行是来求另两个变量活动最早开始时间ete和活动最开始时间lte，并对相同下标的它们做比较。两重循环嵌套是对邻接表的顶点和每个顶点的弧表遍历。
9. 当j=0时，从V0点开始，有<V0,V2>和<V0,V1>两条弧。当k=2时，ete=etv[j]=etv[0]=0。lte=ltv[k]-e->weight=ltv[2]-len<V0,V2>=4-4=0，此 时ete=lte，表示弧<V0,V2>是关键活动，因此打印。当k=1时，ete=etv[j]=etv[0]=0。lte=ltv[k]-e->weight=ltv[1]-len<V0,V1>=7-3=4，此时 ete≠lte，因此<V0,V1>并不是关键活动，如图所示。
   
   这里需要解释一下，ete本来是表示活动<Vk,Vj>的最早开工时间，是针对弧来说的。但只有此弧的弧尾顶点vk的事件发生了，它才可以开始，因此ete=etv[k]。
   而 lte 表示的是活动<Vk,Vj>的最晚开工时间，但此活动再晚也不能等Vj事件发生才开始，而必须要在Vj事件之前发生，所以lte=ltv[j]-len<Vk,Vj>。就像你晚上 23 点睡觉，你不能说到 23点才开始做作业，而必须要提前2小时，在21点开始，才有可能按时完成作业。
   所以最终，其实就是判断ete与lte是否相等，相等意味着活动没有任何空闲，是关键活动，否则就不是。
10. j=1 一直到 j=9 为止，做法是完全相同的，关键路径打印结果为“<V0,V2> 4,<V2,V3> 8,<V3,V4>3,<V4,V7>4,<V7,V8>5,<V8,V9>3,”，最终关键路径如图所示。
    
    分析整个求关键路径的算法，第6行是拓扑排序，时间复杂度为0(n+e)，第8~9行时间复杂度为 0(n)，第10~19 行时间复杂度为 O(n+e)，第 20~31 行时间复杂也为 O(n+e)，根据我们对时间复杂度的定义，所有的常数系数可以忽略，所以最终求关键路径算法的时间复杂度依然是 O(n+e)。
    实践证明，通过这样的算法对于工程的前期工期估算和中期的计划调整都有很大的帮助。不过注意，本例是唯一一条关键路径，这并不等于不存在多条关键路径的有向无环图。如果是多条关键路径，则单是提高一条关键路径上的关键活动的速度并不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。这就像仅仅是有事业的成功，而没有健康的身体以及快乐的生活，是根本谈不上幸福的人生一样，三者缺一不可。