离散数学实验C语言欧拉图

欧拉图是指一张图中存在一条经过每个边恰好一次的路径。如果这条路径的起点和终点重合，则该图为欧拉回路。判断一个无向图是否为欧拉图，可以通过以下步骤：

1. 判断图是否连通，如果不连通，则一定不是欧拉图。
2. 统计每个节点的度数，如果存在度数为奇数的节点，则一定不是欧拉图。
3. 如果每个节点的度数都是偶数，则该图是欧拉图。

以下是基于邻接矩阵存储的无向图的判断欧拉图的 C 语言代码：

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

#define MAX_VERTICES 100

int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int degree[MAX_VERTICES]; // 每个节点的度数
int visited[MAX_VERTICES]; // 记录节点是否被访问过
int num_vertices, num_edges; // 图的节点数和边数

void dfs(int v) {
    visited[v] = 1;
    for (int i = 0; i < num_vertices; i++) {
        if (adj[v][i] && !visited[i]) {
            dfs(i);
        }
    }
}

int is_connected() {
    for (int i = 0; i < num_vertices; i++) {
        visited[i] = 0;
    }
    dfs(0);
    for (int i = 0; i < num_vertices; i++) {
        if (!visited[i]) {
            return 0;
        }
    }
    return 1;
}

int is_eulerian() {
    if (!is_connected()) {
        return 0;
    }
    int odd_degree_count = 0;
    for (int i = 0; i < num_vertices; i++) {
        degree[i] = 0;
        for (int j = 0; j < num_vertices; j++) {
            if (adj[i][j]) {
                degree[i]++;
            }
        }
        if (degree[i] % 2 != 0) {
            odd_degree_count++;
        }
    }
    if (odd_degree_count > 2) {
        return 0;
    }
    return 1;
}

int main() {
    printf("请输入节点数和边数：\n");
    scanf("%d%d", &num_vertices, &num_edges);
    printf("请输入每条边的两个节点：\n");
    for (int i = 0; i < num_edges; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u][v] = adj[v][u] = 1;
    }
    if (is_eulerian()) {
        printf("这是一个欧拉图。\n");
    } else {
        printf("这不是一个欧拉图。\n");
    }
    return 0;
}