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;
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
