c语言邻接矩阵利用拓扑排序判断图中是否有回路的函数
时间: 2023-08-14 10:08:34 浏览: 154
以下是一个基于邻接矩阵的C语言函数,利用拓扑排序来判断有向图中是否有回路:
int hasCycle(int n, int graph[][n]) {
int indegree[n], queue[n], front = 0, rear = -1;
memset(indegree, 0, sizeof(indegree)); // 初始化入度数组为0
// 计算每个顶点的入度
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j]) {
indegree[j]++;
}
}
}
// 将入度为0的顶点加入队列
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue[++rear] = i;
}
}
// 拓扑排序
int count = 0;
while (front <= rear) {
int u = queue[front++];
count++;
for (int v = 0; v < n; v++) {
if (graph[u][v]) {
if (--indegree[v] == 0) {
queue[++rear] = v;
}
}
}
}
return count != n; // 如果count不等于n,说明有回路
}
该函数接受两个参数:n表示图中顶点的数量,graph是一个邻接矩阵,表示图的结构。如果函数返回1,则说明图中存在回路;否则,返回0表示图中不存在回路。
阅读全文
相关推荐















