欧拉路径算法详解（C++实现图论中的欧拉路径与欧拉回路）

判断条件（无向图）

要判断一个连通无向图是否存在欧拉路径或欧拉回路，只需检查每个顶点的度数（连接的边数）：

• 如果所有顶点的度数都是偶数 → 存在欧拉回路（也是欧拉路径）。
• 如果有且仅有两个顶点的度数是奇数 → 存在欧拉路径（但不是回路），这两个奇度顶点分别是起点和终点。
• 其他情况 → 既无欧拉路径也无欧拉回路。

算法思路：Hierholzer 算法

一旦确认图存在欧拉路径/回路，我们可以使用 Hierholzer 算法 来构造具体路径。该算法的核心思想是：

1. 从合适的起点开始深度优先搜索（DFS）。
2. 每次访问一条边就将其删除（避免重复使用）。
3. 当无法继续前进时，将当前节点加入结果路径。
4. 最终将路径反转，即为欧拉路径。

C++ 实现代码

下面是一个完整的 C++ 实现，支持判断并输出欧拉路径或回路：

#include <iostream>#include <vector>#include <stack>#include <algorithm>using namespace std;// 判断图是否连通（使用 DFS）bool isConnected(const vector<vector<int>>& graph, int n) {    vector<bool> visited(n, false);    stack<int> st;        // 找到第一个有边的顶点作为起点    int start = -1;    for (int i = 0; i < n; ++i) {        if (!graph[i].empty()) {            start = i;            break;        }    }        if (start == -1) return true; // 空图视为连通        st.push(start);    visited[start] = true;        while (!st.empty()) {        int u = st.top();        st.pop();        for (int v : graph[u]) {            if (!visited[v]) {                visited[v] = true;                st.push(v);            }        }    }        // 检查所有有边的顶点是否都被访问    for (int i = 0; i < n; ++i) {        if (!graph[i].empty() && !visited[i])            return false;    }    return true;}// Hierholzer 算法求欧拉路径vector<int> findEulerPath(vector<vector<int>>& graph, int n) {    // 计算每个顶点的度数    vector<int> degree(n, 0);    for (int i = 0; i < n; ++i) {        degree[i] = graph[i].size();    }        // 检查连通性    if (!isConnected(graph, n)) {        return {}; // 不连通，无欧拉路径    }        // 统计奇度顶点    vector<int> oddVertices;    for (int i = 0; i < n; ++i) {        if (degree[i] % 2 == 1)            oddVertices.push_back(i);    }        // 判断是否存在欧拉路径    if (oddVertices.size() != 0 && oddVertices.size() != 2) {        return {}; // 既不是回路也不是路径    }        // 确定起点    int start = 0;    if (!oddVertices.empty()) {        start = oddVertices[0];    } else {        // 找任意一个有边的点作为起点（用于欧拉回路）        for (int i = 0; i < n; ++i) {            if (!graph[i].empty()) {                start = i;                break;            }        }    }        // 使用栈进行 Hierholzer 算法    stack<int> currPath;    vector<int> eulerPath;    currPath.push(start);        while (!currPath.empty()) {        int u = currPath.top();                // 如果还有未访问的边        if (!graph[u].empty()) {            int v = graph[u].back();            graph[u].pop_back();                        // 从邻接表中移除反向边（无向图）            auto it = find(graph[v].begin(), graph[v].end(), u);            if (it != graph[v].end()) {                graph[v].erase(it);            }                        currPath.push(v);        } else {            eulerPath.push_back(u);            currPath.pop();        }    }        return eulerPath;}int main() {    // 示例：5个顶点的图    int n = 5;    vector<vector<int>> graph(n);        // 添加边（无向图）    graph[0].push_back(1); graph[1].push_back(0);    graph[1].push_back(2); graph[2].push_back(1);    graph[2].push_back(3); graph[3].push_back(2);    graph[3].push_back(4); graph[4].push_back(3);    graph[4].push_back(1); graph[1].push_back(4);        vector<int> path = findEulerPath(graph, n);        if (path.empty()) {        cout << "该图不存在欧拉路径或欧拉回路。" << endl;    } else {        cout << "欧拉路径为：";        for (int i = path.size() - 1; i >= 0; --i) {            cout << path[i];            if (i > 0) cout << " -> ";        }        cout << endl;    }        return 0;}

代码说明

• isConnected 函数用于判断图是否连通（欧拉路径存在的前提）。
• findEulerPath 函数先检查度数条件，再用 Hierholzer 算法构建路径。
• 由于是无向图，删除边时需同时从两个顶点的邻接表中移除。
• 最终路径是逆序的，所以输出时从后往前打印。

总结

通过本教程，你已经掌握了如何用 C++算法 实现欧拉路径和欧拉回路的判断与构造。关键在于理解图的度数性质和 Hierholzer 算法的递归思想。这类图论算法是算法竞赛和工程实践中的重要工具，建议多加练习！

如果你觉得这篇文章对你有帮助，欢迎分享给更多学习 C++语言 和算法的朋友！