因为上一篇无向图是否含环的文章取得了还不错的反馈，以及笔者刚好也在复习数据结构的知识，因此加更一篇有向图存在环的判断，我们可以看看两者之间是否具有互相可参考性。

有向无环图的主要应用是AOV和AOE分别是顶点制约关系和过程制约关系。

AOV 模板题Leetcode 207 课程表Ⅰ

我们还是借一个最简单的模板题来看一下题目的需求，我找到了一个非常完美的模板题，这里贴出链接：Leetcode 207课程表Ⅰ

一些废话（时间紧张可以跳过）

咱们都知道计算机专业有先导课程对吧，这个例子也是非常的经典了，在陈越姥姥的数据结构课里也有提到。

首先咱们要抽象出题目要求：给你一些课程之间的先导关系，你为他们检查是否可以排好课表，衡量标准就是，两个课不能互为先导课。不能有悖论的关系。

就像你得上Github学怎么科学上网，但你不会科学上网，你就打不开Github一样。 这肯定是不行的，必须要有位贵人先教会你科学上网，你才可以打开Github，去浏览更多的技术信息对吧（doge）。

拓扑排序解法及其优化

拓扑排序的核心思路是通过入度的变化来不断筛选出当前阶段可以上的课并记录完成情况，其实也是一种动态规划的思想。

核心步骤

  • 首先保存这个图的信息：每对边的指向。（方法不限，一会再讲优化）
  • 保存图信息的同时记录每个顶点的入度信息（用一个数组即可，数组下标即为顶点编号）
  • 筛选入度为0的顶点，（因为他们是不需要先导课的课程）将他们标记为已经修读并且遍历他们指向的后继课程，将这些后继课程的入度-1。这个过程是在模拟修读当前不需要先导课的课程。
  • 继续筛选修改之后入度为0的课程，重复这个过程，直到没有入度为0的课程。
  • 计算当前修读完的课程总数，如果等于所有课程的总数，那么可以完成排课。

整个过程就是一个判断有向图是否存在环的过程，大致思路如上。该方法逻辑的严谨性在于，如果两个顶点之间存在双向的路径，那么这两个顶点谁的入度都不会先变成0，所以也就不可能被加到count里。因此count是否等于课程总数是一个判断是否能排课的充分条件。

那么如何实现呢？

用到的结构和变量

  1. 一个二维的向量matrix用来存储先导关系，定义方式vector<vector<int>> matrix，向量matrix[i]里面存储的所有顶点都是i顶点的后继。当然也可以用邻接矩阵去存储，只不过那样需要耗费更多的空间去存储空信息，更多的时间去遍历。
  2. 一个int类型的变量count用来记录完成课程的数量，初始化为0。
  3. 一个大小为numCourses的int数组inDegree，全部初始化为0，表示各个顶点的入度。
  4. 一个队列start用来存储每轮的入度为0的点，定义方式queue<int> start。

代码：

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> matrix(numCourses);
        int *inDegree=new int[numCourses]{0};
        int count=0;
        for(int i=0;i<prerequisites.size();i++){
            matrix[prerequisites[i][0]].push_back(prerequisites[i][1]);
            inDegree[prerequisites[i][1]]++;
        }
        queue<int> start;
        for(int i=0;i<numCourses;i++){
            if(inDegree[i]==0)
                start.push(i);
        }
        while(!start.empty()){
            count++;
            for(int j=0;j<matrix[start.front()].size();j++){
                inDegree[matrix[start.front()][j]]--;
                if(inDegree[matrix[start.front()][j]]==0)
                    start.push(matrix[start.front()][j]);
            }
            start.pop();
        }
        if(count==numCourses)
            return true;
        else
            return false;

    }
};

上面的解法在时间性能和空间性能上超过了98%和76%的C++用户。

AOE模板题 Leetcode 课程表Ⅱ

这里贴出链接：Leetcode 210课程表Ⅱ

如果你真的理解了上面的思路的话，这道题几乎没有变化，只需要加上几行代码。事实上，这道题并不是一个标准的关键路径题，它只要求经过所有课程，但它的边却仍然是无权的。所以我们只要根据要求轻微调整：

代码

1
2
3
4
5
6
7
//这里需要注意输入的prerequisites略有变化，一条边前后两点的意义不同
vector<int> res;
/*207的代码一样，count++时
res.push_back(start.front());*/
if(count!=numCourses)
    res.erase(res.begin(),res.end());
return res;

AOE经典题型 工程最短消耗

给出一个工程中N个阶段的时间消耗和依赖关系，试求出工程的最短时间消耗。
N行数据，每行包含从1起始的阶段编号S、时间消耗T、以及用分号隔开的所依赖的不同阶段编号【如果不依赖其他阶段则此项为空】

这里有一个需要考虑并行的操作。因为只需要把相同层级的工序同时进行，这样最大的消耗就是这些工序中最耗时的一个。

拓扑排序核心代码

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
/*
实现需要先准备好这几个东西
int matrix[MAX][MAX]{0};
int indegree[MAX]{ 0 };
int cost[MAX]{ 0 };
*/

/*
解释一下为啥和上面不一样，因为这个是笔者初学时用的方法，完成OJ作业的，直接用邻接矩阵做了。
然后现在复习比较忙就不优化了，当时也写了不少注释，凑合看吧看官老爷，不懂的话也可以私信我QAQ
*/

void TopSort() {
	queue<int> q;
	int least_cost[MAX]{0};
	for (int i = 1; i <= N; i++)
		least_cost[i] = INF;
	for (int i = 1; i <= N;i++) {
		if (indegree[id[i]] == 0) {
			q.push(id[i]);
			least_cost[id[i]] = 0;
		}
	}
	int cnt=0,last;
	while (!q.empty()) {
		int V = q.front(),W;
		q.pop();
		for (int i = 1; i <= N; i++) {
			if (matrix[i][V]) {//找到V的前驱i
				if (least_cost[i] + cost[i] > least_cost[V]||least_cost[V]==INF){
					least_cost[V] = least_cost[i] + cost[i];//更新最小的值
				}
			}
		}
		if (cnt == N - 1)last = V;
		cnt++;
		for (int i = 1; i <= N; i++) {
			if (matrix[V][i]) {//如果有邻接点
				W = i;
				if (--indegree[W] == 0)
					q.push(W);
			}
		}
	}
	if (cnt != N) 
		cout << "error";//有环 报错
	else
		cout << least_cost[last] + cost[last];//输出最短的消耗
}