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
}
}文章来源:https://www.toymoban.com/news/detail-421533.html
spNode->nColor = 2;//标记为黑色节点(已完成)
vecSpRes.emplace_back(spNode);
return true;
}文章来源地址https://www.toymoban.com/news/detail-421533.html
到了这里,关于C++的拓扑排序实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!