算法学习 拓扑排序(TopSort)

时间:2023-02-02 14:39:05

拓扑排序

一、基本概念

在一个有向无环图(Directed Acyclic Graph, DAG)中,规定< u,v > 表示一条由u指向v的的有向边。要求对所有的节点排序,使得每一条有向边 < u,v>中u都排在v的前面。

换个形象点的解释,我们在学习一门课程之前,应该需要一定的预备知识,比如在学习B课程之前我们需先学习A(后用< X,Y > 表示X课程是Y课程的预备知识,其实与上述有序偶的含义相同),则有 < A,B >。我们还有 < C,B >, < B,D >, < E,D >, < D,F >, < D,G >, < H,G >. 现在要求你合理安排A-H这些课程的学习顺序。这个任务的要求实际上就是对A-H进行拓扑排序。
算法学习 拓扑排序(TopSort)

为何要求这个图是DAG呢?不难想象,如果上面的课程变成 < A,B >, < B,C >, < C,D > …… < H,A >. (即A-H成有向环)那么我们就无法判断出先学哪个课程了。
算法学习 拓扑排序(TopSort)

二、算法实现

以上面给课程排序为例,我们首先要学的,一定是一个不需要任何预备知识的课程,然后学完这个课程之后,根据边的关系再看有哪些新的课程可以学习,同时我们还要清楚,学完一门课程后,就不需要再次学习这一门课程了

我们将其与图做个类比。
不需要预备知识的课程-> 入度为0的点
新的课程->所指向的下一个点
每门课之学一次->从图中删除节点 && 从图中删除有向边

接着再根据图类比结果决定存储的数据
入度为0的点->需要存储每个节点的入度
所指向的下一个点->需要存每个节点的后继
删除节点与有向边-> 这里讨论一下:
如果我们真的删除了节点和有向边,那就意味着无法在找到这些数据了。因为我们还需要判断是否形成了DAG,最保险的做法是将下一个节点的入度-1。如果发现某个节点的入度为-1了,表明存在有向环,那么说明不存在与拓扑排序。

根据存储的数据选择数据结构(具体情况具体分析,灵活变通)
节点入度->数组
节点后继->vector

三、例题讲解

UVA.10305 Ordering Tasks
有n个点,m条边,给n个顶点做拓扑排序。

#include <iostream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#define nmax 200
#define MEM(x) memset(x,0,sizeof(x))
using namespace std;
vector<int> v[nmax];
int indegree[nmax];
int n;
bool suc = true;
queue<int> ans;
void topsort()
{
queue<int> q;
while(1){
for(int i = 1; i<=n ;++i){
if(indegree[i] == 0){
q.push(i);
ans.push(i);
indegree[i] = -1;
}
}
if(q.empty()) break;
while(!q.empty()){
int t = q.front(); q.pop();
for(int j = 0;j<v[t].size();++j){
int tt = v[t][j];
if(indegree[tt] == -1){
suc = false;
break;
}else indegree[tt]--;
}
v[t].clear();
if(!suc) break;
}
if(!suc) break;
}
if(ans.size() <n){
suc =false;
return;
}
}
void output()
{
bool isfirst = true;
while(!ans.empty()){
int t = ans.front(); ans.pop();
if(isfirst){
printf("%d",t);
isfirst = false;
}else
printf(" %d",t);
}
printf("\n");
}
int main()
{
//freopen("in.txt","r",stdin);
int m;
while(scanf("%d%d",&n,&m) ==2 && (n||m)){
MEM(indegree);
suc = true;
int a,b;
for(int i = 0; i<m; ++i){
scanf("%d%d",&a,&b);
indegree[b]++;
v[a].push_back(b);
}
topsort();
if(suc) output();
else printf("failed\n");
}
return 0;
}

基本方法是,indegree表示入度表,vector存后继节点。在topsort函数中,制造一个辅助队列,首先从入度表中找到入度为0的点作起点,并且置入度为-1。接着依次处理队列中的节点,首先根据他们的后继,将其后继节点的入度依次减1,若其后继节点中的入度存在-1的,说明成环,则不存在拓扑排序。紧接着再从入度表中找到入度为0的节点,加入到队列中,直到队列空。当退出while循环的时候,需要检查ans答案队列中是否已经有全部的节点,若其数量为n,则表明存在拓补排序,否则不存在。

当然本题满足存在topsort。下面给出三组例子,可以检验一下自己程序的健壮性。

算法学习 拓扑排序(TopSort)

Graph1
不存在拓扑排序,节点2,3,4成环

4 5
1 3
1 2
2 3
3 4
4 2

Graph2
不存在拓扑排序,节点1,2,3成环

5 6
5 1
1 2
2 3
3 1
1 4
4 3

Graph3
存在拓扑排序

13 14
1 2
1 6
1 7
3 1
3 4
4 6
6 5
8 7
9 8
7 10
10 11
10 12
10 13
12 13