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。

相关文章

C++右移运算符的一个小坑及解决

C++右移运算符的一个小坑及解决

《C++右移运算符的一个小坑及解决》文章指出右移运算符处理负数时左侧补1导致死循环,与除法行为不同,强调需注意补码机制以正确统计二进制1的个数... 目录我遇到了这么一个www.chinasem.cn函数由此可以看到也很好理解总结我遇到了这么一个函数template<typename T>unsigned
阅读更多...
C++统计函数执行时间的最佳实践

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
C++ STL-string类底层实现过程

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数
阅读更多...
C++ vector越界问题的完整解决方案

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基
阅读更多...
c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2