数据结构—图(Part Ⅲ)—拓扑排序&关键路径_邻接矩阵的拓扑排序时间复杂度

数据结构-图(第八章)的整理笔记，若有错误，欢迎指正。

图的应用

有向无环图描述表达式

• 有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG(Directed Acyclic Graph)图。
  
• 有向无环图是描述含有公共子式的表达式的有效工具。例如表达式$((a+b)\ast (b\ast (c+d))+(c+d)\ast e)\ast ((c+d)\ast e)$，可以用二叉树来表示。仔细观察该表达式，可发现有一些相同的子表达式$(c+d)$和$(c+d)\ast e)$，而在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。

拓扑排序

• AOV网(Activity On Vertex NetWork，用顶点表示活动的网)：若用DAG图(Directed Acyclic Graph，有向无环图)表示一个工程，其顶点表示活动，用有向边<$V_i，V_j$>表示活动$V_i$必须先于活动$V_j$进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为AOV网。
  
• 在AOV网中，活动$V_i$是活动$V_j$的直接前驱，活动$V_j$是活动$V_i$的直接后继，这种前驱和后继关系具有传递性，且任何活动不能以它自己作为自己的前驱或后继。
• 拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
  ①每个顶点出现且只出现一次。
  ②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
  或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。
• 对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：
  ①从AOV网中选择一个没有前驱(入度为0)的顶点并输出；
  ②从网中删除该顶点和所有以它为起点的有向边；
  ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
  

算法实现(邻接矩阵法)

