欧拉路径算法详解（Java语言实现图论中的欧拉路径与欧拉回路）

判断条件（无向图）

要判断一个无向图是否存在欧拉路径或欧拉回路，需满足以下条件：

• 欧拉回路存在：图是连通的，且所有顶点的度数都是偶数。
• 欧拉路径存在（但不是回路）：图是连通的，且恰好有两个顶点的度数是奇数（这两个点分别是路径的起点和终点）。

注意：如果图不连通，则既不存在欧拉路径，也不存在欧拉回路。

Java 实现步骤

我们将分三步实现：

1. 构建图（使用邻接表）
2. 判断图是否连通（使用 DFS 或 BFS）
3. 检查每个顶点的度数，判断是否存在欧拉路径/回路

1. 图的表示

我们使用 ArrayList<List<Integer>> 来表示邻接表。

import java.util.*;public class EulerPath {    private int V; // 顶点数量    private List<List<Integer>> adj;    public EulerPath(int v) {        V = v;        adj = new ArrayList<>();        for (int i = 0; i < v; i++) {            adj.add(new ArrayList<>());        }    }    public void addEdge(int u, int v) {        adj.get(u).add(v);        adj.get(v).add(u); // 无向图    }}

2. 判断图是否连通

使用深度优先搜索（DFS）从任意非孤立点出发，看是否能访问所有非零度顶点。

private boolean isConnected() {    // 找到第一个有边的顶点    int start = -1;    for (int i = 0; i < V; i++) {        if (!adj.get(i).isEmpty()) {            start = i;            break;        }    }    if (start == -1) return true; // 空图视为连通    boolean[] visited = new boolean[V];    dfs(start, visited);    // 检查所有有边的顶点是否都被访问    for (int i = 0; i < V; i++) {        if (!adj.get(i).isEmpty() && !visited[i]) {            return false;        }    }    return true;}private void dfs(int v, boolean[] visited) {    visited[v] = true;    for (int neighbor : adj.get(v)) {        if (!visited[neighbor]) {            dfs(neighbor, visited);        }    }}

3. 判断欧拉路径/回路

统计每个顶点的度数（即邻接表大小），然后根据规则判断。

public void checkEuler() {    if (!isConnected()) {        System.out.println("图不连通，不存在欧拉路径或欧拉回路。");        return;    }    int oddDegreeCount = 0;    for (int i = 0; i < V; i++) {        if (adj.get(i).size() % 2 != 0) {            oddDegreeCount++;        }    }    if (oddDegreeCount == 0) {        System.out.println("存在欧拉回路！");    } else if (oddDegreeCount == 2) {        System.out.println("存在欧拉路径（但不是回路）！");    } else {        System.out.println("既无欧拉路径，也无欧拉回路。");    }}

完整测试示例

public static void main(String[] args) {    EulerPath g = new EulerPath(5);    g.addEdge(0, 1);    g.addEdge(1, 2);    g.addEdge(2, 3);    g.addEdge(3, 4);    g.checkEuler(); // 输出：存在欧拉路径（但不是回路）！}

总结

通过本教程，你已经掌握了如何用 Java 实现 欧拉路径算法。关键点在于：

• 理解欧拉路径与欧拉回路的定义
• 掌握图连通性判断（DFS/BFS）
• 利用顶点度数判断类型

这些知识属于图论算法教程中的核心内容，也是面试常考题。希望你能动手实践，加深理解！

如果你正在学习Java实现欧拉路径或准备算法面试，建议多画图、多调试，逐步掌握欧拉回路检测的逻辑。

祝你编程愉快！