数据结构-图-其他特性

最小生成树

一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的 n-1 条边，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。对于一个带权连通无向图 $G=(V,E)$ ，生成树不同，其中边的权值之和最小的那颗生成树（构造连通网的最小代价生成树），称为G的最小生成树(Minimum-Spanning-Tree,MST)。

构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质：

假设 $G=(V,E)$ 是一个带权连通无向图，$U$ 是顶点集 $V$ 的一个非空子集。若 $(u,v)$ 是一条具有最小权值的边，其中 $u\in U,v \in V-U$ ，则必存在一棵包含边 $(u,v)$ 的最小生成树。

基于该性质的最小生成树算法主要有 Prim 算法和 Kruskal 算法，它们都基于贪心算法的策略。

下面介绍一个通用的最小生成树算法：

1
2
3
4
5
6
GENERIC_MSG(G){
    T=NULL;
    while T 未形成一棵生成树;
    	do 找到一条最小代价边(u,v)并且加入T后不会产生回路；
            T=T U (u,v);
}

通用算法每次加入一条边以逐渐形成一棵生成树，下面介绍两种实现上述通用算法的途径。

一、普里姆（Prim）算法

Prim算法构造最小生成树的过程如下图所示。初始时从图中任取一顶点(如顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1。以此类推，直至图中所有的顶点都并入 T，得到的 T 就是最小生成树。此时 T 中必然有 n-1 条边。）

通俗点说就是：从一个顶点出发，在保证不形成回路的前提下，每找到并添加一条最短的边，就把当前形成的连通分量当作一个整体或者一个点看待，然后重复“找最短的边并添加”的操作。

Prim算法的步骤如下：

假设 $G={V,E}$ 是连通图，其最小生成树 $T=(U,E_T)$ ，$E_T$ 是最小生成树种边的集合。

初始化：向空树 $T=(U,E_T)$ 中添加图 $G=(V,E)$ 的任一顶点 $u_0$ ，使 $U={u_0},E_T=NULL$ 。

循环(重复下列操作直至 $U=V$)：从图 G 中选择满足 ${(u,v)|u\in U,v\in V-U}$ 且具有最小权值的边$(u,v)$ ，加入树 $T$ ，置 $U= U \bigcup { v } , E_T = E_T \bigcup { (u,v)}$ ,

额，不得不说这样理解起来有点抽象，为了能描述这个算法，我们先构造一个邻接矩阵，如下图的右图所示。

于是普里姆（Prim）算法代码如下，左侧数字为行号。其中 INFINITY 为权值极大值，不妨设 65535，MAXVEX为顶点个数最大值，此处大于等于 9 即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*Prim算法生成最小生成树*/
void MiniSpanTree_Prim(G){
    int min,i,j,k;
    int adjvex[MAXVEX];//保存相关顶点下标
    int lowcost[MAXVEX];//保存相关顶点间边的权值
    lowcost[0]=0; //初始化第一个权值为 0 ,即 v0 加入生成树
    //lowcost的值为 0，在这里就是此下标的顶点已经加入生成树
    adjvex[0] = 0; //初始化第一个顶点下标为 0
    for(i=1;i<G.numVertexes;i++){
        lowcost[i]=G.arc[0][i]; //将v0顶点与之组成边的权值存入数组
        adjvex[i]=0; //初始化都为 v0 的下标
    }
    for(i=1;i<G.numVertexes;i++){
        min=INFINITY;//初始化最下权值为 ∞,通常设置一个不可能的很大的数字
        j=1;k=0;
        //循环全部顶点
        while(j<G.numVertexes){
            //如果权值不为 0 且权值小于 min
            if(lowcost[j]!=0 && lowcost[j]<min){
                min=lowcost[j]; //则让当前权值成为最小值
                k=j; //将当前最小值的下标存入 k
            }
            j++;
        }
        print("(%d,%d)",adjvex[k],k); //打印当前顶点边中权值的最小边
        for(j=1;j<G.numvertexes;j++){
            //若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
            if(lowcost[j]!=0 && G.arc[k][j]<lowcost[j]){
                lowcost[j]=G.arc[k][j];//将较小权值存入lowcost
                adjvex[j]=k;//将下标为k的顶点存入adjvex
            }
        }
    }
}

由算法代码中的循环嵌套可得知此算法的时间复杂度为 $O(n^2)$ 。

二、克鲁斯卡尔（Kruskal）算法

与Prim算法从顶点开始扩展最小生成树不同，Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

Kruskal算法构造最小生成树的过程如下图所示。初始时为只有 n 个顶点而无边的非连通图 $T=V$ ，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入 T ,否则舍弃此边而选择下一条权值最小的边。以此类推，直至 T 中所有的顶点都在一个连通分量上。

算法思路：

我们可以直接就以边为目标去构建，因为权值在边上，直接去找最小权值的边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环路而已。此时我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码：

1
2
3
4
5
6
/*对边集数组Edge结构的定义*/
typedef struct{
    int begin;
    int end;
    int weight;
}Edge;

我们将下面左图的邻接矩阵通过程序转化为右图的边集数组，并且对它们的权值从小到大排序。

于是Kruskal算法代码如下，左侧数字为行号。其中MAXEDGE为边数量的极大值，此处大于等于15即可，MAXVEX为顶点个数最大值，此处大于等于9即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*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.numVertexes;i++){
        n = Find(parent,edges[i].begin);
        m = Find(parent,edges[i].end);
        /*假如n与m不等，说明此边没有与现有生成树形成环路*/
        if(n!=m){
            /*将此边的结尾顶点放入下标为起点的parent中，表示此顶点已经在生成树集合中*/
            parent[n]=m;
            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;
}

此算法的 Find函数由边数e决定，时间复杂度为O(loge)，而外面有一个for循环e次。所以克鲁斯卡尔算法的时间复杂度为 $O(eloge)$。

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

最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

一、迪杰斯特拉（Dijkstra）算法

Dijkstra算法用于构建单源点的最短路径，即图中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地表的最短距离。可以用于有向图，但是不能存在负权值。

我们以上图为例，通俗点说，这个迪杰斯特拉(Dijkstra)算法，它并不是一下子求出了 $v_0$ 到 $v_8$ 的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

Dijkstra算法设置一个集合 S 记录已求得的最短路径的顶点。

在构造的过程中还设置了辅助数组：

dist[]: 记录从源点 $v_0$ 到其他各顶点当前的最短路径长度，它的初态为：若从 $v_0$ 到 $v_i$ 有弧，则dist[i]为弧上的权值；否则置dist[i]为 ∞ 。

例如，如图6.17中的图应用 Dijkstra 算法求从顶点 1 出发至其余顶点的最短路径的过程，如表 6.1 所示。算法执行过程的说明如下。

初始化：集合 S 初始为 $v_1$ ，$v_1$ 可达 $v2$ 和 $v_5$ ，$v_1$ 不可达 $v_3$ 和 $v_4$ ，因此 dist[] 数组各元素的初值依次设置为 dist[2]=10 , dist[3]=$\infty$ ,dist[4]=$\infty$ ，dist[5]=5。
第一轮：选出最小值 dist[5]，将顶点 $v_5$ 并入集合 $S$ ，即此时已找到 $v_1$ 到 $v_5$ 的最短路径。当 $v_5$ 加入 $S$ 后，从 $v_1$ 到集合 $S$ 中可达顶点的最短路径长度可能会产生变化。因此需要更新 dist[] 数组。$v_5$ 可达 $v_2$ ，因 $v_1 \longrightarrow v_5 \longrightarrow v_2$ 的距离 8 比 dist[2]=10小，更新 dist[2]=8; $v_5$ 可达 $v_3$ ，$v_1 \longrightarrow v_5 \longrightarrow v_3$ 的距离14，更新 dist[3]=14；$v_5 可达 v_4,v_1 \longrightarrow v_5 \longrightarrow v_4$ 的距离 7 ,更新 dist[4]=7。
第二轮：选出最小值 dist[4]，将顶点 $v_4$ 并入集合 $S$ 。继续更新 dist[] 数组。$v_4 不可达 v_2$，dist[2]不变；$v_4 可达 v_3 , v_1 \longrightarrow v_5 \longrightarrow v_4 \longrightarrow v_3$ 的距离 13 比 dist[3] 小，故更新 dist[3]=13。
第三轮：选出最小值 dist[2]，将顶点 $v_2$ 并入集合 $S$ 。继续更新 dist[] 数组。$v_2 可达 v_3 ，v_1 \longrightarrow v_5 \longrightarrow v_2 \longrightarrow v_3$ 的距离 9 比 dist[3] 小，更新 dist[3] = 9。
第四轮：选出唯一的最小值 dist[3]，将顶点 $v_3$ 并入集合 $S$ ，此时全部顶点都已包含在 $S$ 中。

显然，Dijkstra 算法也是基于贪心策略的。使用邻接矩阵或者带权的邻接表表示时，时间复杂度为 $O(V^2)$ 。

人们可能只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度也为 $O(V^2)$ 。

二、弗洛伊德（Floyd）算法

定义一个 n 阶方阵序列 $A^{(-1)},A^{(0)},\dots,A^{(n-1)}$，其中， $$ A^{(-1)}[i][j]=arcs[i][j] \ A^{(k)}[i][j]=Min{ A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j],k=0,1,\dots,n-1 } $$ 式中，$A^{(0)}[i][j]$ 是从顶点 $v_i 到 v_j$、中间顶点的序号不大于 k 的最短路径的长度。Floyd 算法是一个迭代的过程，每迭代一次，在从 $v_i 到 v_j$ 的最短路径上就多考虑了一个顶点；经过 n 次迭代后，所得到的 $A^{(n-1)}[i][j]$ 就是 $v_i 到 v_j$ 的最短路径长度，即方阵 $A^{(n-1)}$ 中就保存了任意一对顶点之间的最短路径长度。