bool TopologicalSort(MGraph g, int indegree[MaxVertenNum], int print[MaxVertenNum])
{
	SqStack st;
	InitStack(st);
	int i, j, count = 0;
	for (i = 0; i < g.vexnum; i++)
	{
		print[i] = -1; //初始全部为-1
		if (indegree[i] == 0) Push(st, i); //把入度为零的顶点入栈
	}
	while (!StackEmpty(st)) //栈不空时循环
	{
		Pop(st, i);
		print[count++] = i;
		for (j = 0; j < g.vexnum; j++)
			if (g.Edge[i][j] == 1)
				if (!(--indegree[j])) Push(st, j);
	}
	if (count < g.vexnum) return false;
	else return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果

程序分析

• 采用邻接矩阵法来拓扑排序的时间复杂度为O(|V|${}^2$)。

算法实现(邻接表法)

bool TopologicalSort(AdjGraph g,int indegree[MaxVertexNum],int print[MaxVertexNum])
{
	SqStack st;
	InitStack(st); //初始化栈，存储入度为0的顶点
	int i, j;
	ArcNode* p;
	for (i = 0; i < g.vexnum; i++)
	{
		print[i] = -1; //初始全部为-1
		if (indegree[i] == 0) Push(st, i); //将所有入度为0的顶点进栈
	}
	int count = 0; //计数，记录当前已经输出的顶点数
	while (!StackEmpty(st)) //栈不空，则存在入度为0的顶点
	{
		Pop(st, i); //输出顶点i
		print[count++] = i; 
		p = g.adjlist[i].firstarc;
		while (p != NULL)
			//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈st
		{
			j = p->adjvex;
			if (!(--indegree[j])) Push(st, j); //入度为0，则入栈
			p = p->nextarc;
		}
	}
	if (count < g.vexnum) return false; //拓扑排序失败，有向图中有回路
	else return true; //拓扑排序成功
}
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

运行结果

程序分析

• 由于输出每个顶点的同时还要删除以它为起点的边，故采用邻接表法来拓扑排序的时间复杂度为O(|V|+|E|)；

算法实现(深度优先遍历—DFS算法)

• 对于有向无环图G中的任意结点u、v，它们之间的关系必然是下列三种之一：

1. 假设结点u是结点v的祖先，则在调用DFS访问u的过程中，必然会在这个过程结束之前递归地对v调用DFS访问，即v的DFS函数结束时间先于u的DFS结束时间。从而可以考虑在DFS调用过程中设定一个时间标记，在DFS调用结束时，对各结点计时。因此，祖先的结束时间必然大于子孙的结束时间。
2. 若u是结点v的子孙，则v为u的祖先，按上述思路，v的结束时间大于u的结束时间。
3. 若u和v没有关系，则u和ν在拓扑序列的关系任意。从而按结束时间从大到小，可以得到一个拓扑序列。

• 下面给出利用DFS求各结点结束时间的代码。至于拓扑序列，将结束时间从大到小排序即可得到(实际上和深度优先遍历算法完全相同，只不过加入了time变量)。

bool visited[MaxVertenNum]; //访问标记数组
int finishTime[MaxVertenNum];
int time = 0;
void DFS(MGraph& g,int v)
//深度优先遍历图G，统计访问过的顶点数和边数，通过Vnum和Enum返回
{
	visited[v] = true; //作访问标记
	for (int w = FirstNeighbor(g, v); w >= 0; w = NextNeighbor(g, v, w))
		//取v的第一个邻接顶点
		if (!visited[w]) DFS(g, w); //当该邻接顶点为访问过
	time = time + 1; 
	finishTime[v] = time;
}

void DFSTraverse(MGraph g)
{
	int i;
	for (i = 0; i < g.vexnum; i++) visited[i] = false;
	for (i = 0; i < g.vexnum; i++)
		if (!visited[i]) DFS(g, g.Vex[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

逆拓扑排序

• 对一个AOV网(Activity On Vertex NetWork，用顶点表示活动的网)，如果采用下列步骤进行排序，则称之为逆拓扑排序：
  ①从AOV网中选择一个没有后继(出度为0)的顶点并输出；
  ②从网中删除该顶点和所有以它为终点的有向边；
  ③重复①和②直到当前的AOV网为空。

算法实现(邻接矩阵法)

• 主要代码不变，统计某个顶点的出度时，看该顶点对应序号的那一列有几个1。

bool Reverse_TopologicalSort(MGraph g, int outdegree[MaxVertenNum], int print[MaxVertenNum])
{
	SqStack st;
	InitStack(st);
	int i, j, count = 0;
	for (i = 0; i < g.vexnum; i++)
	{
		print[i] = -1;
		if (outdegree[i] == 0) Push(st, i);
	}
	while (!StackEmpty(st))
	{
		Pop(st, i);
		print[count++] = i;
		for (j = 0; j < g.vexnum; j++)
			if (g.Edge[j][i] == 1)
				if (!(--outdegree[j])) Push(st, j);
	}
	if (count < g.vexnum) return false;
	else return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果

算法实现(邻接表法)

• 需要使用逆邻接表，所谓逆邻接表(inverse adjacency list)，就是在有向图的邻接表中对每个顶点链接的是指向该顶点的边。
• 在邻接表代码的基础上做一点小的改动，在输入数值时进行区分，并且修改顶点的入度和出度。
  

bool Reverse_TopologicalSort(AdjGraph g,int outdegree[MaxVertexNum],int print[MaxVertexNum])
{
	SqStack st;
	InitStack(st); //初始化栈，存储出度为0的顶点
	int i, j;
	ArcNode* p;
	for (i = 0; i < g.vexnum; i++)
	{
		print[i] = -1; //初始全部为-1
		if (outdegree[i] == 0) Push(st, i); //将所有出度为0的顶点进栈
	}
	int count = 0; //计数，记录当前已经输出的顶点数
	while (!StackEmpty(st)) //栈不空，则存在出度为0的顶点
	{
		Pop(st, i); //输出顶点i
		print[count++] = i; 
		p = g.adjlist[i].firstarc;
		while (p != NULL)
			//将所有i指向的顶点的出度减1，并且将出度减为0的顶点压入栈st
		{
			j = p->adjvex;
			if (!(--outdegree[j])) Push(st, j); //出度为0，则入栈
			p = p->nextarc;
		}
	}
	if (count < g.vexnum) return false; //拓扑排序失败，有向图中有回路
	else return true; //拓扑排序成功
}
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

运行结果

算法实现(深度优先遍历—DFS算法)

bool visited[MaxVertexNum]; //访问标记数组
void DFS(AdjGraph g, int v)
{
	visited[v] = true; //设已访问标记
	for (int w = FirstNeighbor(g, v); w >= 0; w = NextNeighbor(g, v, w))
		if (!visited[w]) DFS(g, w); //尚未访问的邻接顶点
	printf("%d ", v); //访问顶点
}

void DFSTraverse(AdjGraph g) //对G进行深度优先遍历
{
	int i;
	for (i = 0; i < g.vexnum; i++) visited[i] = false; //初始化已访问标记数据
	for (i = 0; i < g.vexnum; i++) //从0号顶点开始遍历
		if (!visited[i]) DFS(g, i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行结果

关键路径

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

• AOE网具有以下两个性质：
  ①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
  ②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

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

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

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

• 下面给出在寻找关键活动时所用到的几个参量的定义。

1. 事件$v_k$的最早发生时间$ve(k)$

• 它是指从源点$v_i$到顶点$v_k$的最长路径长度。事件$v_k$的最早发生时间决定了所有从$v_k$开始的活动能够开工的最早时间。可用下面的递推公式来计算：
  v e ( 源 点 ) = 0 ， v e ( k ) = M a x { v e ( j ) + W e i g h t ( v j ， v k ) } ve(源点)=0，ve(k)=Max\{ve(j)+Weight(v_j，v_k)\} ve(源点)=0，ve(k)=Max{ve(j)+Weight(vj​，vk​)}，$v_k$为$v_j$的任意后继，Weight($v_j，v_k$)表示<$v_j，v_k$>上的权值
  计算$ve()$值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算：
  ①初始时，令$ve[1...n]$=0；
  ②输出ー个入度为0的顶点$v_j$时，计算它所有直接后继顶点$v_k$的最早发生时间，若$ve[j]+Weight(v_j，v_k)>ve[k]$，则$ve[k]=ve[j]+Weight(v_j，v_k)$。以此类推，直至输出全部顶点。
  

2. 事件$v_k$的最迟发生时间$v{l}_k$

• 它是指在不推迟整个工程完成的前提下，即保证它的后继事件$v_j$在其最迟发生时间$v{l}_j$能够发生时，该事件最迟必须发生的时间。可用下面的递推公式来计算：
  $vl$(汇点)=$ve$(汇点)， v l ( k ) = M i n { v l ( j ) − W e i g h t ( v k ， v j ) } vl(k)=Min\{vl(j)-Weight(v_k，v_j)\} vl(k)=Min{vl(j)−Weight(vk​，vj​)}，$v_k$为$v_j$的任意前驱
  ！注意： 在计算$v{l}_k$时，按从后往前的顺序进行，可以在逆拓扑排序的基础上计算。
  计算$vl()$值时，按从后往前的顺序进行，在上述拓扑排序中，增设一个栈以记录拓扑序列，拓扑排序结束后从栈顶至栈底便为逆拓扑有序序列。过程如下：
  ①初始时，令$vl[1...n]=ve[n]$；
  ②栈顶顶点$v_j$出栈，计算其所有直接前驱顶点$v_k$的最迟发生时间，若$vl[j]-Weight(v_k，v_j)<vl[k]$，则$vl[k]=vl[j]-Weight(v_k，v_j)$。以此类推，直至输出全部栈中顶点。
  

3. 活动$a_i$的最早开始时间$e(i)$

• 它是指该活动弧的起点所表示的事件的最早发生时间。若边$<v_k，v_j>$表示活动$a_i$，则有$e_i=ve(k)$。

4. 活动的最迟开始时间$l(i)$

• 它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边$<v_k，v_j>$表示活动$a_i$，则有$l(i)=vl(i)-Weight(v_k，v_j)$。

5. 一个活动$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$是关键活动。
  

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

1. 从源点出发，令$ve$(源点)=0，按拓扑有序求其余顶点的最早发生时间$ve()$。
   

2. 从汇点出发，令$vl$(汇点)=$ve$(汇点)，按逆拓扑有序求其余顶点的最迟发生时间$vl()$。
   

3. 根据各顶点的$ve()$值求所有弧的最早开始时间$e()$。
   

4. 根据各顶点的$vl()$值求所有弧的最迟开始时间$l()$。
   

5. 求AOE网中所有活动的差额$d()$，找出所有$d()=0$的活动构成关键路径。
   

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

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