探索图的奇妙之旅（C语言实现欧拉路径算法详解）

算法思路

我们将使用Hierholzer 算法来寻找欧拉路径。该算法的基本思想是：
1. 从合适的起点开始（若存在欧拉回路，可任选一点；若为欧拉路径，则必须从奇度顶点出发）。
2. 深度优先遍历图，每次访问一条未访问的边，并将其标记为已访问。
3. 当无法继续前进时，将当前顶点加入结果路径。
4. 最终将路径反转，即可得到欧拉路径。

C语言实现

下面是一个完整的 C 语言程序，用于判断无向图是否存在欧拉路径/回路，并输出路径（如果存在）。

#include <stdio.h>#include <stdlib.h>#define MAX_VERTICES 100int graph[MAX_VERTICES][MAX_VERTICES];int degree[MAX_VERTICES];int path[1000];int pathIndex = 0;int V; // 顶点数量// 深度优先搜索，用于 Hierholzer 算法void dfs(int u) {    for (int v = 0; v < V; v++) {        if (graph[u][v] > 0) {            graph[u][v]--;            graph[v][u]--;            dfs(v);        }    }    path[pathIndex++] = u;}// 判断是否存在欧拉路径或回路int hasEulerPath() {    int oddCount = 0;    int startVertex = 0;    // 计算每个顶点的度数    for (int i = 0; i < V; i++) {        degree[i] = 0;        for (int j = 0; j < V; j++) {            degree[i] += graph[i][j];        }        if (degree[i] % 2 != 0) {            oddCount++;            startVertex = i; // 记录奇度顶点作为起点        }    }    if (oddCount == 0) {        printf("存在欧拉回路！\n");        return 0; // 所有顶点度数为偶数    } else if (oddCount == 2) {        printf("存在欧拉路径！\n");        return startVertex; // 从奇度顶点出发    } else {        printf("不存在欧拉路径或回路。\n");        return -1;    }}int main() {    // 示例：输入图的邻接矩阵    V = 5;    // 初始化图（无向图，对称矩阵）    int edges[][2] = {{0,1}, {1,2}, {2,3}, {3,4}, {4,1}};    int E = sizeof(edges)/sizeof(edges[0]);    // 构建邻接矩阵    for (int i = 0; i < E; i++) {        int u = edges[i][0];        int v = edges[i][1];        graph[u][v]++;        graph[v][u]++;    }    int start = hasEulerPath();    if (start != -1) {        pathIndex = 0;        dfs(start);        printf("欧拉路径为：");        for (int i = pathIndex - 1; i >= 0; i--) {            printf("%d ", path[i]);        }        printf("\n");    }    return 0;}

代码说明

- 我们使用邻接矩阵 graph 表示无向图，支持多重边。
- hasEulerPath() 函数统计奇度顶点数量，判断是否存在欧拉路径/回路。
- dfs() 是 Hierholzer 算法的核心，通过递归构建路径。
- 最终路径是逆序存储的，因此输出时需从后往前打印。

总结

通过本教程，你已经掌握了如何用 C 语言实现欧拉路径算法。理解欧拉路径、欧拉回路的判定条件以及 Hierholzer 算法的执行过程，是学习图论基础的重要一步。这个C语言算法不仅有助于面试准备，也能加深你对图遍历的理解。

尝试修改图的结构，看看程序是否能正确识别不同情况下的欧拉路径吧！