C语言写一份成环检测算法

C语言成环检测算法示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100 // 图的最大顶点数

typedef struct ArcNode { // 图的边表结点定义
    int adjvex;          // 相邻顶点在顶点数组中的下标
    struct ArcNode* nextarc; // 指向下一条边的指针
}ArcNode;

typedef struct VNode { // 图的顶点表结点定义
    int data;           // 顶点信息
    ArcNode* firstarc;  // 指向第一条边的指针
}VNode;

typedef struct { // 图的邻接表结构体定义
    VNode vertices[MAX_VERTEX_NUM]; // 顶点数组
    int vexnum, arcnum;     // 存储顶点数和边数
}ALGraph;

void CreateGraph(ALGraph* G) { // 创建邻接表表示的无向图
    int i, j;
    printf("输入图的顶点数和边数\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("输入图的各个顶点信息\n");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL; // 初始化边表链表头指针
    }
    printf("输入构成各边的顶点编号\n");
    for (j = 0; j < G->arcnum; j++) {
        int v1, v2;
        printf("输入边的端点：");
        scanf("%d%d", &v1, &v2);
        ArcNode* p1 = (ArcNode*)malloc(sizeof(ArcNode));
        p1->adjvex = v2;
        p1->nextarc = G->vertices[v1].firstarc;
        G->vertices[v1].firstarc = p1;

        ArcNode* p2 = (ArcNode*)malloc(sizeof(ArcNode));
        p2->adjvex = v1;
        p2->nextarc = G->vertices[v2].firstarc;
        G->vertices[v2].firstarc = p2;
    }
}

int visited[MAX_VERTEX_NUM];
int DFS(ALGraph* G, int v, int p) { // 检测当前节点是否成环
    int flag = 0;
    visited[v] = 1;
    ArcNode* pArc = G->vertices[v].firstarc;
    while (pArc != NULL) {
        int u = pArc->adjvex;
        if (visited[u] == 0) { // 没有访问过，继续递归
            flag |= DFS(G, u, v);
        }
        else if (u != p) { // 已经访问过，且不是父节点，说明成环
            flag = 1;
        }
        pArc = pArc->nextarc;
    }
    return flag;
}

int IsCyclic(ALGraph* G) { // 判断无向图是否成环
    int i;
    for (i = 0; i < G->vexnum; i++) {
        visited[i] = 0; // 初始化所有节点为未访问状态
    }
    for (i = 0; i < G->vexnum; i++) {
        if (visited[i] == 0 && DFS(G, i, -1)) { // 从尚未访问的节点开始深度优先搜索
            return 1; // 若成环直接返回
        }
    }
    return 0; // 无环返回0
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    if (IsCyclic(&G)) {
        printf("The graph contains cycle(s).\n");
    }
    else {
        printf("The graph is acyclic.\n");
    }
    return 0;
}

实现思路：

使用深度优先搜索（DFS）算法，搜索过程中每当访问到已经访问过的节点，就判断其是否是当前节点的父节点，如果不是，则说明产生了环。这是因为每条边被确定为一次前往（存储）和两次访问（提取），所以如果不是父节点，但已访问，那么对应的边必定要重复。对于无向图判断环，需要加一个入口函数，从所有点开始都遍历一遍。代码实现过程中，用visited数组记录每个节点的遍历状态，用-1代表还未访问，用0代表已访问，以区分树边和横叉边。输入和输出都通过标准输入和输出完成。