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++中实现调试日志输出》在C++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳：精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
Python中lambda排序的六种方法

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序
阅读更多...
深入理解C++ 空类大小

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中，规
阅读更多...
关于Java内存访问重排序的研究

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int
阅读更多...
在 VSCode 中配置 C++ 开发环境的详细教程

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode（VSCode）中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境：详细教程1. 什么是 VSCode？2. 安装 VSCo
阅读更多...
C++11的函数包装器std::function使用示例

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2