给出拓扑排序的C++模板
时间: 2024-10-21 11:13:46 浏览: 19
拓扑排序是一种有向无环图(DAG,Directed Acyclic Graph)中节点排序的算法。在C++中,我们可以使用模板来实现一个通用的拓扑排序函数。这里是一个基础版本的模板实现,假设我们有一个顶点和边的数据结构:
```cpp
#include <vector>
#include <queue>
template <typename T>
void topologicalSort(std::vector<std::pair<T, T>>& edges, std::vector<T>& order) {
std::unordered_set<T> visited;
std::queue<T> q;
// 初始化队列:入度为0的节点先加入
for (const auto& edge : edges) {
if (visited.find(edge.first) == visited.end()) {
q.push(edge.first);
}
}
while (!q.empty()) {
T vertex = q.front();
q.pop();
order.push_back(vertex); // 将访问过的节点放入结果列表
visited.insert(vertex);
// 遍历所有邻接节点,如果当前节点未被访问过,则增加其入度并检查是否可以入队
for (const auto& edge : edges) {
if (edge.first == vertex && visited.find(edge.second) == visited.end()) {
--edge.second; // 减少邻接节点的入度
if (edge.second == 0) {
q.push(edge.second);
}
}
}
}
// 如果队列空而未找到解决方案,说明图中存在环
if (q.empty() && !visited.size() == edges.size()) {
throw std::runtime_error("Graph contains a cycle and cannot be sorted");
}
}
```
这个模板接受一个包含顶点对的边的集合`edges`(例如`(u, v)`表示从`u`指向`v`),以及一个用于存放排序结果的向量`order`。注意,对于这个模板,输入的`T`必须支持`==`和`--`操作。
阅读全文