c++topsort

C++中的topsort是指拓扑排序，它是一种对有向无环图进行排序的算法。拓扑排序可以用来解决很多实际问题，比如任务调度、依赖关系等。在C++中，可以使用邻接表或邻接矩阵来表示有向无环图，并使用类来实现拓扑排序算法。拓扑排序的基本思想是，从图中选择一个入度为0的顶点，将其输出并从图中删除，然后更新与该顶点相邻的顶点的入度，重复这个过程直到所有顶点都被输出。如果图中存在环，则无法进行拓扑排序。

相关问题

用C++代码写拓扑排序template <typename T, typename WGT_T> std::vector<typename graf<T, WGT_T>::size_type> topsort(const graf<T, WGT_T>& g)

以下是用C++代码实现拓扑排序的模板函数：

#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>`是一个自定义的图类型，可以通过实现以下接口来定义：

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>`类型的拓扑序列，表示按照拓扑排序排好序的顶点序列。

用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)

以下是用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;
}

使用方法如下：

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 的结点，然后依次访问队列中的结点并将其从图中删除。如果存在环，则说明无法进行拓扑排序，我们在最后抛出了一个运行时错误。