有向无环图判断的C语言代码
时间: 2023-10-19 12:07:52 浏览: 55
判断有向无环图可以使用拓扑排序算法,以下是使用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 图的最大节点数
// 邻接表节点结构体
typedef struct ArcNode {
int adjvex; // 邻接点下标
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
// 顶点信息结构体
typedef struct {
int data; // 顶点数据
ArcNode *firstarc; // 指向该顶点邻接表的指针
} VNode;
// 邻接表图结构体
typedef struct {
VNode adjlist[MAX_VERTEX_NUM]; // 存储图中所有顶点的数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 创建邻接表图
void CreateGraph(ALGraph *G) {
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar();
printf("请输入所有顶点的数据:");
for (int i = 0; i < G->vexnum; i++) {
scanf("%d", &G->adjlist[i].data);
G->adjlist[i].firstarc = NULL;
}
getchar();
printf("请输入每条边的起点和终点:");
for (int i = 0; i < G->arcnum; i++) {
int start, end;
scanf("%d%d", &start, &end);
getchar();
// 创建一个新的邻接节点并将其插入起点的邻接表中
ArcNode *node = (ArcNode *)malloc(sizeof(ArcNode));
node->adjvex = end;
node->next = G->adjlist[start].firstarc;
G->adjlist[start].firstarc = node;
}
}
// 拓扑排序
int TopologicalSort(ALGraph *G) {
int indegree[MAX_VERTEX_NUM] = {0}; // 存储每个顶点的入度
int stack[MAX_VERTEX_NUM], top = -1; // 模拟栈
int count = 0; // 记录已经输出的顶点数
// 统计每个顶点的入度
for (int i = 0; i < G->vexnum; i++) {
ArcNode *node = G->adjlist[i].firstarc;
while (node != NULL) {
indegree[node->adjvex]++;
node = node->next;
}
}
// 将所有入度为0的顶点入栈
for (int i = 0; i < G->vexnum; i++) {
if (indegree[i] == 0) {
stack[++top] = i;
}
}
// 循环处理栈中的顶点
while (top != -1) {
int v = stack[top--]; // 出栈一个顶点
printf("%d ", G->adjlist[v].data); // 输出该顶点
count++;
// 对该顶点的所有邻接点的入度减1
ArcNode *node = G->adjlist[v].firstarc;
while (node != NULL) {
int w = node->adjvex;
indegree[w]--;
// 如果该邻接点的入度为0,则入栈
if (indegree[w] == 0) {
stack[++top] = w;
}
node = node->next;
}
}
// 如果输出的顶点数不等于总顶点数,则表示图中有环
if (count != G->vexnum) {
return 0;
}
return 1;
}
int main() {
ALGraph G;
CreateGraph(&G);
// 判断是否是有向无环图
if (TopologicalSort(&G)) {
printf("该图是有向无环图。\n");
} else {
printf("该图不是有向无环图。\n");
}
return 0;
}
```