论坛 › 网络安全 › C++的拓扑排序实现

络腮胡菲菲 发表于 2023-4-22 17:26:42

C++的拓扑排序实现

template
        struct Union_node//!< 节点
        {
                Union_node() :nColor(0) {}
                std::vector vecNodeSon;
                T key;//!< 关键数据
                _Data data;//!< 卫星数据
                mutable int nColor;//0:白色节点(未发现),1:灰色节点(发现),2:黑色节点(完毕)
        };
        template
        class TopologicalSort//!< 拓扑排序
        {
                using node = std::shared_ptr;
        public:
                void setSpNode(const std::vector& spNode) { m_vecSpNode = spNode; }
                void setSpNode(std::vector&& spNode) { m_vecSpNode.swap(spNode); }
                /*!
                * 拓扑排序
                * \return 是否是有向无环图
                */
                bool topologicalSort(std::vector& vecSpRes) const;
        private:
                /*!
                * 深搜，如果图规模较大，可能会栈溢出，需要用栈辅助
                */
                bool dfs(const node& spNode, std::vector& vecSpRes) const;
        private:
                std::vector m_vecSpNode;//!< 所有节点
        };
        template
        bool TopologicalSort::topologicalSort(std::vector& 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
        bool TopologicalSort::dfs(const node& spNode, std::vector& 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;
        }

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

查看完整版本: C++的拓扑排序实现