避圈法编程 根据避圈法的算法,编写相应程序。
时间: 2024-02-16 09:00:34 浏览: 57
避圈法(Topological Sorting Algorithm)是一种基于拓扑排序的算法,可以用来判断有向图中是否存在圈。如果有,就说明该有向图不是一个DAG(有向无环图)。
下面是使用C++实现的避圈法的代码示例:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1000; // 最大点数
vector<int> G[MAXN]; // 邻接表存图
int in_degree[MAXN]; // 入度
bool vis[MAXN]; // 标记是否访问过
bool topological_sort(int n) {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
q.push(i); // 入度为0的节点入队
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = true; // 标记已访问
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); // 入度为0的节点入队
}
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) return false; // 如果有未访问的节点,说明存在圈
}
return true;
}
int main() {
int n, m;
cin >> n >> m; // 输入点数和边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 输入边的起点和终点
G[u].push_back(v);
in_degree[v]++; // 统计终点的入度
}
if (topological_sort(n)) {
cout << "No cycle found." << endl;
} else {
cout << "Cycle found." << endl;
}
return 0;
}
```
这段代码使用邻接表存储有向图,使用in_degree数组统计每个节点的入度,使用vis数组标记是否访问过。在topological_sort函数中,先把所有入度为0的节点入队,然后不断取出队首元素,并更新其周围节点的入度。如果有节点的入度为0,则将其入队。如果在遍历完所有节点之前,队列为空了,说明不存在圈。否则,就说明存在圈。
注意,避圈法只能用来判断有向图中是否存在圈。对于无向图,需要使用寻圈法。