上图所示为带权有向图 G 及其邻接矩阵。算法执行过程的说明如下：

初始化：方阵 $A^{(-1)}[i][j] = arcs[i][j]$。
第一轮：将 $v_0$ 作为中间顶点，对于所有顶点 ${i,j}$ ,如果有 $A^{-1}[i][j] > A^{-1}[i][0]+A^{-1}[0][j]$，则将 $A^{-1}[i][j]$ 更新为 $A^{-1}[i][0]+A^{-1}[0][j]$。有 $A^{-1}[2][1] > A^{-1}[2][0]+A^{-1}[0][1]=11$，更新 $A^{-1}[2][1]=11$，更新后的方阵标记为 $A^0$。
第二轮：将 $v_1$ 作为中间顶点，继续监测全部顶点对 ${i,j }$。有 $A^0[0][1]>A^0[0][1]+A^0[1][2]=10$ 更新后的方阵标记为 $A^1$ 。
第三轮：将 $v_2$ 作为中间顶点，继续监测全部顶点对 ${i,j}$ 。有 $A^1[1][0] > A^1[1][2]+A^1[2][0]=9$，更新后的方阵标记为 $A^2$。此时 $A^2$中保存的就是任意顶点对的最短路径长度。

应用 Floyd 算法求所有顶点之间的最短路径长度的过程如下表所示。

