c++拓扑排序 代码实现
时间: 2024-08-12 11:01:32 浏览: 28
C++中的拓扑排序通常用于有向无环图(DAG, Directed Acyclic Graph)中,它将图中所有的节点按照它们的依赖关系排成线性的顺序。这种排序可以帮助我们确定任务的执行顺序,例如在一个任务图中,先完成的任务可以放在前面。
下面是一个简单的C++代码实现,使用邻接表来表示图,并使用深度优先搜索(DFS)进行排序:
```cpp
#include <iostream>
#include <vector>
#include <list>
using namespace std;
// 图节点结构体
struct Node {
int id;
vector<int> adj; // 存储邻居节点
};
// 检查图是否强连通分量
bool isCyclic(Node* node, list<Node*> &visited, list<Node*>& result) {
visited.push_back(node);
bool hasCycle = false;
for (int neighbor : node->adj) {
if (visited.end() == find(visited.begin(), visited.end(), static_cast<Node*>(neighbor))) {
hasCycle |= isCyclic(neighbor, visited, result);
}
}
if (!hasCycle) {
result.push_back(node);
return false;
} else {
visited.pop_back();
return true;
}
}
// 拓扑排序
void topologicalSort(vector<Node>& graph) {
int n = graph.size();
list<Node*> nodes(n), result;
// 初始化所有节点为未访问状态
for (int i = 0; i < n; ++i)
nodes[i] = &graph[i];
// 对每个节点,如果发现没有从它指向的边,将其加入结果列表
for (Node* node : nodes) {
if (isCyclic(node, list<Node*>(), result)) { // 如果存在环,则无法排序
cout << "Graph contains a cycle and is not a DAG." << endl;
return;
}
}
// 将节点按顺序添加到结果列表
while (!result.empty()) {
Node* current = result.front();
result.pop_front();
cout << current->id << " ";
for (int neighbor : current->adj)
nodes.erase(find(nodes.begin(), nodes.end(), static_cast<Node*>(neighbor)));
}
}
// 示例图构造
void buildExampleGraph(vector<Node>& graph) {
Node node1{1, {2}};
Node node2{2, {3}};
Node node3{3, {}};
graph.push_back(node1);
graph.push_back(node2);
graph.push_back(node3);
}
int main() {
vector<Node> graph;
buildExampleGraph(graph); // 假设这里构造了一个示例图
cout << "Topological sort of the example graph: ";
topologicalSort(graph);
cout << endl;
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)