数据结构与算法-图论-拓扑排序

前置芝士

概念

拓扑排序(Topological Sorting)是对有向无环图(DAG,Directed Acyclic Graph)的顶点进行排序的一种算法。它将图中的所有顶点排成一个线性序列,使得对于图中的任意一条有向边 (u, v),顶点 u 在序列中都出现在顶点 v 之前。也就是说,拓扑排序的结果反映了图中顶点之间的先后依赖关系。

需要注意的是,只有有向无环图才有拓扑排序,因为如果图中存在环,就无法满足先后顺序的要求。

算法流程

Kahn 算法(基于入度的算法)

-1统计入度:遍历图中的所有边,统计每个顶点的入度(即指向该顶点的边的数量)。

-2初始化队列:将所有入度为 0 的顶点加入一个队列中。

-3拓扑排序过程

-从队列中取出一个顶点,并将其加入拓扑排序的结果序列中。

-对于该顶点的所有邻接顶点,将它们的入度减 1。

-如果某个邻接顶点的入度变为 0,则将其加入队列。

-4检查结果:重复步骤 3,直到队列为空。如果最终拓扑排序结果序列中的顶点数量等于图中的顶点数量,则说明图是有向无环图,得到的序列就是拓扑排序结果;否则,图中存在环,不存在拓扑排序。

具体的 C++ 算法

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

// 拓扑排序函数

vector<int> topologicalSort(int n, vector<vector<int>>& graph) {

    // 存储每个顶点的入度

    vector<int> inDegree(n, 0);

    // 存储拓扑排序的结果

    vector<int> result;

    // 队列用于存储入度为 0 的顶点

    queue<int> q;

    // 统计每个顶点的入度

    for (int i = 0; i < n; ++i) {

        for (int neighbor : graph[i]) {

            ++inDegree[neighbor];

        }

    }

    // 将所有入度为 0 的顶点加入队列

    for (int i = 0; i < n; ++i) {

        if (inDegree[i] == 0) {

            q.push(i);

        }

    }

    // 拓扑排序过程

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        result.push_back(u);

        // 遍历该顶点的所有邻接顶点

        for (int v : graph[u]) {

            --inDegree[v];

            if (inDegree[v] == 0) {

                q.push(v);

            }

        }

    } 

    // 如果拓扑排序结果的长度不等于顶点数量,说明图中存在环

    if (result.size() != n) {

        return {}; // 返回空向量表示不存在拓扑排序

   }

return result;

}

int main() {

    int n = 6; // 顶点数量

    vector<vector<int>> graph(n);

    // 添加有向边

    graph[5].push_back(2);

    graph[5].push_back(0);

    graph[4].push_back(0);

    graph[4].push_back(1);

    graph[2].push_back(3);

    graph[3].push_back(1);

    vector<int> result = topologicalSort(n, graph);

    if (result.empty()) {

        cout << "图中存在环,不存在拓扑排序。" << endl;

    } else {

        cout << "拓扑排序结果:";

        for (int vertex : result) {

            cout << vertex << " ";

        }

        cout << endl;

    }

return 0;

}

应用场景

任务调度:在项目管理中,任务之间可能存在先后依赖关系。可以将任务看作图的顶点,任务之间的依赖关系看作有向边,通过拓扑排序可以确定任务的执行顺序,确保在执行某个任务之前,其所有前置任务都已经完成。

课程安排:在学校的课程体系中,某些课程可能需要先修其他课程。可以将课程看作顶点,先修关系看作有向边,使用拓扑排序可以得到一个合理的课程学习顺序。

编译顺序:在软件开发中,源文件之间可能存在依赖关系。通过拓扑排序可以确定源文件的编译顺序,确保在编译某个文件之前,其所有依赖的文件都已经编译完成。

数据流分析:在计算机科学中,数据流图可以表示数据在系统中的流动和处理过程。拓扑排序可以用于确定数据处理的顺序,确保数据在被处理之前已经被正确生成。

练习题:

家谱图:

标准的板子题:

代码:

#include<bits/stdc++.h>

using namespace std;

unordered_map<int,vector<int>>e;

const int N=110;

queue <int> Q;

int in[N];

int n;

void toposort() {

for(int i = 1; i <= n; i++) {

if(in[i] == 0) {

printf("%d ", i);

Q.push(i);

}

}

while(Q.size()) {

int u = Q.front(); Q.pop();

for(int v:e[u]) {

in[v]--;

if(in[v] == 0) {

printf("%d ", v);

Q.push(v);

}

}

}

}

int main(){

    cin>>n;

    for(int i=1;i<=n;i++){

        int tmp=0;

        while(cin>>tmp,tmp!=0){

            e[i].push_back(tmp);

            in[tmp]++;

        }

    }

    toposort();

    

}

奖金

分析:

差分约束的简化版,这里使用拓普排序,如果u->v,那么f[v]=max(f[v],f[u]+1);

为什么是max?因为还有其他的u1连接到了v,万一u1的值更大,那么v就要满足>u1

所以要求的是满足一系列v>u,u1,u2....的v的最小值

至于如果把100搞定,当然可以直接把初值设置为100或者答案最后加100就好了

同时归纳下:

如果边权无限制,只有使用差分约束了

如果边权非负,那就可以使用tarjan算法

如果边权为正数,就可以使用拓扑排序来做了!

代码

可达性统计:

分析:


求拓扑序,然后倒序求出f[i],这里的f[i]表示i之后可达的点的集合

f[i]=所以i的子节点能到的点的并集,这里的集合我们用string来模拟01001的二进制串来表示

代码:

#include<bits/stdc++.h>

using namespace std;

// 定义常量 N 作为最大顶点数

const int N = 30010;

// n 表示图的顶点数量,m 表示图的边数量

int n, m;

// in 数组用于记录每个顶点的入度,入度即指向该顶点的边的数量

int in[N];

// q 数组作为队列使用,用于拓扑排序过程中存储入度为 0 的顶点

int q[N];

// h 是队列的头指针,初始化为 0;t 是队列的尾指针,初始化为 -1

int h = 0, t = -1;

// f 数组是一个 bitset 数组,f[i] 表示从顶点 i 出发能够到达的所有顶点的集合// bitset 是一种高效存储二进制位的数据结构,这里用它可以方便地进行位运算

bitset<N> f[N];

// e 是一个无序映射,用于存储图的邻接表// e[u] 存储的是从顶点 u 出发的所有边指向的顶点

unordered_map<int, vector<int>> e;

// 拓扑排序函数,用于对有向图进行拓扑排序

bool toposort() {

    // 遍历所有顶点,将入度为 0 的顶点加入队列

    for (int i = 1; i <= n; i++) {

        if (!in[i]) {

            // 入度为 0 的顶点入队,尾指针后移

            q[++t] = i;

        }

    }

    // 当队列不为空时,持续进行处理

    while (h <= t) {

        // 取出队头元素

        int u = q[h++];

        // 遍历从顶点 u 出发的所有边指向的顶点

        for (int v : e[u]) {

            // 将顶点 v 的入度减 1,表示移除从 u 到 v 的边

            --in[v];

            // 如果顶点 v 的入度变为 0,将其加入队列

            if (!in[v]) {

                q[++t] = v;

            }

        }

    }

    // 这里原代码直接返回 1,存在问题,正确应该判断是否拓扑排序成功

    // 若拓扑排序成功,队列中应该存储了所有顶点,即 t == n - 1

return t == n - 1;

}