从这个表中，可以发现一些规律：

可以看出，矩阵中，每一步红线划掉的部分都不用考虑计算，只需要计算红线外的部分，节省了计算量。

Floyd算法的时间复杂度为 $O(V^3)$。不过由于其代码很紧凑，且并不包含其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。

Floyd算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。Floyd算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。

也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次 Dijkstra算法，其时间复杂度为 $O(V^3)*V=O(V^3)$。

拓扑排序

1、定义

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为 AOV 网(Activity On VertexNetwork)。

若用 DAG 图(有向无环图) 表示一个工程，其顶点表示活动，用有向边 $<V_i,V_j>$ 表示活动 $V_i$ 必须先于活动 $V_j$ 进行的这样一种关系。在 AOV 网中，活动 $V_i$ 是活动 $V_j$ 的直接前驱，活动 $V_j$ 是活动 $V_i$ 的直接后继，这种前驱和后继关系具有传递性，且任何活动 $V_i$ 不能以它自己作为自己的前驱或后继。

设 $G = (V,E)$ 是一个具有 n 个顶点的有向图，V 中的顶点序列 $V_1,V_2,\dots,V_n$ ,满足若从顶点 $V_i$ 到 $V_j$ 有一条路径，则在顶点序列中顶点 $V_i$ 必在顶点 $V_j$ 之前。则我们称这样的顶点序列为一个拓扑序列。

所谓**拓扑排序，其实就是对一个有向图构造拓扑序列的过程。**每个 AOV 网都有一个或多个拓扑排序序列。

二、算法

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：

①从 AOV 网中选择一个没有前驱的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复 ① 和 ② 直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是 AOV 网。

上图所示为拓扑排序过程的示例。每一轮选择一个入度为 0 的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为 {1,2,4,3,5} 。

拓扑排序算法的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool TopologicalSort(Graph G){
	InitStack(S);	//初始化栈，存储入度为0的顶点
	for(int i=0; i<G.vexnum; i++){
		if(indegree[i] == 0){
			Push(S, i);	//将所有入度为0的顶点进栈
		}
	}
	int count = 0;	//计数，记录当前已经输出的顶点数
	while(!IsEmpty(S)){	//栈不空，则存在入度为0的顶点
		Pop(S, i);	//顶点元素出栈
		printf("%d ", i);	//输出顶点i
		count++;
		for(p=G.vertices[i].finstarc; p; p=p->nextarc){
			//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
			v = p->adjvex;
			if(!--indegree[v]){
				Push(S, v);	//入度为0，则入栈
			}
		}
	}
	if(count < G.vexnum){
		return false;	//输出顶点少了，有向图中有回路，排序失败
	}else{
		return true;	//拓扑排序成功
	}
}

