每日算法 — 使用java实现欧拉回路：Fleury与Hierholzer算法

欧拉回路是图论中最经典的问题之一：给定无向图或有向图，找到一条经过每条边恰好一次并最终回到起点的闭合路径。该问题源于哥尼斯堡七桥问题，由欧拉在1736年解决并开创了图论学科。本文用Java实现两种经典算法——Fleury算法与Hierholzer算法，包含欧拉路存在性判定、完整代码实现与复杂度分析。

一、欧拉回路的判定定理

在寻找欧拉回路之前，必须判定其是否存在。欧拉给出了如下经典定理：

无向图：连通图存在欧拉回路，当且仅当每个顶点的度数均为偶数；存在欧拉通路（非回路），当且仅当恰好有两个顶点度数为奇数。

有向图：弱连通的有向图存在欧拉回路，当且仅当每个顶点的入度等于出度；存在欧拉通路，当且仅当恰好一个顶点出度比入度大1（起点），一个顶点入度比出度大1（终点），其余顶点入度等于出度。

import java.util.*;

/**
 * 图结构：支持有向/无向图，邻接表存储
 */
public class Graph {
    public int n;                          // 顶点数
    public List<List<Edge>> adj;           // 邻接表
    public boolean directed;               // 是否是有向图
    private int edgeCount = 0;

    public Graph(int n, boolean directed) {
        this.n = n;
        this.directed = directed;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    }

    /** 添加边，返回边的唯一ID */
    public void addEdge(int u, int v) {
        int eid = edgeCount++;
        adj.get(u).add(new Edge(u, v, eid));
        if (!directed) {
            adj.get(v).add(new Edge(v, u, eid));
        }
    }

    /** 获取所有边的数量 */
    public int edgeCount() { return edgeCount; }

    /**
     * 判定欧拉回路/通路是否存在
     * @return [是否存在欧拉回路, 是否存在欧拉通路, 起点（若存在通路）]
     */
    public boolean[] checkEuler() {
        if (directed) return checkDirected();
        else return checkUndirected();
    }

    private boolean[] checkUndirected() {
        // 检查连通性（忽略孤立点）
        if (!isConnected()) return new boolean[]{false, false, false};

        int oddCount = 0;
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (adj.get(i).size() % 2 == 1) {
                oddCount++;
                start = i;
            }
        }
        // 所有偶度 -> 欧拉回路
        // 恰好两个奇度 -> 欧拉通路
        boolean hasCircuit = (oddCount == 0);
        boolean hasPath = (oddCount == 0 || oddCount == 2);
        return new boolean[]{hasCircuit, hasPath, hasPath};
    }

    private boolean[] checkDirected() {
        if (!isWeaklyConnected()) return new boolean[]{false, false, false};

        int[] inDegree = new int[n];
        int[] outDegree = new int[n];
        for (int u = 0; u < n; u++) {
            outDegree[u] = adj.get(u).size();
            for (Edge e : adj.get(u)) {
                inDegree[e.to]++;
            }
        }

        int startPlus = 0, endPlus = 0;
        int start = 0;
        for (int i = 0; i < n; i++) {
            int diff = outDegree[i] - inDegree[i];
            if (Math.abs(diff) > 1) return new boolean[]{false, false, false};
            if (diff == 1) { startPlus++; start = i; }
            else if (diff == -1) endPlus++;
        }

        boolean hasCircuit = (startPlus == 0 && endPlus == 0);
        boolean hasPath = (startPlus == 1 && endPlus == 1) || hasCircuit;
        return new boolean[]{hasCircuit, hasPath, hasPath};
    }

    /** BFS检查无向图连通性 */
    private boolean isConnected() {
        boolean[] vis = new boolean[n];
        int start = -1;
        for (int i = 0; i < n; i++) {
            if (!adj.get(i).isEmpty()) { start = i; break; }
        }
        if (start == -1) return true; // 空图

        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        vis[start] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (Edge e : adj.get(u)) {
                if (!vis[e.to]) { vis[e.to] = true; q.add(e.to); }
            }
        }
        for (int i = 0; i < n; i++) {
            if (!adj.get(i).isEmpty() && !vis[i]) return false;
        }
        return true;
    }

    /** BFS检查有向图弱连通性 */
    private boolean isWeaklyConnected() {
        // 构建无向版本的邻接表
        List<Set<Integer>> undirected = new ArrayList<>();
        for (int i = 0; i < n; i++) undirected.add(new HashSet<>());
        for (int u = 0; u < n; u++) {
            for (Edge e : adj.get(u)) {
                undirected.get(u).add(e.to);
                undirected.get(e.to).add(u);
            }
        }
        boolean[] vis = new boolean[n];
        int start = -1;
        for (int i = 0; i < n; i++) {
            if (!adj.get(i).isEmpty()) { start = i; break; }
        }
        if (start == -1) return true;

        Queue<Integer> q = new LinkedList<>();
        q.add(start); vis[start] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : undirected.get(u)) {
                if (!vis[v]) { vis[v] = true; q.add(v); }
            }
        }
        for (int i = 0; i < n; i++) {
            if (!adj.get(i).isEmpty() && !vis[i]) return false;
        }
        return true;
    }
}

