用C++代码写拓扑排序template <typename T, typename WGT_T> std::vector<typename DASS::graf<T, WGT_T>::size_type> topsort(const DASS::graf<T, WGT_T>& g)
时间: 2023-06-25 18:04:17 浏览: 157
以下是用C++实现拓扑排序的代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
template <typename T, typename WGT_T>
std::vector<typename DASS::graf<T, WGT_T>::size_type> topsort(const DASS::graf<T, WGT_T>& g) {
// 初始化入度为 0 的结点队列
std::queue<typename DASS::graf<T, WGT_T>::size_type> q;
std::vector<typename DASS::graf<T, WGT_T>::size_type> in_degree(g.size(), 0);
for (typename DASS::graf<T, WGT_T>::size_type u = 0; u < g.size(); ++u) {
for (const auto& e : g[u]) {
++in_degree[e.v];
}
}
for (typename DASS::graf<T, WGT_T>::size_type u = 0; u < g.size(); ++u) {
if (in_degree[u] == 0) {
q.push(u);
}
}
// 执行拓扑排序
std::vector<typename DASS::graf<T, WGT_T>::size_type> order;
while (!q.empty()) {
typename DASS::graf<T, WGT_T>::size_type u = q.front();
q.pop();
order.push_back(u);
for (const auto& e : g[u]) {
--in_degree[e.v];
if (in_degree[e.v] == 0) {
q.push(e.v);
}
}
}
// 如果存在环,则说明无法进行拓扑排序
if (order.size() != g.size()) {
throw std::runtime_error("The graph contains a cycle");
}
return order;
}
```
使用方法如下:
```c++
DASS::graf<int, int> g(6);
g[0].emplace_back(1, 1);
g[0].emplace_back(2, 1);
g[1].emplace_back(3, 1);
g[2].emplace_back(3, 1);
g[2].emplace_back(4, 1);
g[3].emplace_back(5, 1);
g[4].emplace_back(5, 1);
std::vector<DASS::graf<int, int>::size_type> order = topsort(g);
for (auto u : order) {
std::cout << u << " ";
}
// 输出:0 2 1 4 3 5
```
上述代码中,我们使用了一个队列来存储入度为 0 的结点,然后依次访问队列中的结点并将其从图中删除。如果存在环,则说明无法进行拓扑排序,我们在最后抛出了一个运行时错误。
阅读全文