定义
在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。
算法步骤
在任一有向无环图中,必然存在入度为0的顶点。否则,每个顶点都至少有一条入边,这意味着包含环路。
转换成算法:
step1:统计图中每个节点的入度,生成入度表 indegrees。
step2:借助一个队列 queue,将所有入度为0的节点入队。
step3:当queue非空时,依次将队首节点出队,依次将队首节点的所有邻接节点cur的入度-1,即 indegrees[cur] -= 1;
当入度-1后邻接节点cur的入度为0,说明cur所有的前驱节点已经被 “删除”,此时将cur入队。
若整个课程安排图是有向无环图,则所有节点一定都入队并出队过,即完成拓扑排序。换个角度说,若图中存在环,一定有节点的入度始终不为0。
应用
拓扑排序通常用来“排序”具有依赖关系的任务;
或者用来判断有向图中是否有环
例题
现在你总共有 n 门课需要选,记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件,返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序,你只要返回一种就可以了。如果不可能完成所有课程,返回一个空数组。
输入
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此,一个正确的课程顺序是[0,1,2,3] 。另一个正确的排序是[0,2,1,3]
代码
class Solution {
public:
static const int N = 100010;
int h[N], e[N], ne[N], idx;
int d[N];
int n;
int q[N];
int hh, tt;
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
d[b] += 1;
}
bool topSort()
{
hh = tt = 0;
// cout << "入度0的点" << " ";
for(int i = 0; i < n; i++)
{
if(d[i] == 0) {
q[tt++] = i;
//cout << i << " ";
}
}
//cout << endl;
while(hh < tt)
{
int t = q[hh];
hh++;
//cout << "cur node=" << t << endl;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
//cout << t << "-->" << j << ", dist=" << d[j] << " ";
d[j]--;
if(d[j] == 0)
{
q[tt++] = j;
}
}
}
if(tt == n) return true;
else return false;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> res;
if(numCourses == 1)
{
res.push_back(0);
return res;
}
n = numCourses;
memset(h, -1, sizeof(h));
memset(d, 0, sizeof(d));
for(int i = 0; i < prerequisites.size(); i++)
{
int a = prerequisites[i][0], b = prerequisites[i][1];
add(a, b);
}
bool t = topSort();
if(t != false)
{
for(int i = tt - 1; i >= 0; i--)
{
res.push_back(q[i]);
}
}
return res;
}
};