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

热门相关：地球第一剑   天启预报   豪门闪婚：帝少的神秘冷妻   大神你人设崩了   霸皇纪