C++ 有向图拓扑排序算法

2024-08-20 21:36
文章标签 算法 c++ 有向图 排序 拓扑

本文主要是介绍C++ 有向图拓扑排序算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码 
#include <algorithm>
#include <cassert>
#include <functional>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <unordered_set>
#include <vector>namespace jc {template <typename K, typename V>struct DAGNode {K k;V v;std::set<DAGNode<K, V>*> in;std::set<DAGNode<K, V>*> out;};template <typename K, typename V>class DAGGraph {public:bool AddEdge(const K& from, const K& to);V& operator[](const K& key);bool Exist(const K& key) const;void Clear();std::size_t Size() const;void Walk(std::function<void(const K& k, const V& v)> f,bool start_from_head = true);void WalkHeads(std::function<void(const K& k, const V& v)> f);void WalkTails(std::function<void(const K& k, const V& v)> f);std::unordered_set<K> NextKeys();std::unordered_set<K> NextKeys(const K& key);private:bool IsCyclic(const DAGNode<K, V>& from, const DAGNode<K, V>& to) const;void RefreshWalkSequences();std::vector<std::set<K>> ConnectedComponents() const;void DFS(const K& k, std::unordered_set<K>* visited,std::set<K>* connected_components) const;std::vector<K> TopologicalSequence(const std::set<K>& connected_components,bool start_from_head) const;private:std::map<K, DAGNode<K, V>> bucket_;std::unordered_set<K> heads_;std::unordered_set<K> tails_;std::vector<std::vector<K>> sequences_start_from_head_;std::vector<std::vector<K>> sequences_start_from_tail_;private:bool allow_modify_ = true;std::vector<std::vector<K>> sequences_start_from_head_for_next_;std::unordered_set<K> current_heads_for_next_;};template <typename K, typename V>inline bool DAGGraph<K, V>::AddEdge(const K& from, const K& to) {assert(allow_modify_);if (from == to || !bucket_.count(from) || !bucket_.count(to) ||IsCyclic(bucket_.at(from), bucket_.at(to))) {return false;}bucket_.at(from).out.emplace(&bucket_.at(to));bucket_.at(to).in.emplace(&bucket_.at(from));heads_.erase(to);tails_.erase(from);sequences_start_from_head_.clear();sequences_start_from_tail_.clear();return true;}template <typename K, typename V>inline V& DAGGraph<K, V>::operator[](const K& key) {if (!bucket_.count(key)) {assert(allow_modify_);bucket_[key].k = key;heads_.emplace(key);tails_.emplace(key);sequences_start_from_head_.clear();sequences_start_from_tail_.clear();}return bucket_.at(key).v;}template <typename K, typename V>inline bool DAGGraph<K, V>::Exist(const K& key) const {return bucket_.count(key);}template <typename K, typename V>inline void DAGGraph<K, V>::Clear() {allow_modify_ = true;bucket_.clear();heads_.clear();tails_.clear();sequences_start_from_head_.clear();sequences_start_from_tail_.clear();}template <typename K, typename V>inline std::size_t DAGGraph<K, V>::Size() const {return bucket_.size();}template <typename K, typename V>inline void DAGGraph<K, V>::Walk(std::function<void(const K& k, const V& v)> f,bool start_from_head) {if (sequences_start_from_head_.empty()) {RefreshWalkSequences();}const std::vector<std::vector<K>>& seqs_to_walk =start_from_head ? sequences_start_from_head_ : sequences_start_from_tail_;for (const std::vector<K>& seq : seqs_to_walk) {std::for_each(std::begin(seq), std::end(seq), [&](const K& key) {const DAGNode<K, V>& node = bucket_.at(key);f(node.k, node.v);});}}template <typename K, typename V>inline void DAGGraph<K, V>::WalkHeads(std::function<void(const K& k, const V& v)> f) {if (sequences_start_from_head_.empty()) {RefreshWalkSequences();}for (const std::vector<K>& seq : sequences_start_from_head_) {std::for_each(std::begin(seq), std::end(seq), [&](const K& key) {if (heads_.count(key)) {const DAGNode<K, V>& node = bucket_.at(key);f(node.k, node.v);}});}}template <typename K, typename V>inline void DAGGraph<K, V>::WalkTails(std::function<void(const K& k, const V& v)> f) {if (sequences_start_from_head_.empty()) {RefreshWalkSequences();}for (const std::vector<K>& seq : sequences_start_from_tail_) {std::for_each(std::begin(seq), std::end(seq), [&](const K& key) {if (tails_.count(key)) {const DAGNode<K, V>& node = bucket_.at(key);f(node.k, node.v);}});}}template <typename K, typename V>inline std::unordered_set<K> DAGGraph<K, V>::NextKeys() {assert(allow_modify_);  // allowed call once unless Clear()allow_modify_ = false;current_heads_for_next_ = heads_;if (sequences_start_from_head_.empty()) {RefreshWalkSequences();}return heads_;}template <typename K, typename V>inline std::unordered_set<K> DAGGraph<K, V>::NextKeys(const K& key) {assert(!allow_modify_);  // must call NextKeys() beforeassert(current_heads_for_next_.count(key));current_heads_for_next_.erase(key);std::unordered_set<K> res;for (std::vector<K>& seq : sequences_start_from_head_for_next_) {auto it = std::find(begin(seq), std::end(seq), key);if (it == std::end(seq)) {continue;}seq.erase(it);const std::set<DAGNode<K, V>*>& nodes = bucket_.at(key).out;for (DAGNode<K, V>* v : nodes) {const std::set<DAGNode<K, V>*>& prev_nodes = v->in;bool no_prev_node_in_seq =std::all_of(std::begin(prev_nodes), std::end(prev_nodes),[&](DAGNode<K, V>* in_node) {return std::find(std::begin(seq), std::end(seq),in_node->k) == std::end(seq);});if (no_prev_node_in_seq) {current_heads_for_next_.emplace(v->k);res.emplace(v->k);}}break;}return res;}template <typename K, typename V>inline bool DAGGraph<K, V>::IsCyclic(const DAGNode<K, V>& from,const DAGNode<K, V>& to) const {std::queue<DAGNode<K, V>*> q;for (DAGNode<K, V>* v : from.in) {q.emplace(v);}std::unordered_set<DAGNode<K, V>*> visited;while (!q.empty()) {DAGNode<K, V>* node = q.front();q.pop();if (visited.count(node)) {continue;}if (node == &to) {return true;}visited.emplace(node);for (DAGNode<K, V>* v : node->in) {q.emplace(v);}}return false;}template <typename K, typename V>inline void DAGGraph<K, V>::RefreshWalkSequences() {sequences_start_from_head_.clear();sequences_start_from_tail_.clear();const std::vector<std::set<K>> connected_components = ConnectedComponents();for (const std::set<K>& x : connected_components) {const std::vector<K> seq_from_head = TopologicalSequence(x, true);const std::vector<K> seq_from_tail = TopologicalSequence(x, false);assert(!seq_from_head.empty());assert(!seq_from_tail.empty());sequences_start_from_head_.emplace_back(seq_from_head);sequences_start_from_tail_.emplace_back(seq_from_tail);}sequences_start_from_head_for_next_ = sequences_start_from_head_;}template <typename K, typename V>inline std::vector<std::set<K>> DAGGraph<K, V>::ConnectedComponents() const {std::vector<std::set<K>> res;std::unordered_set<K> visited;for (auto& x : bucket_) {std::set<K> tmp;DFS(x.second.k, &visited, &tmp);if (!tmp.empty()) {res.emplace_back(tmp);}}std::sort(std::begin(res), std::end(res),[&](const std::set<K>& lhs, const std::set<K>& rhs) {return lhs.size() < rhs.size();});return res;}template <typename K, typename V>inline void DAGGraph<K, V>::DFS(const K& k, std::unordered_set<K>* visited,std::set<K>* connected_components) const {if (visited->count(k)) {return;}visited->emplace(k);connected_components->emplace(k);if (!bucket_.at(k).in.empty()) {for (DAGNode<K, V>* v : bucket_.at(k).in) {DFS(v->k, visited, connected_components);}}if (!bucket_.at(k).out.empty()) {for (DAGNode<K, V>* v : bucket_.at(k).out) {DFS(v->k, visited, connected_components);}}}template <typename K, typename V>inline std::vector<K> DAGGraph<K, V>::TopologicalSequence(const std::set<K>& connected_components, bool start_from_head) const {std::map<K, std::vector<K>> adjacency_list;std::map<K, int32_t> in_degree;for (const K& key : connected_components) {if (!in_degree.count(key)) {in_degree.emplace(key, 0);}const std::set<DAGNode<K, V>*>& nodes =start_from_head ? bucket_.at(key).out : bucket_.at(key).in;for (DAGNode<K, V>* v : nodes) {adjacency_list[key].emplace_back(v->k);++in_degree[v->k];}}std::queue<K> q;for (auto& x : in_degree) {if (x.second == 0) {q.emplace(x.first);}}std::vector<K> res;while (!q.empty()) {const K key = q.front();q.pop();res.emplace_back(key);for (const K& k : adjacency_list[key]) {if (--in_degree.at(k) == 0) {q.emplace(k);}}}assert(res.size() == connected_components.size());  // graph is DAGreturn res;}}  // namespace jcnamespace jc::test {class MockPipelineEngine {public:void Start() {}void Stop() {}void Destroy() {}};void test() {DAGGraph<int, std::unique_ptr<MockPipelineEngine>> d;// Make Direct Acyclic Graph://    0    6      11  13//   / \   |      |//  1   3  7  8   12//  | x |      \ ///  2   4       9//   \ /        |//    5         10// Traverse each child graph in order whose size smaller// Start Order:// 13// 6 -> 7// 8 -> 11 -> 12 -> 9 -> 10// 0 -> 1 -> 3 -> 2 -> 4 -> 5// Stop Order:// 13// 7 -> 6// 10 -> 9 -> 8 -> 12 -> 11// 5 -> 2 -> 4 -> 1 -> 3 -> 0constexpr int nodes_count = 14;for (int i = 0; i < nodes_count; ++i) {d[i].reset(new MockPipelineEngine);}assert(d.AddEdge(0, 1));assert(d.AddEdge(0, 3));assert(d.AddEdge(1, 2));assert(d.AddEdge(3, 4));assert(d.AddEdge(1, 4));assert(d.AddEdge(3, 2));assert(d.AddEdge(2, 5));assert(d.AddEdge(4, 5));assert(d.AddEdge(6, 7));assert(d.AddEdge(8, 9));assert(d.AddEdge(9, 10));assert(d.AddEdge(11, 12));assert(d.AddEdge(12, 9));assert(d.Size() == nodes_count);for (int i = 0; i < nodes_count; ++i) {assert(d.Exist(i));}assert(!d.AddEdge(1, 0));assert(!d.AddEdge(2, 0));assert(!d.AddEdge(4, 0));assert(!d.AddEdge(7, 6));assert(!d.AddEdge(10, 11));assert(!d.AddEdge(13, 13));assert(!d.AddEdge(13, 14));constexpr bool start_from_head = true;{std::vector<int> v;std::vector<int> start_order{ 13, 6, 7, 8, 11, 12, 9, 10, 0, 1, 3, 2, 4, 5 };std::vector<int> start_order2{ 13, 6, 7, 8, 11, 12, 9, 10, 0, 3, 1, 4, 2, 5 };d.Walk([&](int key, const std::unique_ptr<MockPipelineEngine>& pipeline) {pipeline->Start();v.emplace_back(key);},start_from_head);assert(v == start_order || v == start_order2);}{std::vector<int> v;std::vector<int> stop_order{ 13, 7, 6, 10, 9, 8, 12, 11, 5, 2, 4, 1, 3, 0 };std::vector<int> stop_order2{ 13, 7, 6, 10, 9, 12, 8, 11, 5, 2, 4, 1, 3, 0 };d.Walk([&](int key, const std::unique_ptr<MockPipelineEngine>& pipeline) {pipeline->Stop();v.emplace_back(key);},!start_from_head);assert(v == stop_order || v == stop_order2);}{std::vector<int> v;std::vector<int> heads_order{ 13, 6, 8, 11, 0 };d.WalkHeads([&](int key, const std::unique_ptr<MockPipelineEngine>& pipeline) {pipeline->Destroy();v.emplace_back(key);});assert(v == heads_order);}{std::vector<int> v;std::vector<int> tails_order{ 13, 7, 10, 5 };d.WalkTails([&](int key, const std::unique_ptr<MockPipelineEngine>& pipeline) {pipeline->Destroy();v.emplace_back(key);});assert(v == tails_order);}{std::vector<int> test_sequence{ 13, 6, 7, 0,  1,  3, 4,2,  5, 8, 11, 12, 9, 10 };std::unordered_set<int> heads{ 0, 6, 8, 11, 13 };assert(d.NextKeys() == heads);std::vector<std::unordered_set<int>> next_keys{{}, {7}, {}, {1, 3}, {}, {2, 4}, {}, {5}, {}, {}, {12}, {9}, {10}, {},};assert(test_sequence.size() == nodes_count);assert(next_keys.size() == nodes_count);for (int i = 0; i < nodes_count; ++i) {assert(d.NextKeys(test_sequence[i]) == next_keys[i]);}}d.Clear();assert(d.Size() == 0);for (int i = 0; i < nodes_count; ++i) {assert(!d.Exist(i));}}}  // namespace jc::test//int main() { jc::test::test(); }
效果

 

