拓扑排序--C++实现

1. 定义

前置知识

  1. DAG: Directed Acyclic Graph 有向无环图
  2. 拓扑序: 像先修课程一样,即任意课程的前置课程都在其前面。

举个例子
图一
在这个图中,1234或者1324是拓扑序。而其他的序列不是,即在一个节点出现之前他的所有祖先节点需要出现。

2. 实现

2.1 DFS

任意选节点,先递归各个子节点,在将根节点放入栈中。最后将栈中元素弹出,即可得到一个拓扑序列。相当于二叉树的后序遍历。

由于存在可能有环的情况,所有节点的状态需要三个状态位来表示以防止和遍历过的冲突。


struct Graph {Graph(int vertex_num = 100):maxVertexSz(vertex_num + 1),graph(vertex_num + 1,std::vector<int>( vertex_num + 1, 0)){}enum Status{to_visit,visiting,visited};void add_edge(int u, int v){graph[u][v] = 1;}bool find_edge(int u, int v) const{return graph[u][v];}std::unordered_set<int> getVertexSet() const{std::unordered_set<int> vertexSet;for (int i = 0; i < maxVertexSz; ++i)for (int j = 0; j < maxVertexSz; ++j)if (graph[i][j])vertexSet.insert(i), vertexSet.insert(j);return vertexSet;}void cal_inDeg(std::vector<int> &inDeg){for (int i = 0; i < maxVertexSz; ++i)for (int j = 0; j < maxVertexSz; ++j)if (graph[i][j])inDeg[j]++;}std::vector<std::vector<int>> graph;int maxVertexSz;
};bool topo_sort_dfs(const Graph &p, std::vector<Graph::Status> &stat,std::stack<int> &st,int node) {if (stat[node] == Graph::visited)return true;if (stat[node] == Graph::visiting)return false;stat[node] = Graph::visiting;bool not_cyclic = true;for (int i = 0; i < p.maxVertexSz; ++i) {if (!not_cyclic)return false;if (p.graph[node][i] != 0) {not_cyclic = topo_sort_dfs(p, stat, st, i);}}st.push(node);stat[node] = Graph::visited;
}std::vector<int> topo_dfs(const Graph &p)
{std::vector<int> topo_seq;std::unordered_set<int> vertexSet(std::move(p.getVertexSet()));std::vector<Graph::Status> stat(p.maxVertexSz, Graph::to_visit);std::stack<int> st;bool not_cyclic = true;for (auto node:vertexSet) {if (not_cyclic && stat[node] == Graph::to_visit)not_cyclic = topo_sort_dfs(p, stat, st, node);}if ( not_cyclic ) {while (!st.empty()) {topo_seq.push_back(st.top());st.pop();}}return topo_seq;
}
2.2 Kahn’s

先计算出所有节点的入度,再将入度为0的节点放入队列中。每次从队列中取出一个节点放入拓扑序列,并根据以该节点为入点的边,降低从该节点到达节点的入度。若降低后节点入度为0,则放入队列中。

其实相当于BFS。
注意对比拓扑序列的序列长度,若长度比节点数目少,则说明图中有环。

std::vector<int> topo_sort_kahn(const Graph &p)
{std::vector<int> topo_seq;int sz = p.maxVertexSz;std::vector<int> inDeg(sz, 0);std::unordered_set<int> vertexSet(std::move(p.getVertexSet()));std::queue<int> q;for ( int i = 0; i < sz; ++i) {for ( int j = 0; j < sz; ++j) {if (p.graph[i][j])inDeg[j]++;}}for (int node:vertexSet) {if (vertexSet.count(node) && !inDeg[node])q.push(node);}while (!q.empty()) {int cur = q.front();topo_seq.push_back(cur);q.pop();for (int i = 0; i < sz; ++i ) {if ( p.graph[cur][i] ) {inDeg[i]--;if (!inDeg[i])q.push(i);}}}return topo_seq;
}

