c语言 无向图输出环路径代码

以下是一份基于邻接表的无向图输出环路径的C语言代码：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 邻接表中的边节点
typedef struct EdgeNode {
    int adjvex; // 邻接点下标
    struct EdgeNode* next; // 指向下一个邻接点
} EdgeNode;

// 邻接表中的顶点节点
typedef struct VertexNode {
    int data; // 顶点信息
    EdgeNode* firstedge; // 指向第一个邻接点
} VertexNode;

// 无向图结构体
typedef struct {
    VertexNode adjlist[MAX_VERTEX_NUM]; // 邻接表
    int vertex_num, edge_num; // 顶点数和边数
} Graph;

// 初始化无向图
void init_graph(Graph* G, int vertex_num) {
    G->vertex_num = vertex_num;
    G->edge_num = 0;
    for (int i = 0; i < vertex_num; i++) {
        G->adjlist[i].data = i; // 顶点信息默认为下标
        G->adjlist[i].firstedge = NULL; // 初始时没有邻接点
    }
}

// 添加无向图的边
void add_edge(Graph* G, int u, int v) {
    // 新建边节点
    EdgeNode* new_edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    new_edge->adjvex = v;
    new_edge->next = G->adjlist[u].firstedge;
    G->adjlist[u].firstedge = new_edge;

    // 由于是无向图，所以还需要添加反向的边
    new_edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    new_edge->adjvex = u;
    new_edge->next = G->adjlist[v].firstedge;
    G->adjlist[v].firstedge = new_edge;

    G->edge_num++;
}

// 判断当前节点是否在路径上
int in_path(int* path, int path_len, int v) {
    for (int i = 0; i < path_len; i++) {
        if (path[i] == v) {
            return 1;
        }
    }
    return 0;
}

// 输出环路径
void print_path(int* path, int path_len, int start) {
    printf("%d", start);
    for (int i = 0; i < path_len; i++) {
        printf("-%d", path[i]);
    }
    printf("-%d\n", start);
}

// DFS遍历无向图，查找环路径
void dfs(Graph* G, int v, int* visited, int* path, int path_len) {
    visited[v] = 1;
    EdgeNode* p = G->adjlist[v].firstedge;
    while (p != NULL) {
        int adjvex = p->adjvex;
        if (!visited[adjvex]) { // 邻接点未被访问过
            path[path_len] = adjvex;
            dfs(G, adjvex, visited, path, path_len + 1);
        } else if (in_path(path, path_len, adjvex) && adjvex != path[0]) { // 邻接点已被访问过，且在路径上
            print_path(path, path_len, adjvex);
        }
        p = p->next;
    }
    visited[v] = 0; // 恢复状态
}

// 查找无向图中的环路径
void find_cycle(Graph* G) {
    int visited[MAX_VERTEX_NUM] = {0}; // 标记顶点是否被访问过
    int path[MAX_VERTEX_NUM] = {0}; // 记录访问路径
    for (int i = 0; i < G->vertex_num; i++) {
        path[0] = i;
        dfs(G, i, visited, path, 1);
    }
}

int main() {
    Graph G;
    init_graph(&G, 6);
    add_edge(&G, 0, 1);
    add_edge(&G, 0, 2);
    add_edge(&G, 1, 2);
    add_edge(&G, 1, 3);
    add_edge(&G, 2, 3);
    add_edge(&G, 3, 4);
    add_edge(&G, 4, 5);
    find_cycle(&G);
    return 0;
}

这份代码实现了基于邻接表的无向图表示和DFS遍历，并在DFS遍历时查找环路径。具体实现方法是，用一个数组`visited`来标记每个顶点是否被访问过，用另一个数组`path`记录当前访问路径。当访问到一个已经被访问过的邻接点时，如果该邻接点不是路径的起点，且在路径上，那么就找到了一个环路径，输出即可。