这篇关于C++ 有向图拓扑排序算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1091239。

相关文章

Windows下C++使用SQLitede的操作过程

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能（如数据库连接、事务管理）、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite：C++轻松操作SQ
阅读更多...
C++中RAII资源获取即初始化

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...
C++ 函数 strftime 和时间格式示例详解

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五
阅读更多...
C++作用域和标识符查找规则详解

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域（Scope）和标识符查找（IdentifierLookup）是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找（Ordinary Lookup）2. 限定查找（Qualif
阅读更多...
C/C++ chrono简单使用场景示例详解

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》：本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示
阅读更多...
C++/类与对象/默认成员函数@构造函数的用法

C++/类与对象/默认成员函数@构造函数的用法

《C++/类与对象/默认成员函数@构造函数的用法》：本文主要介绍C++/类与对象/默认成员函数@构造函数的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录名词概念默认成员函数构造函数概念函数特征显示构造函数隐式构造函数总结名词概念默认构造函数：不用传参就可以
阅读更多...
C++类和对象之默认成员函数的使用解读

C++类和对象之默认成员函数的使用解读

《C++类和对象之默认成员函数的使用解读》：本文主要介绍C++类和对象之默认成员函数的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、默认成员函数有哪些二、各默认成员函数详解默认构造函数析构函数拷贝构造函数拷贝赋值运算符三、默认成员函数的注意事项总结一
阅读更多...
C/C++中OpenCV 矩阵运算的实现

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算（标量与矩阵）、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2