3. 应用

求图中是否有环,AOE中的关键路径等。

4. 参考

OIWIKI
GeekForGeeks

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

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

相关文章

OSPF复习(2)

目录 一、LSA的头部 二、6种类型的LSA&#xff08;课堂演示&#xff09; 1、type1-LSA&#xff1a;----重要且复杂 2、type2-LSA&#xff1a; 3、type3-LSA&#xff1a; 4、type4-LSA&#xff1a; 5、type5-LSA&#xff1a; 6、type7-LSA&#xff1a; 三、OSPF的网络类…

CSS3媒体查询与页面自适应

2017年9月&#xff0c;W3C发布媒体查询(Media Query Level 4)候选推荐标准规范&#xff0c;它扩展了已经发布的媒体查询的功能。该规范用于CSS的media规则&#xff0c;可以为文档设定特定条件的样式&#xff0c;也可以用于HTML、JavaScript等语言。 1、媒体查询基础 媒体查询…

windows docker desktop 更换镜像 加速

最近 docker hub 访问不了; 经过研究 可以通过添加 代理镜像网址 添加代理服务器的方式 实现完美访问 1添加镜像网站 修改成国内镜像地址就能享受到飞一般的速度&#xff0c;但有一个问题&#xff0c;部分站点镜像不全或者镜像比较老&#xff0c;建议使用多个镜像站。 https…

供应商等级:一级、二级和三级供应商之间有什么区别

作为一名专业采购人员&#xff0c;你知道拥有一个可靠且具有成本效益的供应链有多么重要。确保供应链顺利运行的方法之一就是利用供应商分级。 什么是供应商分级&#xff1f; 供应商分级是根据供应商的绩效和对企业的重要性&#xff0c;对其进行分类的做法。 因此&#xff0c…

计算机毕业设计选题推荐-超市售货微信小程序/安卓APP-项目实战

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…

有方N58 HTTP POST 请求连接 TDengine

串口调试软件&#xff1a;格西调试精灵 第一步先注册网络获取IP地址 建立PPP连接 ATXIIC1\r PPP链路建立成功&#xff0c;查询IP地址 ATXIIC?\r 设置网络APN ATCREG?\r 运行结果&#xff0c;红线处是获…

深度学习数据集大合集—疾病、植物、汽车等

最近又收集了一大批深度学习数据集&#xff0c;今天分享给大家&#xff01;废话不多说&#xff0c;直接上数据&#xff01; 1、招聘欺诈数据集 招聘欺诈数据集&#xff1a;共收集了 200,000 条数据&#xff0c;来自三个网站。 该数据集共收集了 200.000 条数据&#xff0c;分别…

智慧渔业养殖远程监控解决方案

智慧渔业养殖远程监控解决方案 项目背景 影响水产养殖环境的关键参数就是水温、光照、溶氧&#xff0c;氨氮&#xff0c;硫化物、亚硝酸盐等&#xff0c;但这些关键因素即看不见又摸不着很难准确把握。现有的水产管理是以养殖经验为指导&#xff0c;也就是一种普遍的养殖经验…

MySQL 分组后统计 TopN 思路优化

一、表信息 表结构如下&#xff1a; CREATE TABLE score (id int(11) NOT NULL AUTO_INCREMENT,name varchar(255) DEFAULT NULL,score int(11) DEFAULT NULL,PRIMARY KEY (id) ) ENGINEInnoDB AUTO_INCREMENT1746687 DEFAULT CHARSETutf8;使用存储过程生成十万条测试数据&am…

【深度学习】pytorch——Tensor(张量)详解

笔记为自我总结整理的学习笔记&#xff0c;若有错误欢迎指出哟~ pytorch——Tensor 简介创建Tensortorch.Tensor( )和torch.tensor( )的区别torch.Tensor( )torch.tensor( ) tensor可以是一个数&#xff08;标量&#xff09;、一维数组&#xff08;向量&#xff09;、二维数组&…

