用C++代码写拓扑排序template <typename T, typename WGT_T> std::vector<typename graf<T, WGT_T>::size_type> topsort(const graf<T, WGT_T>& g)
时间: 2023-06-25 17:04:13 浏览: 140
c++实现拓扑排序
5星 · 资源好评率100%
以下是用C++代码实现拓扑排序的模板函数:
```cpp
#include <vector>
#include <queue>
template <typename T, typename WGT_T>
std::vector<typename graf<T, WGT_T>::size_type> topsort(const graf<T, WGT_T>& g)
{
// 记录每个顶点的入度
std::vector<typename graf<T, WGT_T>::size_type> in_degree(g.size(), 0);
for (auto& e : g.edges()) {
++in_degree[e.to()];
}
// 将入度为0的顶点加入队列
std::queue<typename graf<T, WGT_T>::size_type> q;
for (typename graf<T, WGT_T>::size_type i = 0; i < g.size(); ++i) {
if (in_degree[i] == 0) {
q.push(i);
}
}
// 依次输出拓扑序列
std::vector<typename graf<T, WGT_T>::size_type> topo_order;
while (!q.empty()) {
auto u = q.front();
q.pop();
topo_order.push_back(u);
for (auto& e : g.edges(u)) {
auto v = e.to();
--in_degree[v];
if (in_degree[v] == 0) {
q.push(v);
}
}
}
return topo_order;
}
```
该函数接受一个模板类型为`graf<T, WGT_T>`的参数`g`,表示待排序的图。其中`graf<T, WGT_T>`是一个自定义的图类型,可以通过实现以下接口来定义:
```cpp
template <typename T, typename WGT_T>
class graf {
public:
using size_type = std::size_t;
std::vector<edge<T, WGT_T>> edges() const;
std::vector<edge<T, WGT_T>> edges(size_type u) const;
size_type size() const;
};
```
其中`edge<T, WGT_T>`表示一条边,`size_type`表示顶点的类型。
该函数返回一个`std::vector<typename graf<T, WGT_T>::size_type>`类型的拓扑序列,表示按照拓扑排序排好序的顶点序列。
阅读全文