int main() {

    // 读取图的顶点数量 n 和边的数量 m

    scanf("%d%d", &n, &m);

    // 循环读取每条边的信息

    for (int i = 0; i < m; i++) {

        int u, v;

        // 读取边的起点 u 和终点 v

        scanf("%d%d", &u, &v);

        // 将终点 v 添加到起点 u 的邻接表中

        e[u].push_back(v);

        // 终点 v 的入度加 1

        in[v]++;

    }

    // 调用拓扑排序函数

    if (!toposort()) {

        // 如果拓扑排序失败,说明图中存在环,输出错误信息并退出程序

        cerr << "图中存在环,无法进行可达性统计。" << endl;

        return 1;

    }

    // 按照拓扑排序结果的逆序遍历顶点

    for (int i = n - 1; i >= 0; i--) {

        // 取出当前处理的顶点

        int u = q[i];

        // 顶点 u 能到达自身,将 f[u] 的第 u 位设为 1

        f[u][u] = 1;

        // 遍历从顶点 u 出发的所有边指向的顶点

        for (int v : e[u]) {

            // 通过位运算将 f[v] 能到达的顶点合并到 f[u] 中

            f[u] |= f[v];

        }

    }

    // 遍历所有顶点,输出每个顶点能到达的顶点数量

    for (int i = 1; i <= n; i++) {

        // count() 方法返回 bitset 中 1 的个数,即能到达的顶点数量

        cout << f[i].count() << endl;

    }

return 0;

}

车站分级:

分析

这道题可以通过建立有向图并进行拓扑排序来求解火车站最少的级别数,以下是具体思路:

建立有向图思路

顶点含义:将每个火车站看作图中的一个顶点,编号为 1 到 n ,对应图中的 n 个顶点。

边的构建:对于每一趟车次,设其停靠站为 si1​,si2​,⋯,sisi​​(按编号从小到大排列)。对于这趟车次的任意两个停靠站 sij​ 和 sik​(j<k),在图中添加有向边 (sij​,sik​)。这是因为根据题目条件,如果一趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠,添加边表示了这种级别上的 “约束” 关系。更通俗地理解,就是停靠靠前的车站可以 “指向” 停靠靠后的车站,意味着靠前车站的级别小于等于靠后车站的级别。

边的隐含意义:有向边 (u,v) 表示火车站 u 的级别小于等于火车站 v 的级别。通过这样构建有向图,就将车次运行情况转化为了图中顶点之间的关系。

拓扑排序思路

入度统计:在构建好有向图后,统计每个顶点(即每个火车站)的入度,入度表示有多少条边指向该顶点。

初始处理:把所有入度为 0 的顶点(即没有其他顶点的级别小于它的火车站)加入队列。这些顶点可以看作是最低级别的候选者。

拓扑排序过程:

从队列中取出一个顶点,这个顶点代表的火车站可以被划分为一个级别。

对于该顶点的所有邻接顶点(即由该顶点出发的边指向的顶点),将它们的入度减 1。这是因为已经处理了当前顶点,与它相关的 “约束” 减少了。

如果某个邻接顶点的入度变为 0,则将其加入队列。这表示在处理完当前级别后,这个顶点所代表的火车站也可以被确定为一个新的级别(在当前已处理的级别基础上)。

结果确定:重复上述步骤,直到队列为空。每一轮从队列中取出顶点并处理的过程,相当于确定了一个新的级别。最终统计处理的轮数,这个轮数就是 n 个火车站最少划分的级别数 。因为拓扑排序的特性保证了在处理过程中,先处理的顶点级别不高于后处理的顶点级别,通过这种方式能得到满足车次运行要求的最少级别划分。

建立边的及技巧

9 2

4 1 3 5 6

这里的1->3->5->6,可以如下优化

代码:

#include <bits/stdc++.h>

using namespace std;

const int N=2010;

unordered_map<int,vector<pair<int,int>>>e;

int n,m;

int in[N];

bool st[N];

int q[N];

int dis[N]={0};

int h=0,t=-1;

