C语言实现拓扑排序与关键路径_c语言 拓扑排序

一.有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图。

有向无环图是描述含有公共子式的表达式的有效工具。例如表达式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

可以用之前描述的二叉树来表示，仔细观察该表达式，可发现有一些相同的子表达式(c +d )和(c +d)*e,而在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间，下图为该表达式的有向无环图表示。

二.拓扑排序

1.AOV网

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

2.拓扑排序

拓扑排序:在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序:

• ①每个顶点出现且只出现一次。
• ②若项点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或定义为：拓扑排序是对有向无环图的顶点的一种排序， 它使得若存在一条从顶点 A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

3.基本步骤

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

• ①从AOV网中选择一个没有前驱的顶点并输出。
• ②从网中删除该顶点和所有以它为起点的有向边。
• ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

4.效率分析

由于输出每个顶点的同时还要删除以它为起点的边，故采用邻接表存储时拓扑排序的时间复杂度为0(|V|+ |E|)，采用邻接矩阵存储时拓扑排序的时间复杂度为0(|V|² )。

三.关键路径

1.基础概念

在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始;网中也仅存在一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。

在AOE网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

2.基本过程

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

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

3.举例计算

• 1)求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)+ 2, ve(3)+3} = max{7,8,5}= 8。
• 求vI():初始v1(6)=8,在逆拓扑排序出栈过程中，求得vl(5)=7, v/(4)=6, v(3)= min{(4)-4, v(6)-3} = min{2,5}=2, v(2) = min{vl(5)-3, 1(4)-2} = min{4, 4}=4，v(1)必然为0而无须再求。
• 3)弧的最早开始时间e()等于该弧的起点的顶点的ve()，求得结果如下表所示。
• 4)弧的最迟开始时间[(i)等 于该弧的终点的顶点的vl(O减去该弧持续的时间，求得结果如下表所示。
• 5)根据(i)-e(i)=0的关键活动，得到的关键路径为(v1, V3, V4, v6)。

4.注意

对于关键路径，需要注意以下几点:

• 1)关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可以通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一 定的程度，该关键活动就可能会变成非关键活动。
• 2)网中的关键路径并不唯-一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

四.C语言实现拓扑排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTEX_NUM 20  // 最大顶点数

typedef struct {
	char vertex[MAX_VERTEX_NUM];  // 存放顶点信息
	int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 存放边信息
	int vertex_num;  // 顶点数
	int edge_num;  // 边数
} Graph;

int indegree[MAX_VERTEX_NUM];           //存放每个顶点的入度
/*这里我们不要判断某个顶点的出度，在拓扑排序中我们用不到这些*/

//初始化顶点的入度数组
void Initindegree(Graph G){
	//首先初始化入度数组
	for(int i=0;i<G.vertex_num;i++){
		indegree[i]=0;
	}
	//统计每个元素对应邻接矩阵列中1的个数即可判断有几条边进入
	for(int i=0;i<G.vertex_num;i++){
		int count=0;
		for(int j=0;j<G.vertex_num;j++){
			if(G.edge[j][i]==1)
				count++;
		}
		indegree[i]=count;
	}
}

// 拓扑排序函数
bool Topologicalsort(Graph G) {
	char queue[MAX_VERTEX_NUM];
	int front = -1, rear = -1;    // 初始化队列，front和rear都设为0
	
	// 首先把入度为0的顶点都进队列
	for (int i = 0; i < G.vertex_num; i++) {
		if (indegree[i] == 0) {
			queue[++rear] = i; // 注意这里应该存储顶点的索引，而不是顶点的值
		}
	}
	
	int count = 0; // 这个变量用来记录当前已输出的顶点数
	while (front != rear) {
		int cur_vertex = queue[++front]; // 出队一个顶点,front原先是零，现在是1
		printf("%c ", G.vertex[cur_vertex]); // 输出顶点的值
		count++; // 已输出的顶点数加1
		
		// 遍历以当前顶点为起点的所有边
		for (int i = 0; i < G.vertex_num; i++) {
			if (G.edge[cur_vertex][i] == 1) {
				indegree[i]--; // 将这些边的终点的入度减1
				if (indegree[i] == 0) { // 如果某个终点的入度变为0，就将其入队
					queue[++rear] = i;
				}
			}
		}
	}
	
	if (count == G.vertex_num) { // 如果已输出的顶点数等于总顶点数，说明拓扑排序成功
		return true;
	} else { // 否则说明存在环，拓扑排序失败
		return false;
	}
}

int main(){
	Graph G;
	G.vertex_num=5;
	G.edge_num=6;
	//人为构造图的顶点
	for(int i=0;i<G.vertex_num;i++){
		G.vertex[i]= 'A'+i;
	}
	for(int i=0; i<G.vertex_num; i++){
		for(int j=0; j<G.vertex_num; j++){
			G.edge[i][j]=0;
		}
	}
	//人为构造图的边
	G.edge[0][1]=1;
	G.edge[0][3]=1;
	G.edge[1][3]=1;
	G.edge[1][2]=1;
	G.edge[3][4]=1;
	G.edge[2][4]=1;
	G.edge[3][2]=1;
	Initindegree(G);
	Topologicalsort(G);
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

五.运行截图

与我们自己手动排序的结果一样。

六.说明

这个专栏接下来就是排序算法啦，让我们共同期待。