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;
}