template<typename T = CString, typename _Data = https://www.cnblogs.com/shizhimofa/archive/2023/04/22/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 = https://www.cnblogs.com/shizhimofa/archive/2023/04/22/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.uj5u.com/houduan/550845.html
標籤：其他
下一篇：返回列表