浙江财经大学
信工学院ACM集训队

浅谈拓扑排序

本文由 Ocrosoft 于 2016-07-31 12:05:55 发表

PPT下载:本地下载

定义:

拓扑排序就是对一个有向无环图(DAG)的顶点进行排序,使得如果有一条有向边:u->v,那么排序后顶点u一定在顶点v的前面。

排序过程:

2

对于上图,有1->2,2->3,4->3这样三条边。

1.对于第一条边,排序时把2排在1的后面,排序结果是这样:

1->2

2.对于第二条边,排序时,3要在2的后面,排序结果:

1->2->3

3.对于第三条边,排序时3要在4的后面,但是14,24的相对位置并没有要求,所以排序结果可以是:

1->2->4->3

也可以是:

1->4->2->3

还可以是:

4->1->2->3

也就是说,对于一个可以排序的图来说,排序结果并不一定唯一

排序结果唯一性:

这里涉及到离散数学中的偏序与全序的概念,不做解释。参考:CSDN

可排序图:

上面说的,有向无环图一定可以拓扑排序,那么为什么无向无环图,有向有环图等就不能排序呢?

无向图:拓扑排序是要有相对位置关系的,无向自然不能排序。

有环图:例如:1->2->3->1,这样一个环,2要在1后面,3要在2后面,1又要在3后面,但是前面关系保证了13前面,这样出现矛盾,所以无法排序。

排序基础:

保存图,需要使用邻接矩阵或者邻接表,比较基础,这里不介绍,可以看PPT

入度:在实现的时候需要用到,入度就是指向这个顶点的有向边的数量。有向无环图,保证了至少一个点的入度为0

实现思路(Kahn):

在上面说过,DAG一定有顶点入度为0

一开始创建一个队列,把初始时入度为0的点放入队列,后续操作如下图。

1

操作完毕后,输出的那些顶点就是拓扑排序结果。(如果题目有其他要求,就不输出而进行其他操作)

原理:

入度为0,说明没有指向这个顶点的边,也就是说,这个顶点的前面没有其他顶点了。看一下定义,如果有u->v,那么v一定在u的后面,现在对v来说,不存在u,那么可以毫无顾虑地输出v

实现代码:

int n,m,t;//顶点数量,边数量,临时变量
bool mp[505][505];//邻接表保存边信息
int indegree[505];//保存入度
queue<int> q;
void toposort()
{
    while(!q.empty())
    {
        t=q.front();
        q.pop();//第一个输出不能输出空格
        printf("%d ",t);//输出这个顶点
        for(int i=1; i<=n; i++)//遍历这个节点的邻接表
        {
            if(mp[t][i])//如果找到一条边
            {
                indegree[i]--;//删除边,即相应节点入度-1
                if(!indegree[i])q.push(i);//如果入度为0,放入队列
            }
        }
    }
    printf("\n");
}
int main()
{
    while(cin>>n>>m)
    {
        ms(indegree),ms(mp);//初始化
        while(!q.empty())q.pop();//清空队列
        for(int i=0; i<m; i++)//读取边,修改入度
        {
            int a,b;
            cin>>a>>b;
            if(!mp[a][b])mp[a][b]=1,indegree[b]++;//如果没有记录过,记录并且入度+1
        }
        for(int i=1; i<=n; i++)//查找入度为0的点
            if(!indegree[i])q.push(i);//放入队列
        toposort();
    }
    return 0;
}

输入:

4 3
1 2
2 3
4 3

输出:

1 4 2 3

例题1HDU 1285 确定比赛名次):

这个题目用的是邻接矩阵

参考题解:http://www.ocrosoft.com/?p=541

例题2HDU 5695 Gym Class):

这个题目用得是邻接表

参考题解:http://www.ocrosoft.com/?p=551

欢迎转载,请保留出处与链接。Ocrosoft » 浅谈拓扑排序

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址