由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为 $O(V+E)$。

此外，利用深度优先遍历也可实现拓扑排序。

用拓扑排序算法处理 AOV 网时，应注意以下问题：
①入度为0的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
②若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
③由于 AOV 网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成 AOV 网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

关键路径

一、定义

拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。

在带权有向图，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称 AOE 网。 AOE 网和 AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的， AOE网中的边有权值；而 AOV网中的边无权值，仅表示顶点之间的前后关系。

AOE网具有以下两个性质：

①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

如上图的 AOE 网，在AOE网中仅有一个入度为 0 的顶点，称为开始顶点(源点)，它表示整个工程的开始；网中也仅存在一个出度为 0 的顶点，称为 结束顶点(汇点)，它表示整个工程的结束。我们把路径上各种活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫 关键活动。

完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。

二、算法

在分析算法之前，需要了解几个重要的参数：

**事件的最早发生时间 $ve$ **：即顶点 $V_k$ 的最早发生时期。
事件的最晚发生时间 $ul$：即顶点 $V_k$ 的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。
活动的最早开始时间 $e$ ：即弧 $a_i$ 的最早发生时间。
活动的最晚开始时间 $l$：即弧 $a_i$ 的最晚发生时间，也就是不推迟工期的最晚开工时间。
一个活动 $a_i$ 的最迟开始时间 $l(i)$ 和其最早开始时间 $e(i)$ 的差额 $d(i)=l(i)-e(i)$：它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动 $a_i$ 可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称 $l(i)-e(i)=0$ 即 $l(i)=e(i)$ 的活动 $a_i$ 是关键活动。

求关键路径的算法步骤如下：

从源点出发，令 $ve(源点)$ = 0 ，按拓扑排序求其余顶点的最早发生时间 $ve()$。
从汇点出发，令 $vl(汇点)=ve(汇点)$，按 逆拓扑排序 求其余顶点的最迟发生时间 $vl()$。
根据各顶点的 $ve() $ 值求所有弧的最早开始时间 $e()$。
根据各顶点的 $vl$ 值求所有弧的最迟开始时间 $l()$。
求 AOE 网中所有活动的差额 $d()$，找出所有 $d()=0$ 的活动构成关键路径。

上图所示为求解关键路径的过程，简单说明如下：

求 $ve()$：初始 $ve(1)=0$ ,在拓扑排序输出顶点的过程中，求得 $ve(2)=3$, $ve(3)=2$, $ve(4)=max{ve(2)+2,ve(3)+4}$=$max{5,6}$=$6,ve(5)$=$6,ve(6)$=$max{ve(5)+1,ve(4)+0,ve(3)+3}$=$max{7,8,5}$=$8$。
求 $vl()$：初始 $vl(6)=8$，在逆拓扑排序出栈过程之中，求得 $vl(5)=7$，$vl(4)=6$，$vl(3)$=$min{vl(4)-4,vl(6)-3}$=$min{2,5}$=2,$vl(2)=min{vl(5)-3，vl(4)-2}$=$min{4,4}$=4,$vl(1)$必然为0而无需再求。
弧的最早开始时间 $e()$ 等于该弧的起点的顶点的 $ve()$，求得结果如上表所示。
弧的最迟开始时间 $l(i)$ 等于该弧的终点的顶点的 $vl()$ 减去该弧持续的时间，求得结果如上表所示。
根据 $l(i)-e(i)=0$的关键活动，得到的关键路径为 $(v_1,v_3,v_4,v_6)$。
对于关键路径，需要注意以下几点：
①关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
②网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括所有关键路径上的关键活动才能达到缩短工期的目的。

最小生成树#

一、普里姆（Prim）算法#

二、克鲁斯卡尔（Kruskal）算法#

最短路径#

一、迪杰斯特拉（Dijkstra）算法#

二、弗洛伊德（Floyd）算法#

拓扑排序#

1、定义#

二、算法#

关键路径#

一、定义#

二、算法#

最小生成树

一、普里姆（Prim）算法

二、克鲁斯卡尔（Kruskal）算法

最短路径

一、迪杰斯特拉（Dijkstra）算法

二、弗洛伊德（Floyd）算法

拓扑排序

1、定义

二、算法

关键路径

一、定义

二、算法