每日算法 — 使用java实现欧拉路径：Hierholzer算法与一笔画判定

欧拉路径问题源于著名的柯尼斯堡七桥问题，是图论中最经典的问题之一。给定一个图，判断是否存在一条经过每条边恰好一次的路径（欧拉路径），或者一条经过每条边恰好一次并回到起点的回路（欧拉回路）。该问题在路径规划、电路板布线、DNA序列组装、游戏关卡设计等领域有广泛应用。

问题定义

• 欧拉回路：从某节点出发，经过图中每条边恰好一次，最终回到起点的闭合路径
• 欧拉路径：从某节点出发，经过图中每条边恰好一次的路径（不要求回到起点）

存在性判定定理

无向图：
– 欧拉回路：所有顶点度数为偶数，且图连通
– 欧拉路径：恰好有0个或2个顶点度数为奇数，且图连通

有向图：
– 欧拉回路：所有顶点入度等于出度，且图连通
– 欧拉路径：恰好一个顶点出度 = 入度 + 1（起点），一个顶点入度 = 出度 + 1（终点），其余入度等于出度

方法一：Hierholzer算法（O(V + E)）

核心思路

Hierholzer算法的核心思想是：从起点出发，沿着未访问的边随意走，直到无法继续前进。此时如果还有未访问的边，说明当前路径上存在”环”可以扩展。回溯到路径上第一个还有未访问边的节点，从该点继续探索，将新路径插入到原路径中。

Java实现（无向图）

import java.util.*;

public class EulerPathUndirected {

    private int n;
    private List<int[]>[] graph; // 存储[邻接点, 边编号]
    private boolean[] used; // 边是否被访问
    private int edgeCount;

    @SuppressWarnings("unchecked")
    public EulerPathUndirected(int n, int m) {
        this.n = n;
        this.graph = new ArrayList[n];
        this.used = new boolean[m];
        this.edgeCount = 0;

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    /**
     * 添加无向边
     */
    public void addEdge(int u, int v) {
        graph[u].add(new int[]{v, edgeCount});
        graph[v].add(new int[]{u, edgeCount});
        edgeCount++;
    }

    /**
     * 判断是否存在欧拉路径/回路
     * @return [是否存在, 起点]
     */
    public Object[] checkExistence() {
        int oddDegreeCount = 0;
        int start = 0;

        for (int i = 0; i < n; i++) {
            if (graph[i].size() % 2 == 1) {
                oddDegreeCount++;
                start = i; // 记录奇度顶点作为起点
            }
        }

        // 0个奇度顶点：欧拉回路；2个奇度顶点：欧拉路径
        boolean exists = (oddDegreeCount == 0 || oddDegreeCount == 2);
        if (oddDegreeCount == 0) {
            // 找第一个有边的节点作为起点
            for (int i = 0; i < n; i++) {
                if (!graph[i].isEmpty()) {
                    start = i;
                    break;
                }
            }
        }

        return new Object[]{exists, start};
    }

    /**
     * Hierholzer算法求欧拉路径
     * @return 欧拉路径的节点序列，如果不存在则返回空列表
     */
    public List<Integer> findEulerPath() {
        Object[] check = checkExistence();
        boolean exists = (Boolean) check[0];
        int start = (Integer) check[1];

        if (!exists) {
            return new ArrayList<>();
        }

        List<Integer> path = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

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

            // 找一条未使用的边
            for (int i = 0; i < graph[u].size(); i++) {
                int[] edge = graph[u].get(i);
                int v = edge[0];
                int eid = edge[1];

                if (!used[eid]) {
                    used[eid] = true;
                    stack.push(v);
                    found = true;
                    break;
                }
            }

            if (!found) {
                // 没有未使用的边，将节点加入路径
                path.add(stack.pop());
            }
        }

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

    public static void main(String[] args) {
        // 构建示例图（柯尼斯堡七桥问题的简化版）
        // 0 -- 1 -- 2
        // |    |    |
        // 3 -- 4 -- 5

        EulerPathUndirected euler = new EulerPathUndirected(6, 7);
        euler.addEdge(0, 1);
        euler.addEdge(1, 2);
        euler.addEdge(0, 3);
        euler.addEdge(1, 4);
        euler.addEdge(2, 5);
        euler.addEdge(3, 4);
        euler.addEdge(4, 5);

        List<Integer> path = euler.findEulerPath();
        System.out.println("欧拉路径: " + path);
        System.out.println("路径长度（边数）: " + (path.size() - 1));
    }
}

方法二：有向图欧拉路径

Java实现

import java.util.*;

public class EulerPathDirected {

    private int n;
    private List<Integer>[] graph; // 邻接表
    private int[] inDegree;
    private int[] outDegree;

