用C语言编写程序判断图是否存在欧拉回路

判断图是否存在欧拉回路可以使用Fleury算法，具体步骤如下：

1. 对于无向图，判断每个顶点的度数是否为偶数；对于有向图，判断每个顶点的入度和出度是否相等。

2. 如果有顶点的度数不为偶数（或者入度和出度不相等），则该图不存在欧拉回路，直接返回。

3. 选择任意一个顶点作为起点，进行深度优先搜索（DFS）。

4. 在DFS过程中，遍历到的每条边都标记为已访问，同时记录下已访问的边的数量。

5. 如果当前节点的所有出边都已经访问过，则回溯到上一个节点，继续搜索其它的出边。

6. 如果已访问的边的数量等于图中边的总数，则该图存在欧拉回路，返回True；否则不存在欧拉回路，返回False。

以下是用C语言实现判断图是否存在欧拉回路的示例代码：

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

#define MAX_VERTEX_NUM 100

// 图的邻接矩阵表示法
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 顶点数组
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vertex_num; // 顶点数量
    int edge_num; // 边数量
} Graph;

// DFS遍历图
void DFS(Graph* graph, int vertex, int* visited, int* edge_count, int* exist_euler_circuit) {
    visited[vertex] = 1; // 标记当前节点已访问

    // 遍历所有的出边
    for (int i = 0; i < graph->vertex_num; i++) {
        if (graph->edge[vertex][i] > 0 && !visited[i]) { // 当前节点到i的边存在且i未被访问
            (*edge_count)++; // 记录已访问的边的数量
            DFS(graph, i, visited, edge_count, exist_euler_circuit); // 继续搜索
        }
    }

    // 如果当前节点的所有出边都已经访问过，则回溯到上一个节点
    if (*edge_count == graph->edge_num) {
        (*exist_euler_circuit) = 1; // 存在欧拉回路
        return;
    }
}

// 判断图是否存在欧拉回路
int has_euler_circuit(Graph* graph) {
    int visited[MAX_VERTEX_NUM] = { 0 }; // 记录每个节点是否已访问
    int edge_count = 0; // 记录已访问的边的数量
    int exist_euler_circuit = 0; // 是否存在欧拉回路

    // 判断每个顶点的度数是否为偶数
    for (int i = 0; i < graph->vertex_num; i++) {
        int degree = 0;
        for (int j = 0; j < graph->vertex_num; j++) {
            degree += graph->edge[i][j];
        }
        if (degree % 2 != 0) {
            return 0; // 度数不为偶数，不存在欧拉回路
        }
    }

    // 从任意一个顶点开始进行DFS
    DFS(graph, 0, visited, &edge_count, &exist_euler_circuit);

    return exist_euler_circuit;
}

int main() {
    Graph graph = {
        {0, 1, 2, 3, 4},
        {
            {0, 1, 0, 1, 0},
            {1, 0, 1, 1, 1},
            {0, 1, 0, 1, 1},
            {1, 1, 1, 0, 1},
            {0, 1, 1, 1, 0}
        },
        5,
        10
    };

    if (has_euler_circuit(&graph)) {
        printf("存在欧拉回路\n");
    } else {
        printf("不存在欧拉回路\n");
    }

    return 0;
}