LeetCode_210: CourseScheduleII 拓扑排序

这道题与前一版本207一样,只不过前一版本要求判断是否有环,而当前版本还要给出可行顺序,那么这个问题就自然而然的归为拓扑排序了。这篇博客将对有向图和无向图中是否存在环这一问题进行归纳,并且给出一个较为简洁的拓扑排序代码。拓扑排序,简单的说就是不断将度为0的点提取出来,提取的顺序就是拓扑排序。在算法导论中,给出了DFS和BFS解法,其中DFS采用完成时间倒序作为拓扑排序,我们需要了解拓扑排序问题的解法是多样的,这篇博客给出的代码不算唯一的。

题目

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

You may assume that there are no duplicate edges in the input prerequisites.

图中的环

对于无向图而言,判断其中的环需要两个步骤:[mathjax]

  1. $latex m >= n $, 根据图论知识,其中必定有环($latex m$为边数,$latex n$为顶点数)
  2. $latex m < n $, 不断删除度为$latex 1$的点,看能否删完

对于有向图而言,有三种解法:

  1. 看是否能完成拓扑排序
  2. 计算强连同分量方法
  3. 改进DFS,看每次搜索出现重复搜索点

拓扑排序

算法导论中给出了DFS完成时间的伪代码,这里更简单的说,不断提取出度为0的点(度为0的点不受其它点制约),然后更新向量节点的度数,看最终能否完成拓扑排序,判断是否有环,没有环存在即可输出拓扑排序。

代码

class Solution {
public:
	// 不断删除度为0的点,BFS方式
	vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
		vector<int> order;
		vector<int> outd(numCourses, 0);
		unordered_map<int, vector<int>> graph;
		for (auto& ele : prerequisites){
			graph[ele.second].push_back(ele.first);
			outd[ele.first]++;
		}

		queue<int> q;
		for (int i = 0; i < numCourses; ++i){
			if (outd[i] == 0){
				q.push(i);
			}
		}

		while (!q.empty()) {
			int t = q.front();
			q.pop();
			order.push_back(t);
			for (int i = 0; i < graph[t].size(); ++i){
				outd[graph[t][i]]--;
				if (outd[graph[t][i]] == 0){
					q.push(graph[t][i]);
				}
			}
		}
		return (order.size() == numCourses) ? order : vector<int>();
	}
};

 

发表评论