    @SuppressWarnings("unchecked")
    public EulerPathDirected(int n) {
        this.n = n;
        this.graph = new ArrayList[n];
        this.inDegree = new int[n];
        this.outDegree = new int[n];

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    public void addEdge(int from, int to) {
        graph[from].add(to);
        outDegree[from]++;
        inDegree[to]++;
    }

    /**
     * 判断是否存在欧拉路径/回路
     * @return [是否存在, 起点]
     */
    public Object[] checkExistence() {
        int startNodes = 0; // 出度 = 入度 + 1
        int endNodes = 0;   // 入度 = 出度 + 1
        int start = 0;

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

        boolean exists = (startNodes == 0 && endNodes == 0) || 
                         (startNodes == 1 && endNodes == 1);

        if (startNodes == 0) {
            // 欧拉回路，找第一个有出边的节点
            for (int i = 0; i < n; i++) {
                if (outDegree[i] > 0) {
                    start = i;
                    break;
                }
            }
        }

        return new Object[]{exists, start};
    }

    /**
     * Hierholzer算法求有向图欧拉路径
     */
    public List<Integer> findEulerPath() {
        Object[] check = checkExistence();
        boolean exists = (Boolean) check[0];
        int start = (Integer) check[1];

        if (!exists) {
            return new ArrayList<>();
        }

        // 复制邻接表用于删除边
        List<Integer>[] tempGraph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            tempGraph[i] = new ArrayList<>(graph[i]);
        }

        List<Integer> path = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

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

            if (!tempGraph[u].isEmpty()) {
                // 还有未访问的边，继续走
                int v = tempGraph[u].remove(tempGraph[u].size() - 1);
                stack.push(v);
            } else {
                // 没有未访问的边，加入路径
                path.add(stack.pop());
            }
        }

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        // 构建有向图示例
        // 0 -> 1 -> 2 -> 0
        // 1 -> 3 -> 1

        EulerPathDirected euler = new EulerPathDirected(4);
        euler.addEdge(0, 1);
        euler.addEdge(1, 2);
        euler.addEdge(2, 0);
        euler.addEdge(1, 3);
        euler.addEdge(3, 1);

        List<Integer> path = euler.findEulerPath();
        System.out.println("有向图欧拉路径: " + path);
    }
}

方法三：字典序最小欧拉路径

当图中存在多个欧拉路径时，有时需要输出字典序最小的路径。通过将邻接表排序，并在Hierholzer算法中优先选择编号较小的邻居，可以实现这一目标。

Java实现

import java.util.*;

public class EulerPathLexicographically {

    private int n;
    private PriorityQueue<Integer>[] graph; // 用小根堆维护邻接点

    @SuppressWarnings("unchecked")
    public EulerPathLexicographically(int n) {
        this.n = n;
        this.graph = new PriorityQueue[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new PriorityQueue<>();
        }
    }

    public void addEdge(int u, int v) {
        graph[u].offer(v);
    }

    /**
     * 求字典序最小的欧拉路径（有向图）
     */
    public List<Integer> findLexicographicallySmallest(int start) {
        List<Integer> path = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int u = stack.peek();
            if (!graph[u].isEmpty()) {
                int v = graph[u].poll();
                stack.push(v);
            } else {
                path.add(stack.pop());
            }
        }

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        EulerPathLexicographically euler = new EulerPathLexicographically(5);
        euler.addEdge(0, 1);
        euler.addEdge(0, 2);
        euler.addEdge(1, 3);
        euler.addEdge(2, 3);
        euler.addEdge(3, 0);
        euler.addEdge(3, 4);
        euler.addEdge(4, 3);

        List<Integer> path = euler.findLexicographicallySmallest(0);
        System.out.println("字典序最小欧拉路径: " + path);
    }
}

复杂度分析

实际应用场景

1. DNA序列组装：将片段重叠图分解为欧拉路径，重建完整序列
2. 电路板布线：寻找经过所有连接点的最优路径
3. 邮递员问题：中国邮路问题的基础，寻找经过所有街道的最短路径
4. 游戏关卡设计：设计遍历所有区域的最优路线
5. 路线规划：规划经过所有景点的最短游览路线

变种问题

半欧拉路径（非欧拉但接近）

当图不存在欧拉路径时，可以通过添加最少的边或重复经过某些边来实现遍历。这引申出中国邮路问题，可用最小权匹配求解。

public class ChinesePostman {

    /**
     * 中国邮路问题：求经过每条边至少一次的最短路径
     * 核心思想：对奇度顶点求最小权完美匹配
     */
    public int chinesePostman(int n, int[][] edges) {
        // 实现略，核心步骤：
        // 1. 找出所有奇度顶点
        // 2. 计算奇度顶点之间的最短路径（Floyd或Dijkstra）
        // 3. 对奇度顶点求最小权完美匹配
        // 4. 原图总权值 + 匹配增加的权值
        return 0;
    }
}

总结

欧拉路径问题是图论的经典入门，Hierholzer算法以线性时间优雅地解决了路径构造问题。理解欧拉路径的存在性判定和构造方法，不仅是算法竞赛的基础，也是解决实际网络遍历、路径规划问题的有力工具。从柯尼斯堡七桥到现代DNA测序，欧拉路径的思想跨越三百多年依然闪耀。