/** 边结构 */
public class Edge {
    public int from, to;
    public int id;
    public boolean used = false;

    public Edge(int from, int to, int id) {
        this.from = from;
        this.to = to;
        this.id = id;
    }
}

二、Fleury算法——桥边优先策略

Fleury算法的核心思想是：除非别无选择，否则不走桥边。桥边（割边）是指删除后会使图不连通的边，如果提前走了桥边，可能会被困在某个连通分量中无法返回。

/**
 * Fleury算法实现
 * 时间复杂度：O(E^2)，因为每次都要判断桥边
 */
public class FleuryAlgorithm {

    /**
     * 寻找欧拉回路/通路
     * @param g 图
     * @param start 起点
     * @return 顶点访问序列，若无解返回空列表
     */
    public static List<Integer> findEulerPath(Graph g, int start) {
        // 复制图结构用于算法（因为会修改边状态）
        Graph graph = cloneGraph(g);
        List<Integer> path = new ArrayList<>();

        int current = start;
        path.add(current);

        while (true) {
            List<Edge> edges = graph.adj.get(current);
            Edge nextEdge = null;

            // 寻找非桥边
            for (Edge e : edges) {
                if (e.used) continue;
                if (!isBridge(graph, e)) {
                    nextEdge = e;
                    break;
                }
            }

            // 若没有非桥边，选择任意可用边（必须是最后一条）
            if (nextEdge == null) {
                for (Edge e : edges) {
                    if (!e.used) {
                        nextEdge = e;
                        break;
                    }
                }
            }

            // 无可用边，算法结束
            if (nextEdge == null) break;

            // 标记边为已使用
            nextEdge.used = true;
            // 无向图需标记反向边
            if (!graph.directed) {
                for (Edge rev : graph.adj.get(nextEdge.to)) {
                    if (rev.to == current && rev.id == nextEdge.id) {
                        rev.used = true;
                        break;
                    }
                }
            }

            current = nextEdge.to;
            path.add(current);
        }

        // 校验是否用完所有边
        int usedCount = 0;
        for (List<Edge> list : graph.adj) {
            for (Edge e : list) if (e.used) usedCount++;
        }
        int totalEdges = graph.directed ? graph.edgeCount() : graph.edgeCount() * 2;
        if (usedCount != totalEdges) {
            return new ArrayList<>(); // 无解
        }
        return path;
    }

    /** 判断边是否为桥边（Tarjan思想简化版） */
    private static boolean isBridge(Graph g, Edge edge) {
        if (edge.used) return false;

        // 若该顶点的可用边仅有一条，则必走
        int available = 0;
        for (Edge e : g.adj.get(edge.from)) {
            if (!e.used) available++;
        }
        if (available == 1) return false;

        // DFS检查删除该边后是否仍然连通
        boolean[] vis = new boolean[g.n];
        // 临时标记该边和反向边为已用
        edge.used = true;
        Edge reverse = null;
        if (!g.directed) {
            for (Edge e : g.adj.get(edge.to)) {
                if (e.to == edge.from && e.id == edge.id) {
                    reverse = e;
                    e.used = true;
                    break;
                }
            }
        }

        // 从edge.from出发DFS看能否到达edge.to
        boolean reachable = dfsReachable(g, edge.from, edge.to, vis);

        // 恢复边状态
        edge.used = false;
        if (reverse != null) reverse.used = false;

        // 若不可达，则是桥边
        return !reachable;
    }

