讲师中心 微信公众号

工具推荐

视频效率加速
AniShort
AniShort

AI短剧协同制作平台

剧云
剧云

中文短剧剧本制作平台

SoundView
SoundView

字幕擦除翻译、配音口型同步

立刻MV
立刻MV

低成本歌曲 MV、视频生成

C++怎么实现拓扑排序算法_C++图论与有向无环图(DAG)应用

胖敏大大_1563

胖敏大大_1563

发布时间:2025-11-30 11:54:06

|

969人浏览过

|

来源于php中文网

原创

拓扑排序适用于有向无环图,通过Kahn算法或DFS实现,用于确定节点线性序列以满足依赖关系,如课程安排或任务调度。

c++怎么实现拓扑排序算法_c++图论与有向无环图(dag)应用

拓扑排序是图论中针对有向无环图(DAG)的一种线性排序算法,它能将图中的所有顶点排成一个序列,使得对于每一条有向边 (u, v),u 在序列中都出现在 v 的前面。C++ 中实现拓扑排序主要有两种方法:基于深度优先搜索(DFS)和基于入度的 Kahn 算法。

1. 什么是拓扑排序?

拓扑排序只适用于有向无环图(DAG)。如果图中存在环,则无法进行拓扑排序,因为会出现逻辑矛盾(比如 A 必须在 B 前,B 又必须在 A 前)。

典型应用场景包括:

  • 课程学习顺序安排
  • 工程任务调度
  • 编译依赖处理

2. 使用 Kahn 算法(基于入度)

Kahn 算法是一种广度优先的思想,通过不断移除入度为 0 的节点来构建拓扑序列。

立即学习“C++免费学习笔记(深入)”;

步骤如下:

Livestream Script Generator
Livestream Script Generator

直播带货脚本:话术、节奏、互动、促单。适用于主播、电商运营、MCN机构。

下载
  • 计算每个节点的入度
  • 将所有入度为 0 的节点加入队列
  • 从队列中取出节点,加入结果序列,并将其邻居的入度减 1
  • 若某邻居入度变为 0,则加入队列
  • 重复直到队列为空
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> topologicalSort(int n, vector<vector<int>>& adj) {
    vector<int> indegree(n, 0);
    
    // 计算每个节点的入度
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            indegree[v]++;
        }
    }

    queue<int> q;
    // 将入度为 0 的节点入队
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topo;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);

        // 遍历 u 的邻居,减少其入度
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 若结果长度不等于节点数,说明存在环
    if (topo.size() != n) {
        return {}; // 返回空表示无法拓扑排序
    }

    return topo;
}

3. 使用 DFS 实现拓扑排序

DFS 方法通过后序遍历的方式记录节点,然后逆序输出即为拓扑序列。

需要维护三个状态:

  • 未访问(0)
  • 正在访问(1,用于检测环)
  • 已完成(2)
vector<int> topo;
vector<int> visited;

bool dfs(int u, vector<vector<int>>& adj) {
    if (visited[u] == 1) return false; // 存在环
    if (visited[u] == 2) return true;  // 已完成

    visited[u] = 1;
    for (int v : adj[u]) {
        if (!dfs(v, adj)) return false;
    }
    visited[u] = 2;
    topo.push_back(u); // 后序添加
    return true;
}

vector<int> topologicalSortDFS(int n, vector<vector<int>>& adj) {
    visited.assign(n, 0);
    topo.clear();

    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            if (!dfs(i, adj)) {
                return {}; // 存在环
            }
        }
    }

    reverse(topo.begin(), topo.end());
    return topo;
}

4. 完整示例与测试

以下是一个完整可运行的例子:

int main() {
    int n = 6;
    vector<vector<int>> adj(n);

    // 构建图:0→1, 0→2, 1→3, 2→3, 3→4, 4→5
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[4].push_back(5);

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

    if (result.empty()) {
        cout << "图中存在环,无法进行拓扑排序。\n";
    } else {
        cout << "拓扑排序结果:";
        for (int x : result) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}

输出结果应为:0 1 2 3 4 5,符合依赖关系。

基本上就这些。Kahn 算法更直观,适合初学者;DFS 方法更贴近递归思维,也便于检测环。根据实际需求选择即可。注意建图方式(邻接表)和边界处理,拓扑排序就能稳定运行。

热门AI工具

更多
笔灵降AI

一款AI论文写作工具,主要用于论文降AI神器,适配知网及维普!一键降至安全线,100%保留原文格式;无口语化问题,文风更学术,降后字数控制最佳!,适合需要提升相关任务效率的用户。

蛙蛙写作

一款AI论文写作工具,主要用于超级AI智能写作助手,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

讯飞绘文

讯飞绘文是一款由科大讯飞推出的一站式 AIGC 内容运营平台。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

Loomy
Loomy Hot

一款AI工具,主要用于科大讯飞发布的桌面级 AI 助理,比 OpenClaw 更易用、更安全!,适合需要提升相关任务效率的用户。

超级简历WonderCV

一款AI办公效率工具,主要用于免费求职简历模版下载制作,应届生职场人必备简历制作神器,适合需要提升相关任务效率的用户。

UP简历
UP简历 Hot

一款AI办公效率工具,主要用于基于AI技术的免费在线简历制作工具,适合需要提升相关任务效率的用户。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

相关专题

更多
页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

7336

2023.08.14

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

0

2026.11.17

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

20

2026.11.17

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

0

2026.11.17

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

0

2026.11.17

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

0

2026.11.17

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

0

2026.11.17

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

180

2026.11.12

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

120

2026.11.12

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C++ Core Guidelines
C++ Core Guidelines

共0课时 | 0人学习

C++ Reference
C++ Reference

共0课时 | 0人学习

C++ 官方标准说明
C++ 官方标准说明

共0课时 | 0人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn