有向图的拓扑序列C++
时间: 2024-08-15 17:02:47 浏览: 28
有向图的拓扑排序是一种将图中顶点按照依赖关系线性排列的方式,如果存在一条从u到v的有向边,那么在结果序列中,u会出现在v之前。这种排序通常应用于任务调度、数据流程分析等场景,保证了所有依赖于其他任务的任务都在其依赖完成之后。
在C++中,你可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法来寻找拓扑序列。这里提供一种基于DFS的简单实现:
```cpp
#include <vector>
#include <queue>
// 图结构定义
using namespace std;
struct Edge {
int from, to;
};
class Graph {
private:
vector<vector<int>> adj; // 存储邻接表
public:
void addEdge(int u, int v) {
adj[u].push_back(v);
}
bool isSafe(vector<int>& topo, int node) { // 检查是否存在环
for (int i : adj[node])
if (topo[i] > topo[node])
return false;
return true;
}
vector<int> topologicalSort() {
vector<int> topo(adj.size(), 0); // 初始化拓扑序列表
queue<int> q;
int count = 0;
for (int i = 0; i < adj.size(); ++i)
if (!adj[i].size()) // 找到入度为0的节点(开始)
q.push(i), topo[i] = ++count;
while (!q.empty()) {
int node = q.front();
q.pop();
if (isSafe(topo, node)) { // 如果当前节点安全,则更新其后续节点
for (int neighbor : adj[node]) {
topo[neighbor]++;
if (topo[neighbor] == 1) // 当前节点的邻接节点入度变为0,加入队列
q.push(neighbor);
}
}
}
// 返回拓扑序列
vector<int> result;
for (int i = 0; i < adj.size(); ++i)
if (topo[i] > 0)
result.push_back(i);
return result;
}
};
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)