    private static boolean dfsReachable(Graph g, int u, int target, boolean[] vis) {
        if (u == target) return true;
        vis[u] = true;
        for (Edge e : g.adj.get(u)) {
            if (!e.used && !vis[e.to]) {
                if (dfsReachable(g, e.to, target, vis)) return true;
            }
        }
        return false;
    }

    /** 深拷贝图（仅复制边结构） */
    private static Graph cloneGraph(Graph g) {
        Graph ng = new Graph(g.n, g.directed);
        // 通过重新添加边来复制
        Set<String> added = new HashSet<>();
        for (int u = 0; u < g.n; u++) {
            for (Edge e : g.adj.get(u)) {
                String key = Math.min(e.from, e.to) + "-" + Math.max(e.from, e.to) + "-" + e.id;
                if (!g.directed && added.contains(key)) continue;
                added.add(key);
                ng.addEdge(e.from, e.to);
            }
        }
        return ng;
    }
}

三、Hierholzer算法——栈与回退策略

Hierholzer算法效率更高，核心思想是：沿着未访问的边随意走，直到无法前进时回溯，将回溯路径拼接。该算法时间复杂度为 O(E)，是求解欧拉回路的工业标准方法。

/**
 * Hierholzer算法实现
 * 时间复杂度：O(E)，空间复杂度：O(V + E)
 */
public class HierholzerAlgorithm {

    /**
     * 寻找欧拉回路/通路（Hierholzer算法）
     */
    public static List<Integer> findEulerPath(Graph g, int start) {
        Graph graph = cloneGraph(g);
        Stack<Integer> stack = new Stack<>();
        List<Integer> path = new ArrayList<>();

        stack.push(start);

        while (!stack.isEmpty()) {
            int u = stack.peek();
            boolean hasUnusedEdge = false;

            // 找到一条未使用的出边
            for (Edge e : graph.adj.get(u)) {
                if (!e.used) {
                    e.used = true;
                    // 无向图标记反向边
                    if (!graph.directed) {
                        for (Edge rev : graph.adj.get(e.to)) {
                            if (rev.to == u && rev.id == e.id) {
                                rev.used = true;
                                break;
                            }
                        }
                    }
                    stack.push(e.to);
                    hasUnusedEdge = true;
                    break;
                }
            }

            // 若没有未使用的出边，回退并记录路径
            if (!hasUnusedEdge) {
                path.add(stack.pop());
            }
        }

        // path是逆序的，需要反转
        Collections.reverse(path);

        // 校验
        int usedCount = 0;
        for (List<Edge> list : graph.adj) {
            for (Edge e : list) if (e.used) usedCount++;
        }
        int totalEdges = graph.directed ? graph.edgeCount() : graph.edgeCount() * 2;
        if (usedCount != totalEdges) {
            return new ArrayList<>();
        }
        return path;
    }

    /** 迭代版：避免递归栈溢出，适合大规模图 */
    public static List<Integer> findEulerPathIterative(Graph g, int start) {
        Graph graph = cloneGraph(g);
        List<Integer> circuit = new ArrayList<>();

        // 为每个顶点维护当前遍历到的边索引
        int[] edgePtr = new int[graph.n];

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int u = stack.peek();
            if (edgePtr[u] < graph.adj.get(u).size()) {
                Edge e = graph.adj.get(u).get(edgePtr[u]++);
                if (e.used) continue;

                e.used = true;
                if (!graph.directed) {
                    for (Edge rev : graph.adj.get(e.to)) {
                        if (rev.to == u && rev.id == e.id) {
                            rev.used = true;
                            break;
                        }
                    }
                }
                stack.push(e.to);
            } else {
                circuit.add(stack.pop());
            }
        }