void toposort(){

    for(int i=1;i<=n;i++)

        if(!in[i])q[++t]=i;

    while(h<=t){

        int u=q[h++];

        for(auto ww:e[u]){

            int v=ww.first;

            if(--in[v]==0){

                q[++t]=v;

            }

        }

    }

}int main(){

    cin>>n>>m;

    for(int i=1;i<=m;i++){

        memset(st,0,sizeof st);

        int cnt;

        cin>>cnt;

        int start=n,end=1;

        for(int j=0;j<cnt;j++){

            int stp;

            scanf("%d",&stp);

            start=min(start,stp);

            end=max(end,stp);

            st[stp]=1;

        }

        int v=i+n;

        for(int i=start;i<=end;i++){

            if(st[i]){

                e[i].push_back({v,0});

                in[v]++;

            }

            else {

                e[v].push_back({i,1});

                in[i]++;

            }

        }

    }

    toposort();

    for(int i=1;i<=n;i++)dis[i]=1;

    for(int i=0;i<n+m;i++){

        int u=q[i];

        for(auto ww:e[u]){

            int v=ww.first,w=ww.second;

            dis[v]=max(dis[v],dis[u]+w);

        }

    }

    int res=0;

    for(int i=1;i<=n;i++)res=max(res,dis[i]);

    cout<<res;

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/35146.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

市长海报/ Mayor‘s posters

AB 省 Bytetown 的市民无法忍受市长竞选活动的候选人随心所欲地将他们的选举海报贴在各个地方。市议会最终决定建造一面选举墙来放置海报&#xff0c;并引入以下规则&#xff1a; 每个候选人都可以在墙上放置一张海报。所有海报的高度都与墙壁的高度相同;海报的宽度可以是任意整…

LeetCode hot 100—验证二叉搜索树

题目 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 示例 1&#…

ccfcsp3402矩阵重塑(其二)

//矩阵重塑&#xff08;其二&#xff09; #include<iostream> using namespace std; int main(){int n,m,t;cin>>n>>m>>t;int c[10000][10000];int s0,sum0;int d[10000],k[100000];for(int i0;i<n;i){for(int j0;j<m;j){cin>>c[i][j];d[s…

MCP和Function Calling的区别

文章目录 1、什么是MCP1.1、定义和特点1.2、架构和工作原理3.3、MCP 的主要优势 2、什么是Function Calling3、MCP和Function Calling的区别4、总结 &#x1f343;作者介绍&#xff1a;双非本科大四网络工程专业在读&#xff0c;阿里云专家博主&#xff0c;前三年专注于Java领域…

裂缝识别系统 Matlab GUI设计

使用说明 裂缝识别系统 Matlab GUI设计 &#xff0c;运行环境Matlab2023b及以上&#xff1b; 一种基于MATLAB图形用户界面&#xff08;GUI&#xff09;的裂缝自动识别系统&#xff0c;该系统利用数字图像处理技术实现裂缝图像的预处理&#xff0c;集成均衡化、噪声滤波、对比…

【源码分析】Nacos实例注册流程分析-事件驱动框架

【踩坑记录】 本人下载的Nacos 服务端版本是2.3.2&#xff0c;在开始进行源码编译便遇到问题&#xff0c;下面是各个问题记录 源码大量爆红 在最开始用Idea加载Maven项目的时候&#xff0c;发现项目中大量的代码爆红&#xff0c;提示其类或者包不存在&#xff0c;后来结果查…

51单片机指令系统入门

目录 基本概念讲解 一、机器指令​ 二、汇编指令​ &#xff08;一&#xff09;汇编指令的一般格式 &#xff08;二&#xff09;按字节数分类的指令 三、高级指令 总结​ 基本概念讲解 指令是计算机&#xff08;或单片机&#xff09;中 CPU 能够识别并执行的基本操作命令…

mysql5.x和mysql8.x查看和设置隔离级别

MySQL的隔离级别 级别标志值描述读未提交READ-UNCOMMITTED0存在脏读、不可重复读、幻读的问题读已提交READ-COMMITTED1解决脏读的问题&#xff0c;存在不可重复读、幻读的问题可重复读REPEATABLE-READ2mysql 默认级别&#xff0c;解决脏读、不可重复读的问题&#xff0c;存在幻…

【函数式编程】【C#/F#】第四讲:单子与函子 - 抽象的编程模式

在第二讲中我们探讨了一个诚实的函数应该要做到什么事&#xff0c;并运用了一种方法&#xff0c;让我们可以去准确的描述数据。 不过有一种情况让我们始料未及&#xff0c;例如网站需要收集一些信息&#xff0c;但有些信息不是必须的&#xff0c;是可有可无的。如果我们要去准…

【vue2 + Cesium】使用Cesium、添加第三方地图、去掉商标、Cesium基础配置、地图放大缩小事件、获取可视区域、层级、高度

参考文章&#xff1a; vue2 使用 cesium 篇【第一篇】 vue2 使用 cesium 【第二篇-相机视角移动添加模型】 vue2 项目模版&#xff1a; vue2-common 安装 cesium npm install cesium --save这个就很简单&#xff0c;只需要一句简简单单的命令就可以实现在 vue 项目中安装 ce…

vllm-openai多服务器集群部署AI模型

服务器配置是两台ubantu系统电脑,每台电脑安装两张4090-48G显存的显卡,共计192G显存。 服务器1 服务器2 准备工作: 1.两台电脑都已经安装了docker 2.两台电脑都已经安装了nvidia驱动 参考vllm官方资料 https://docs.vllm.ai/en/latest/serving/distributed_serving.html…

【电源】斩波电路

文章目录 前言定义概念 缩写降压斩波电路使用步骤总结参考文献 前言 进行大创项目开发的学习 bilibili 定义概念 缩写 斩波电路&#xff1a;分为降压&#xff0c;电荷泵&#xff0c;升压&#xff0c;升降压&#xff0c;Cuk&#xff0c;Speic&#xff0c;Zeta 等等 降压斩…

Hadoop集群组成

&#xff08;一&#xff09;Hadoop的组成 对普通用户来说&#xff0c; Hadoop就是一个东西&#xff0c;一个整体&#xff0c;它能给我们提供无限的磁盘用来保存文件&#xff0c;可以使用提供强大的计算能力。 在Hadoop3.X中&#xff0c;hadoop一共有三个组成部…

c++基础知识-图论进阶

一、拓扑排序 1、基础知识 1&#xff09;什么是拓扑排序 对一个有向无环图G进行拓扑排序&#xff0c;是将G中所有顶点排成一个线性序列&#xff0c;使得图中任意一对顶点u和v&#xff0c;若&#xff0c;则u在线性序列中出现在v之前。 2&#xff09;拓扑排序的操作方法 重复执行…

从Scaling Laws中解析大模型训练的边际递减临界点

前言 当我们拆解GPT-4到DeepSeek的演进路径&#xff0c;会发现一个反直觉的真相&#xff1a;​AI的智能跃迁不依赖参数堆砌&#xff0c;而取决于对"结构-能量-信息"三元关系的精准把控。就像人类大脑在进化中通过皮层折叠而非单纯增大体积来实现智能突破&#xff0c…

Word 小黑第20套

对应大猫21 特定一页设为横向 上下用分页符

【从0到1搞懂大模型】RNN基础(4)

先说几个常用的可以下载数据集的地方 平台&#xff1a;kaggle&#xff08;https://www.kaggle.com/datasets&#xff09; 和鲸社区&#xff08;https://www.heywhale.com/home&#xff09; 阿里天池&#xff08;https://tianchi.aliyun.com/&#xff09; 其他&#xff1a;海量公…

openEuler24.03 LTS下安装MySQL8

前提条件 拥有openEuler24.03 LTS环境&#xff0c;可参考&#xff1a;Vmware下安装openEuler24.03 LTS 步骤 卸载原有mysql及mariadb sudo systemctl stop mysql mysqld 2>/dev/null sudo rpm -qa | grep -i mysql\|mariadb | xargs -n1 sudo rpm -e --nodeps 2>/dev/…

如何在Odoo 18中实现OWL通知服务

如何在Odoo 18中实现OWL通知服务 OWL&#xff08;Odoo Web Library&#xff09;是Odoo的前端框架&#xff0c;用于构建现代化的动态响应式用户界面。在早期版本中&#xff0c;Odoo 前端设计与开发使用的是诸如 QWeb 这类较为老旧的框架&#xff0c;而随着 Odoo 每发布一个新版本…

Unet nn-Unet

Unet && nn-Unet&#xff1a; 文章题目&#xff1a;U-Net: Convolutional Networks for Biomedical Image Segmentation 代码&#xff1a;https://lmb.informatik.uni-freiburg.de/people/ronneber/u-net/ 文章题目&#xff1a;nnU-Net: Self-adapting Framework for U…