2023-macOS下安装anaconda,终端自动会出现(base)字样,如何取消

2023-macOS下安装anaconda&#xff0c;终端自动会出现(base)字样&#xff0c;如何取消 安装后&#xff0c;我们再打开终端&#xff0c;就会自动出现了&#xff08;base&#xff09; 就会出现这样子的&#xff0c;让人头大&#xff0c; 所以我们要解决它 具体原因是 安装了anac…

DDoS类型攻击对企业造成的危害

超级科技实验室的一项研究发现&#xff0c;每十家企业中&#xff0c;有四家(39%)企业没有做好准备应对DDoS攻击&#xff0c;保护自身安全。且不了解应对这类攻击最有效的保护手段是什么。 由于缺乏相关安全知识和保护&#xff0c;使得企业面临巨大的风险。 当黑客发动DDoS攻击…

Spring Boot:构建下一代Java应用的利器

文章目录 什么是Spring Boot&#xff1f;Spring Boot的主要特性1. 自动配置2. 独立性3. 微服务支持4. 生态系统5. Spring生态系统集成 Spring Boot的优势1. 提高开发效率2. 减少样板代码3. 更好的部署和管理4. 多种部署选项5. 微服务支持 如何开始使用Spring Boot1. 安装Spring…

飞致云及其旗下1Panel项目进入2023年第三季度最具成长性开源初创榜单

2023年10月26日&#xff0c;知名风险投资机构Runa Capital发布2023年第三季度ROSS指数&#xff08;Runa Open Source Startup Index&#xff09;。ROSS指数按季度汇总并公布在代码托管平台GitHub上年化增长率&#xff08;AGR&#xff09;排名前二十位的开源初创公司和开源项目。…

Spring Boot Actuator 漏洞利用

文章目录 前言敏感信息泄露env 泄露配置信息trace 泄露用户请求信息mappings 泄露路由信息heapdump泄露堆栈信息 前言 spring对应两个版本&#xff0c;分别是Spring Boot 2.x和Spring Boot 1.x&#xff0c;因此后面漏洞利用的payload也会有所不同 敏感信息泄露 env 泄露配置信…

开发小程序需要多少钱?

随着移动互联网的快速发展&#xff0c;小程序已经成为了企业、个人创业者获取用户、提升品牌影响力的重要工具。然而&#xff0c;对于许多初次接触小程序的人来说&#xff0c;开发小程序需要多少钱&#xff0c;是他们最关心的问题。 首先我们需要明确的是&#xff0c;开发小程…

图论08-图的建模-状态的表达与理解 - 倒水问题为例

文章目录 状态的表达例题1题解1 终止条件&#xff1a;有一个数位为42 状态的改变&#xff1a;a表示十位数&#xff0c;b表示个位数3 其他设置 例题2 力扣773 滑动谜题JavaC 状态的表达 例题1 从初始的(x&#xff0c;y)状态&#xff0c;到最后变成&#xff08;4&#xff0c;&am…

SOLIDWORKS 2024新功能--SOLIDWORKS Electrical篇

SOLIDWORKS Electrical 对齐零部件 在设计 3D 机柜布局时使用对齐零部件时&#xff0c;可以在图形区域中预览更改。这大大减少了在 3D 机柜布局中对齐 SOLIDWORKS 零部件所需的工作量。对齐零部件 PropertyManager 简化并改进了工作流程。 SOLIDWORKS Electrical 更改多个导…

跨境电商须知| 独立站的特点与痛点有哪些?

独立站的特点与痛点有哪些&#xff1f; 无论是做独立站&#xff0c;还是做亚马逊&#xff0c;都有各自的难点。自己做独立站若要在跨境行业长足发展&#xff0c;既要知道独立站有什么特点&#xff0c;要清楚独立站的痛点并一一克服。了解独立站搭建更多 一、独立站的特点 1、…