        Collections.reverse(circuit);
        return circuit;
    }

    private static Graph cloneGraph(Graph g) {
        Graph ng = new Graph(g.n, g.directed);
        Set<String> added = new HashSet<>();
        for (int u = 0; u < g.n; u++) {
            for (Edge e : g.adj.get(u)) {
                String key = Math.min(e.from, e.to) + "-" + Math.max(e.from, e.to) + "-" + e.id;
                if (!g.directed && added.contains(key)) continue;
                added.add(key);
                ng.addEdge(e.from, e.to);
            }
        }
        return ng;
    }
}

四、完整测试与演示

public class EulerPathDemo {
    public static void main(String[] args) {
        // 示例1：经典的无向图欧拉回路（七桥问题变体）
        System.out.println("=== 无向图欧拉回路 ===");
        Graph g1 = new Graph(5, false);
        g1.addEdge(0, 1);
        g1.addEdge(0, 2);
        g1.addEdge(1, 2);
        g1.addEdge(1, 3);
        g1.addEdge(2, 3);
        g1.addEdge(2, 4);
        g1.addEdge(3, 4);

        boolean[] check = g1.checkEuler();
        System.out.println("Has Euler Circuit: " + check[0]);
        System.out.println("Has Euler Path: " + check[1]);

        if (check[1]) {
            List<Integer> fleury = FleuryAlgorithm.findEulerPath(g1, 0);
            System.out.println("Fleury Path: " + fleury);

            List<Integer> hierholzer = HierholzerAlgorithm.findEulerPath(g1, 0);
            System.out.println("Hierholzer Path: " + hierholzer);
        }

        // 示例2：有向图欧拉回路
        System.out.println("\n=== 有向图欧拉回路 ===");
        Graph g2 = new Graph(4, true);
        g2.addEdge(0, 1);
        g2.addEdge(1, 2);
        g2.addEdge(2, 3);
        g2.addEdge(3, 0);
        g2.addEdge(0, 2);
        g2.addEdge(2, 0);

        boolean[] check2 = g2.checkEuler();
        System.out.println("Has Euler Circuit: " + check2[0]);
        if (check2[0]) {
            List<Integer> path = HierholzerAlgorithm.findEulerPath(g2, 0);
            System.out.println("Hierholzer Path: " + path);
        }

        // 示例3：大规模图性能测试
        System.out.println("\n=== 性能测试 ===");
        int n = 10000;
        Graph big = new Graph(n, false);
        Random rand = new Random(42);
        for (int i = 0; i < n; i++) {
            big.addEdge(i, (i + 1) % n);
            big.addEdge(i, (i + 2) % n);
        }

        long t1 = System.currentTimeMillis();
        List<Integer> p1 = HierholzerAlgorithm.findEulerPath(big, 0);
        System.out.println("Hierholzer on " + n + " nodes: " + (System.currentTimeMillis() - t1) + "ms, path length=" + p1.size());
    }
}

五、算法对比与复杂度分析

桥边判断优化：若使用Tarjan算法预处理桥边，可将Fleury优化至 O(E)，但代码复杂度显著增加，不如直接使用Hierholzer算法。

六、实际应用场景

• 路线规划：邮递员问题（中国邮路问题）的基础子问题
• DNA序列拼接：De Bruijn图中寻找欧拉通路进行基因组组装
• 电路板钻孔：优化钻孔路径，使钻头移动距离最短
• 密码学：De Bruijn序列生成基于欧拉回路

七、总结

本文完整实现了欧拉回路的判定与求解算法：

• 欧拉定理判定：基于顶点度数的奇偶性/出入度差，快速判定解的存在性
• Fleury算法：以”不走桥边”为核心策略，直观但效率较低
• Hierholzer算法：利用栈的回退机制，线性时间高效求解，是工业首选

两种算法各有适用场景：Fleury适合教学理解，Hierholzer适合实际工程部署。