拓扑排序

2018-04-17 17:03:33


拓扑排序

概念

我们知道有一种图叫有向无环图(DAG),这个图有很好的性质,那么如何判断一个图是否是有向无环图呢?答案是对 AOV 网络构造它的 拓扑有序序列(topological order sequence),即将各个顶点排列成一个线性有序的序列,使得 AOV 网络中所有存在的前驱和后继关系都能得到满足。

一般一个工程可以分成若干个子工程,这些子工程称为 活动(activity)。完成了这些活动,整 个工程就完成了。例如,计算机专业课程的学习就是一个工程,每门课程的学习就是整个工程中 的一个活动。

实际上,可以用有向图来表示一个工程。在这种有向图中,用顶点表示活动,用有向边<u, v> 表示活动 u 必须先于活动 v 进行。

这种有向图叫做顶点表示活动的网络(activity on vertices),记 作 AOV 网络。

在 AOV 网络中,如果存在有向边<u, v>,则活动 u 必须在活动 v 之前进行,并称 u 是v 的直 接前驱 直 接前驱(immediate predecessor),v 是 u 的 直接后继(immediate successor)。如果存在有向路径<u, u 1 , u 2 , …, u n , v>,则称 u 是 v 的 前驱(predecessor),v 是 u 的 后继(successor)。

这种前驱与后继的关系有 传递性(transitivity)。例如,如果活动 v 2 是v 1 的后继,v 3 是 v 2 的后 继,那么活动 v 3 也是 v 1 的后继。此外,任何活动不能以它自己作为自己的前驱或后继,这种特性 称为 反自反性(irreflexivity)。

从前驱与后继的传递性和反自反性可以看出,AOV 网络中不能出现有向回路(或称为有向 环)。

不含有向回路的有向图称为 有向无环图(DAG, directed acyclic graph)。 在 AOV 网络中如果出现了有向回路,则意味着某项活动以自己作为先决条件,这是不对的。

如果设计出这样的流程图,工程将无法进行。对于程序而言,将陷入死循环。

因此,对于给定的 AOV 网络,必须先判断它是否是有向无环图。

例如,对 2.25(b)所示的学生选课工程图进行拓扑排序,得到的拓扑有序序列为: C 1 ,C 2 ,C 3 ,C 4 ,C 5 ,C 6 ,C 8 ,C 9 ,C 7

或:C 1 ,C 8 ,C 9 ,C 2 ,C 5 ,C 3 ,C 4 ,C 7 ,C 6 。

学生必须按照拓扑有序的顺序选修课程,才能保证学习任何一门课程时其先修课程都已经学 过。从该例子可以看出,一个 AOV 网络的拓扑有序序列可能不唯一。

拓扑排序的实现

BFS

我们用链式前向星存图,记录每个节点的入度,每次选出入度为0的点放入队列中,每次出队一个点,将这个点能到达的所有点的入度减1,如果哪个能到达的点入度变为0,入队。如果在过程中哪一刻没有入度为0的点,则说明此图不是一个DAG。

POJ2367

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int N=101;
queue<int>q;
int n,head[N],cnt,in[N],fail,ans[N];
struct tu{
    int to,ne;
}e[N*N];
inline void add(int u,int v){
    cnt++;
    e[cnt].to=v;
    e[cnt].ne=head[u];
    head[u]=cnt;
}
void topsort(){
    for(int i = 1;i<=n;i++){
        if(!in[i]) q.push(i);
    }
    while(!q.empty()){
        int i = q.front();
        q.pop();
        ans[++fail]=i;
        for(int j = head[i];j;j=e[j].ne){
            int v = e[j].to;
            in[v]--;
            if(!in[v]) q.push(v);
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        int x;
        while(scanf("%d",&x) && x){
            add(i,x);
            in[x]++;
        }
    }
    topsort();
    for(int i = 1;i<=n;i++) printf("%d ",ans[i]);
    return 0;   
}