拓扑排序（附LeetCode题目）
算法期中考到一题关于拓扑序的题目，觉得很值得一写。
1.什么是拓扑序？
对一个有向无环图进行拓扑排序，假如图中存在一条从顶点A到顶点B的路径，则拓扑序中顶点A出现在顶点B的前面。要注意的是，这是对有向无环图而言的，假如图是有环的，拓扑序就无从谈起了。在这道题目中，已经假定了图是一个无环图。因此不需要进行检查。
2.怎么得出拓扑序？
有两种方法，分别基于BFS和DFS，时间复杂度都是O(|V| + |E|)。以这道题作为例子分别说一下：
（1）BFS
这是我最先想到的方法。我们需要：一个数组，统计每个顶点的入度数；一个队列用于bfs。首先遍历一次所有的边，将每个顶点的入度数都求出来，而入度数为0的顶点说明没有其他顶点指向它。因此先把入度数为0的顶点放进队列中。
接着用一个循环每次从队头取出front，把它放进返回结果的列表中。然后遍历一遍所有的边，假如当前边对应的起始顶点为front，则将边对应的终结顶点的入度数减1（我们把front放进结果中，也视作把front从图中去掉了，那入度数自然要减1了）。如果一个顶点的入度数变为0，说明已经没有其他顶点指向它了，就可以把它放入队尾。一直到队列为空时，说明拓扑序已经得到了。
代码如下：
class Solution {
public:
vector<int> topologicalSort(int n, vector<pair<int, int> >& edges) {
vector<int> res;
int * in_degree = new int[n];
queue<int> q;
for (int i = ; i < n; i++) {
in_degree[i] = ;
}
for (int i = ; i < edges.size(); i++) {
in_degree[edges[i].second]++;
}
for (int i = ; i < n; i++) {
if (in_degree[i] == ) {
q.push(i);
}
}
while (!q.empty()) {
int front = q.front();
q.pop();
res.push_back(front);
for (int i = ; i < edges.size(); i++) {
if (edges[i].first == front) {
in_degree[edges[i].second]--;
if (in_degree[edges[i].second] == ) {
q.push(edges[i].second);
}
}
}
}
return res;
}
};
（2）DFS
据说这是神书《算法导论》中提到的算法：用深度搜索来遍历整个图，采用一个数组来保存每个顶点完成的时间，这样这个数组就存放了按先后顺序访问完成的顶点了。然后我们按照顶点访问的完成时间从大到小排序，得到的就是一个拓扑序了，具体证明如下（来自其他博客）：
在这道题中，肯定不用真的开一个数组啊，代码如下：
class Solution {
public:
vector<int> topologicalSort(int n, vector<pair<int, int> >& edges) {
vector<int> res;
stack<int> s;
int * isVisited = new int[n];
for (int i = ; i < n; i++) {
isVisited[i] = ;
}
for (int i = ; i < n; i++) {
if (!isVisited[i]) dfs(edges, s, isVisited, i);
}
while (!s.empty()) {
res.push_back(s.top());
s.pop();
}
return res;
}
void dfs(vector<pair<int, int> >& edges, stack<int> & s, int * isVisited, int u) {
isVisited[u] = ;
for (int i = ; i < edges.size(); i++) {
if (edges[i].first == u && !isVisited[edges[i].second]) {
dfs(edges, s, isVisited, edges[i].second);
}
}
s.push(u);
}
};
这样就得出结果了。（个人认为还是BFS易理解一点）
3.针对这道题......
So sad，以上两种方法在这道题都TLE了，因为对于每个顶点，我们都需要遍历一次边的数组，要想节省时间，我们就要花费空间，使对于每个顶点，我们只需要考虑以它为起始点的边。
真正能AC的代码：
class Solution {
public:
vector<int> topologicalSort(int n, vector<pair<int, int> >& edges) {
vector<int> res;
vector<vector<int> > newedges(n, vector<int>());
queue<int> q;
vector<int> in_degree(n, );
for (int i = ; i < edges.size(); i++) {
in_degree[edges[i].second]++;
newedges[edges[i].first].push_back(edges[i].second);
}
for (int i = ; i < n; i++) {
if (in_degree[i] == ) {
q.push(i);
}
}
while (!q.empty()) {
int front = q.front();
q.pop();
res.push_back(front);
for (int i = ; i < newedges[front].size(); i++) {
in_degree[newedges[front][i]]--;
if (in_degree[newedges[front][i]] == ) q.push(newedges[front][i]);
}
}
return res;
}
};
4.抛开这道题目——有环情况的判断
可以利用上面的dfs方法，比如isVisited这个数组，我们可以多增一种情况，比如0为未访问，1为已访问，-1为正在访问，当dfs搜索时遇到了一条边终止顶点对应的isVisited元素为-1时，就说明图中有环了（为-1说明我们是从这个顶点开始dfs的，现在又遇到了这个顶点...）。
另外一种判断图是否有环的方法，借助bfs（dfs也可，但既然用了dfs，直接用上面的方法好了），假如“生成拓扑序”后，还有顶点不在这个“拓扑序”里面，则图就有环了（加双引号是因为不能真正称作“拓扑序”啊）。
LeetCode上有相应的题目，需要判断有无环（可以试试上面两种判断方法）：
（1）https://leetcode.com/problems/course-schedule/description/
用了上面的第二种方法：
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
int size = ;
vector<int> degree(numCourses, );
queue<int> q;
for (int i = ; i < prerequisites.size(); i++) {
degree[prerequisites[i].second]++;
}
for (int i = ; i < numCourses; i++) {
if (degree[i] == ) {
q.push(i);
}
}
while (!q.empty()) {
int front = q.front();
q.pop();
size++;
for (int i = ; i < prerequisites.size(); i++) {
if (prerequisites[i].first == front) {
if (--degree[prerequisites[i].second] == ) q.push(prerequisites[i].second);
}
}
}
return size == numCourses;
}
};
（2）https://leetcode.com/problems/course-schedule-ii/description/
用了第一种方法：
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> res;
vector<int> isVisited(numCourses, );
vector<vector<int>> v(numCourses, vector<int>());
for (int i = ; i < prerequisites.size(); i++) {
v[prerequisites[i].second].push_back(prerequisites[i].first);
}
stack<int> s;
bool isCircled = false;
for (int i = ; i < numCourses; i++) {
if (!isVisited[i]) {
dfs(i, s, v, isVisited, isCircled);
}
if (isCircled) {
break;
}
}
if (isCircled) return vector<int>();
while (!s.empty()) {
res.push_back(s.top());
s.pop();
}
return res;
}
void dfs(int u, stack<int> &s, vector<vector<int>>& v, vector<int> &isVisited, bool &isCircled) {
if (isCircled) return;
isVisited[u] = -;
for (int i = ; i < v[u].size(); i++) {
if (isVisited[v[u][i]] != ) {
if (isVisited[v[u][i]] == ) {
dfs(v[u][i], s, v, isVisited, isCircled);
}
else {
isCircled = true;
return;
}
}
}
isVisited[u] = ;
s.push(u);
}
};
最新文章
- ORACLE导入、导出命令使用方法
- 如何为Eclipse安装主题(Color Theme)
- centos之开放80端口
- Excel保护工作表
- Jquery各个版本的区别
- codeforces 425E
- Java的IO操作---File类
- 上传文件及$_FILES的用法实例
- [转]天龙八部的BillingServer
- 【CSS3】---样式小技巧
- 自己写CPU第九阶段（5）——实现负载存储指令2（改变运行阶段）
- hdu 1728 搜索求最少的转向次数
- gcc及其选项详解 【转载】
- 16 Content Provider总结
- WebApi生成在线API文档--Swagger
- sql 语句中count()有条件的时候为什么要加上or null
- AI R-CNN目标检测算法
- linux内存源码分析 - 零散知识点
- MyBatis-获取 xxxMapper
- Android应用程序性能优化Tips