C++的拓扑排序实现

这篇具有很好参考价值的文章主要介绍了C++的拓扑排序实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

template<typename T = CString, typename _Data = CString>
struct Union_node//!< 节点
{
Union_node() :nColor(0) {}
std::vector<Union_node*> vecNodeSon;
T key;//!< 关键数据
_Data data;//!< 卫星数据
mutable int nColor;//0:白色节点(未发现),1:灰色节点(发现),2:黑色节点(完毕)
};

template<typename T = CString, typename _Data = CString>
class TopologicalSort//!< 拓扑排序
{
using node = std::shared_ptr<Union_node<T, _Data>>;
public:
void setSpNode(const std::vector<node>& spNode) { m_vecSpNode = spNode; }
void setSpNode(std::vector<node>&& spNode) { m_vecSpNode.swap(spNode); }

/*!
* 拓扑排序
* \return 是否是有向无环图
*/
bool topologicalSort(std::vector<node>& vecSpRes) const;
private:
/*!
* 深搜,如果图规模较大,可能会栈溢出,需要用栈辅助
*/
bool dfs(const node& spNode, std::vector<node>& vecSpRes) const;
private:
std::vector<node> m_vecSpNode;//!< 所有节点
};

template<typename T, typename _Data>
bool TopologicalSort<T, _Data>::topologicalSort(std::vector<node>& vecSpRes) const
{
vecSpRes.clear();

// 将所有节点的颜色标记为白色(未发现)
for (auto spNode : m_vecSpNode)
spNode->nColor = 0;

// 对每个白色节点进行深搜
for (auto spNode : m_vecSpNode)
{
if (spNode->nColor != 0)
continue;
if (!dfs(spNode, vecSpRes))
return false;//遇到环,则返回false
}

// 拓扑排列(完成时间晚的放到前面)
std::reverse(vecSpRes.begin(), vecSpRes.end());
return true;
}

template<typename T, typename _Data>
bool TopologicalSort<T, _Data>::dfs(const node& spNode, std::vector<node>& vecSpRes) const
{
spNode->nColor = 1;//标记为灰色节点(未发现)

for (auto spSon : spNode->vecNodeSon)
{
if (spSon->nColor == 1)
return false;//!< 如果遇到了灰色节点,则表示发现了环
else if (spSon->nColor == 0)
{
if (!dfs(spSon, vecSpRes))
return false;//!< 后继节点包含环,返回false
}
}

spNode->nColor = 2;//标记为黑色节点(已完成)
vecSpRes.emplace_back(spNode);
return true;
}文章来源地址https://www.toymoban.com/news/detail-421533.html

到了这里,关于C++的拓扑排序实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 拓扑排序实现循环依赖判断

    本文记录如何通过拓扑排序,实现循环依赖判断 一般提到循环依赖,首先想到的就是Spring框架提供的Bean的循环依赖检测,相关文档可参考: https://blog.csdn.net/cristianoxm/article/details/113246104 本文方案脱离Spring Bean的管理,通过算法实现的方式,完成对象循环依赖的判断,涉及的

    2024年02月05日
    浏览(35)
  • 超详细讲解实现拓扑排序、关键路径

    今天,小编带着大家来学习图中非常重要的一环,拓扑排序和关键路径! 目录 一. 绪论——实际应用 二. 拓扑排序 (一).含义 (二).实现原理  (三).代码实现 三. 关键路径 (一).含义 (二).实现原理  (三).代码实现 首先,我们需要知道的是,拓扑排序是关键路径

    2023年04月14日
    浏览(47)
  • 采用DFS算法实现逆拓扑排序,并判断是否有回路

    看王道视频的时候,有一道思考题,没有找到理想的答案,所以自己思考了一下,记录一下。 问题问的是:在采用DFS算法实现AOV网的逆拓扑排序时如何判断是否有回路? 首先,要理解,在采用DFS算法(深度优先搜索)实现AOV网的拓扑排序,其本质上是对AOV网的DFS生成森林进行

    2024年02月12日
    浏览(42)
  • 【华为OD机试】启动多任务排序(拓扑排序算法—Java&Python&C++&JS实现)

    本文收录于专栏:算法之翼 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年04月15日
    浏览(45)
  • 拓扑排序详解(包含算法原理图解、算法实现过程详解、算法例题变式全面讲解等)

    在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(DAG图)。 如图所示。 对于一个有向图,若x点指向y点,则称x点为y点的入度。 对于一个有向图,若x点指向y点,则称y点为x点的出度。 队列是一种特殊的线性表,特殊之处在

    2024年02月07日
    浏览(52)
  • 拓扑排序及逆拓扑排序

    拓扑排序其实就是对有向无环图的顶点的一种排序,每个顶点出现且只出现一次。 对一个AOV网进行拓扑排序的方法: 1、从AOV网中选择一个入度为0的顶点并输出; 2、从网中删除该顶点和所有以它为起点的有向边; 3、重复1和2直到当前的AOV网为空或当前网中不存在入度为0的

    2024年02月01日
    浏览(42)
  • 数据结构第12周 :( 有向无环图的拓扑排序 + 拓扑排序和关键路径 + 确定比赛名次 + 割点 )

    【问题描述】 由某个集合上的一个偏序得到该集合上的一个全序,这个操作被称为拓扑排序。偏序和全序的定义分别如下:若集合X上的关系R是自反的、反对称的和传递的,则称R是集合X上的偏序关系。设R是集合X上的偏序,如果对每个x,y∈X必有xRy或yRx,则称R是集合X上的全序

    2024年02月08日
    浏览(42)
  • C语言-算法-拓扑排序

    有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列,使得每个人的后辈都比那个人后列出。 第 1 1 1 行一个整数 N N N ( 1 ≤ N ≤ 100 1 le N le 100 1 ≤ N ≤ 100 ),表示家族的人数。接下来 N N N 行,第 i i i 行描述第 i i i

    2024年01月25日
    浏览(40)
  • 数据结构-拓扑排序

    一个无环的有向图称作有向无环图(Directed Acycline Graph),简称DAG图。 DAG图是描述含有公共子式的表达式的有效工具。 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这种有向图为顶 点表示活动的网,简称AOV网。 AOV网中不能出现回路,而判

    2024年02月08日
    浏览(41)
  • 图论应用——拓扑排序

    拓扑排序的原理和宽度优先搜索差不多

    2024年04月26日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包