c++有向无环图的判定
时间: 2023-12-06 17:09:34 浏览: 157
判断有向图中是否存在环
4星 · 用户满意度95%
C++中判断有向图是否为有向无环图(DAG)的方法通常使用拓扑排序(topological sort)算法。
拓扑排序算法的基本思路是,从DAG中选择一个没有前驱(即入度为0)的顶点,并输出它,然后把它从图中删除,同时更新剩余顶点的入度。重复这个过程直到所有顶点都被输出。如果最后输出的顶点数目少于图中的顶点数目,则该有向图中存在环路,因为环路中的顶点之间互相有依赖关系,因此它们的入度都不为0,无法被输出。
下面是一个示例代码,可以判断给定的有向图是否为DAG:
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> G[N]; // 存储图的邻接表
int in_degree[N]; // 存储每个点的入度
bool topological_sort(int n) {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) q.push(i); // 将所有入度为0的点加入队列
}
int cnt = 0; // 计数已经输出的顶点数目
while (!q.empty()) {
int u = q.front(); q.pop();
cnt++;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
in_degree[v]--;
if (in_degree[v] == 0) q.push(v);
}
}
return cnt == n; // 如果所有顶点都被输出,则图是DAG
}
int main() {
int n, m;
cin >> n >> m; // 读入点数和边数
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v; // 读入一条边
G[u].push_back(v); // 将边加入邻接表
in_degree[v]++; // 更新入度
}
if (topological_sort(n)) {
cout << "It is a DAG." << endl;
} else {
cout << "It is not a DAG." << endl;
}
return 0;
}
```
在上述代码中,我们使用邻接表存储图,使用数组`in_degree`存储每个点的入度。在`topological_sort`函数中,我们首先将所有入度为0的顶点加入队列,然后不断从队列中取出顶点,并将其所有出边指向的顶点的入度减1。如果某个顶点的入度变为0,就将其加入队列。最终,如果所有顶点都被输出,就说明图是DAG,否则说明图中存在环路。
阅读全文