文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C++详细讲解图的拓扑排序

2024-04-02 19:55

关注

一、前言

且该序列必须满足下面两个条件:

  1. 每个顶点出现且只出现一次。
  2. 若存在一条从顶点 x到顶点 y的路径,那么在序列中顶点 x 出现在顶点 y的前面。

拓扑排序只适用于 AOV网 (有向无环图)

若图中有环,则一定不存在拓扑序。

可以证明,一个有向无环图,一定存在一个拓扑序列。有向无环图,又被称为拓扑图。

入度: 即有多少条边指向自己这个节点。

出度: 即有多少条边从自己这个节点指出去。

二、算法流程

算法流程:

用队列来执行 ,初始化所有入度为0的顶点入队。

主要由以下两步循环执行,直到不存在入度为 0 的顶点为止

选择一个入度为 0 的顶点,并将它输出;

删除图中从顶点连出的所有边

循环结束

若输出的顶点数小于图中的顶点数,则表示该图存在回路,即无法拓扑排序,

否则,输出的就是拓扑序列 (不唯一)

模板如下:

1.数组模拟队列实现拓扑排序

bool topsort()
{
    int hh = 0, tt = -1;
    // in[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )// 将所有入度为0的点加入队列
        if (in[i]==0)
            top[ ++ tt] = i;
    while (hh <= tt)
    {
        int t = top[hh ++ ];//找到入度为0的队头
  //遍历一下以t为头节点的的单链表,给每一个结点都要减去1,并再次找到入度为0的点
        for (int i = h[t]; i != -1; i = ne[i])
        {
        // 遍历 t 点的出边
            int j = e[i];
            if (-- in[j] == 0)//将入度减1,如果 j 入度为0,加入队列当中
                top[ ++ tt] = j;
        }
    }
    // 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
    return tt == n - 1;
}

2.使用STL queue实现拓扑排序

bool topsort(){
    queue<int> q;
    int t;
    for(int i = 1;i <= n; ++i)// 将所有入度为0的点加入队列
        if(in[i] == 0) q.push(i);
    while(q.size()){
        t = q.front();//每次取出队列的首部
        top[cnt] = t;//加入到 拓扑序列中
        cnt ++; // 序列中的元素 ++
        q.pop();
        for(int i = h[t];i != -1; i = ne[i]){
            // 遍历 t 点的出边
            int j = e[i];
            in[j] --;// j 的入度 --
            if(in[j] == 0) q.push(j); //如果 j 入度为0,加入队列当中
        }
    }
    if(cnt < n) return 0;
    else return 1;
}

时间复杂度 O(n+m), n表示点数,m表示边数

三、有向图的拓扑排序

给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。

思路

我们每次找到入读为0的点,然后把他插入到队列里,然后将这个点删除,这也就意味着这个点连接的下一个点(可能是多个)的入度就会减1。

这个时候,我们就进入了下一轮。

我们因为前面将一个点删除了,那么它指向的点的入度就会都减去1,所以,就会出现新的点的入度为0,这个点显然是因为它的入度小,所以它理所应当的排在拓扑序里面在第二位。当前面的一个点没有了被删除了,那它就要首当其冲了。

和图的BFS思路很像,但是加了搜索的规则(即入度为零的先被搜索)可以看点这里

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],h[N],idx,in[N],n,m,top[N],cnt = 1;
// e,ne,h,idx 邻接表模板
// in 代表每个元素的入度
// top是拓扑排序的序列,cnt代表top中有多少个元素
void add(int a,int b){
    e[idx] = b; ne[idx] = h[a];h[a] = idx ++;
}
bool topsort(){
    queue<int> q;
    int t;
    for(int i = 1;i <= n; ++i)// 将所有入度为0的点加入队列
        if(in[i] == 0) q.push(i);
    while(q.size()){
        t = q.front();//每次取出队列的首部
        top[cnt] = t;//加入到 拓扑序列中
        cnt ++; // 序列中的元素 ++
        q.pop();
        for(int i = h[t];i != -1; i = ne[i]){
            // 遍历 t 点的出边
            int j = e[i];
            in[j] --;// j 的入度 --
            if(in[j] == 0) q.push(j); //如果 j 入度为0,加入队列当中
        }
    }
    if(cnt < n) return 0;
    else return 1;
}
int main(){
    int a,b;
    cin >> n >> m;
    memset(h,-1,sizeof h);//给头节点赋值为-1;
    while(m--){
        cin >> a >> b;
        add(a,b);
        in[b] ++;// a -> b , b的入度++
    }
    if(topsort() == 0) cout << "-1";
    else {
        for(int i = 1;i <= n; ++i){
            cout << top[i] <<" ";
        }
    }
    return 0;
}

到此这篇关于C++详细讲解图的拓扑排序的文章就介绍到这了,更多相关C++拓扑排序内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