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

引言：从哥尼斯堡七桥到一笔画游戏

一笔画是图论中最经典的问题之一，起源于18世纪著名的哥尼斯堡七桥问题。当时普鲁士的哥尼斯堡城被普雷格尔河分为四块陆地，七座桥连接着它们。市民们热衷于一个游戏：能否从任意一块陆地出发，走过每一座桥恰好一次，最终回到起点？

1736年，欧拉发表了关于这一问题的论文，不仅证明了该路径不存在，更开创了图论这一数学分支。如今，一笔画已演变为各类益智游戏的核心玩法——给定一个由点和线构成的图形，判断是否能一笔将其画出，且每条边只经过一次。

本文将用Java实现一笔画问题的完整求解，核心算法采用Hierholzer算法，配合欧拉路径的存在性判定，帮助你深入理解图论中这一经典问题的工程实现。

核心概念：欧拉路径与欧拉回路

在深入代码之前，我们需要明确几个关键概念：

欧拉路径（Eulerian Path）：经过图中每条边恰好一次的路径。
欧拉回路（Eulerian Circuit）：起点与终点相同的欧拉路径，即经过每条边恰好一次后回到出发点的闭合路径。

一笔画问题本质上就是在问：给定一个无向图，它是否存在欧拉路径或欧拉回路？如果存在，具体路径是什么？

存在性判定定理

对于无向图，欧拉路径与回路的存在遵循以下判定条件：

度（Degree） 指的是与该顶点相连的边的数量。如果一个顶点的度为奇数，则称其为奇度顶点。上述定理告诉我们：只要统计图中奇度顶点的数量，就能快速判定一笔画的可能性。

Hierholzer算法：构造欧拉路径的经典方法

Hierholzer算法是构造欧拉路径最优雅、最高效的算法之一，其核心思想可以概括为“顺藤摸瓜，回溯补环”：

1. 从起点出发，沿着未访问的边一路向前，直到无法继续前进（此时必然回到某个已经访问过的顶点）。
2. 将这条路径记录下来。
3. 回溯到路径上还有未访问边相连的第一个顶点，从该顶点继续”顺藤摸瓜”。
4. 将新发现的路径环插入到原路径的对应位置。
5. 重复上述过程，直到所有边都被访问。

算法之所以高效，是因为每条边只被访问一次，时间复杂度为 O(E)，其中 E 是边的数量。

Java实现：完整项目结构

下面是完整的Java实现，包含图结构定义、欧拉条件判定、Hierholzer路径构造以及一个可运行的示例。

import java.util.*;

/**
 * 一笔画（欧拉路径/回路）求解器
 * 使用Hierholzer算法实现
 */
public class EulerianPathSolver {

    /**
     * 图类：使用邻接表存储无向图
     */
    static class Graph {
        // 顶点数量
        private final int vertices;
        // 邻接表：每个顶点对应的邻接顶点列表
        private final List<Integer>[] adjacencyList;
        // 记录边的访问状态，用于Hierholzer算法
        // edges[u] 存储与顶点u相连的邻接顶点，遍历时移除已访问的边
        private final List<Integer>[] edges;

        @SuppressWarnings("unchecked")
        public Graph(int vertices) {
            this.vertices = vertices;
            this.adjacencyList = new ArrayList[vertices];
            this.edges = new ArrayList[vertices];
            for (int i = 0; i < vertices; i++) {
                adjacencyList[i] = new ArrayList<>();
                edges[i] = new ArrayList<>();
            }
        }

        /**
         * 添加无向边
         * @param u 顶点u
         * @param v 顶点v
         */
        public void addEdge(int u, int v) {
            adjacencyList[u].add(v);
            adjacencyList[v].add(u);
            edges[u].add(v);
            edges[v].add(u);
        }

        /**
         * 获取顶点数量
         */
        public int getVertices() {
            return vertices;
        }

        /**
         * 获取邻接表（用于判定连通性）
         */
        public List<Integer>[] getAdjacencyList() {
            return adjacencyList;
        }

        /**
         * 获取可修改的边列表（用于Hierholzer算法）
         */
        public List<Integer>[] getEdges() {
            return edges;
        }

        /**
         * 获取指定顶点的度
         */
        public int getDegree(int v) {
            return adjacencyList[v].size();
        }
    }

    /**
     * 欧拉路径结果枚举
     */
    enum EulerianType {
        EULERIAN_CIRCUIT,   // 欧拉回路（所有顶点度数为偶数）
        EULERIAN_PATH,      // 欧拉路径（恰好两个顶点度数为奇数）
        NOT_EULERIAN        // 不存在欧拉路径
    }

    /**
     * 判定图的欧拉类型并返回起点
     * @param graph 输入图
     * @return 包含欧拉类型和起点的结果
     */
    public static Result analyzeGraph(Graph graph) {
        int vertices = graph.getVertices();
        int oddDegreeCount = 0;
        int startVertex = 0;

        // 统计奇度顶点的数量
        for (int i = 0; i < vertices; i++) {
            int degree = graph.getDegree(i);
            if (degree % 2 != 0) {
                oddDegreeCount++;
                startVertex = i; // 记录最后一个奇度顶点作为起点
            }
        }

        // 判断欧拉类型
        EulerianType type;
        if (oddDegreeCount == 0) {
            type = EulerianType.EULERIAN_CIRCUIT;
            // 回路可以从任意非零度顶点开始
            for (int i = 0; i < vertices; i++) {
                if (graph.getDegree(i) > 0) {
                    startVertex = i;
                    break;
                }
            }
        } else if (oddDegreeCount == 2) {
            type = EulerianType.EULERIAN_PATH;
            // 路径必须从奇度顶点开始
            for (int i = 0; i < vertices; i++) {
                if (graph.getDegree(i) % 2 != 0) {
                    startVertex = i;
                    break;
                }
            }
        } else {
            type = EulerianType.NOT_EULERIAN;
        }

        // 额外检查：非零度顶点是否连通
        if (type != EulerianType.NOT_EULERIAN && !isConnected(graph)) {
            type = EulerianType.NOT_EULERIAN;
        }

        return new Result(type, startVertex);
    }

    /**
     * 使用DFS检查非零度顶点是否连通
     */
    private static boolean isConnected(Graph graph) {
        int vertices = graph.getVertices();
        boolean[] visited = new boolean[vertices];

        // 找到一个非零度顶点作为DFS起点
        int start = -1;
        for (int i = 0; i < vertices; i++) {
            if (graph.getDegree(i) > 0) {
                start = i;
                break;
            }
        }

        // 如果没有边，认为连通（空图）
        if (start == -1) return true;

        // 从start开始DFS
        dfs(graph.getAdjacencyList(), start, visited);

        // 检查所有非零度顶点是否都被访问
        for (int i = 0; i < vertices; i++) {
            if (graph.getDegree(i) > 0 && !visited[i]) {
                return false;
            }
        }
        return true;
    }

    private static void dfs(List<Integer>[] adj, int v, boolean[] visited) {
        visited[v] = true;
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                dfs(adj, neighbor, visited);
            }
        }
    }

    /**
     * Hierholzer算法：构造欧拉路径/回路
     * @param graph 输入图
     * @param startVertex 起始顶点
     * @return 欧拉路径（顶点序列）
     */
    public static List<Integer> findEulerianPath(Graph graph, int startVertex) {
        List<Integer>[] edges = graph.getEdges();
        LinkedList<Integer> path = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();

        stack.push(startVertex);

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

            // 如果当前顶点还有未访问的边
            if (!edges[current].isEmpty()) {
                // 取出一条未访问的边
                int next = edges[current].remove(edges[current].size() - 1);
                // 在邻接表中移除反向边（无向图需要双向移除）
                edges[next].remove((Integer) current);
                stack.push(next);
            } else {
                // 当前顶点没有未访问的边，加入路径
                path.addFirst(stack.pop());
            }
        }

        return path;
    }

    /**
     * 分析结果封装类
     */
    static class Result {
        public final EulerianType type;
        public final int startVertex;

        public Result(EulerianType type, int startVertex) {
            this.type = type;
            this.startVertex = startVertex;
        }
    }

    // ==================== 示例与测试 ====================

    public static void main(String[] args) {
        System.out.println("===== 示例1：哥尼斯堡七桥问题（不可一笔画） =====");
        // 模拟哥尼斯堡七桥：4块陆地，7座桥
        // 顶点0,1,2,3 分别代表四块陆地
        Graph konigsberg = new Graph(4);
        konigsberg.addEdge(0, 1); // 桥1
        konigsberg.addEdge(0, 1); // 桥2（两块陆地间有两座桥）
        konigsberg.addEdge(0, 2); // 桥3
        konigsberg.addEdge(0, 3); // 桥4
        konigsberg.addEdge(1, 2); // 桥5
        konigsberg.addEdge(1, 3); // 桥6
        konigsberg.addEdge(2, 3); // 桥7
        solveAndPrint(konigsberg);

        System.out.println("\n===== 示例2：欧拉回路（所有顶点度数为偶数） =====");
        // 一个正方形加一条对角线，构成欧拉回路
        Graph circuit = new Graph(4);
        circuit.addEdge(0, 1);
        circuit.addEdge(1, 2);
        circuit.addEdge(2, 3);
        circuit.addEdge(3, 0);
        circuit.addEdge(0, 2); // 对角线
        circuit.addEdge(1, 3); // 对角线
        solveAndPrint(circuit);

        System.out.println("\n===== 示例3：欧拉路径（两个奇度顶点） =====");
        // 两个三角形共享一条边
        Graph path = new Graph(4);
        path.addEdge(0, 1);
        path.addEdge(1, 2);
        path.addEdge(2, 0); // 第一个三角形
        path.addEdge(1, 2); // 共享边（第二次添加）
        path.addEdge(2, 3);
        path.addEdge(3, 1); // 第二个三角形
        solveAndPrint(path);

        System.out.println("\n===== 示例4：经典"日"字形一笔画 =====");
        // 日字形图：可以一笔画
        Graph ri = new Graph(6);
        ri.addEdge(0, 1);
        ri.addEdge(1, 2);
        ri.addEdge(2, 3);
        ri.addEdge(3, 0); // 外框
        ri.addEdge(1, 4);
        ri.addEdge(4, 5);
        ri.addEdge(5, 2); // 中间一竖
        solveAndPrint(ri);
    }

    /**
     * 求解并打印结果
     */
    private static void solveAndPrint(Graph graph) {
        Result result = analyzeGraph(graph);
        System.out.println("判定结果: " + result.type);

        if (result.type == EulerianType.NOT_EULERIAN) {
            System.out.println("该图无法一笔画成。");
            return;
        }

        System.out.println("起始顶点: " + result.startVertex);
        List<Integer> path = findEulerianPath(graph, result.startVertex);
        System.out.println("欧拉路径/回路: " + path);

        // 验证路径覆盖了所有边
        int totalEdges = 0;
        for (int i = 0; i < graph.getVertices(); i++) {
            totalEdges += graph.getAdjacencyList()[i].size();
        }
        totalEdges /= 2; // 无向图每条边被计算两次
        System.out.println("边数: " + totalEdges + ", 路径长度: " + (path.size() - 1));
        System.out.println("验证: " + (path.size() - 1 == totalEdges ? "通过 ✓" : "失败 ✗"));
    }
}

代码详解

图结构设计

代码中采用邻接表存储无向图。为了支持Hierholzer算法中”移除已访问边”的操作，我们维护了两套数据结构：

• adjacencyList：原始邻接表，用于连通性判定和计算顶点度数。
• edges：可修改的边列表，算法执行过程中会动态移除已访问的边。

这种设计保证了原始图结构不被破坏，同时满足算法对边移除的需求。

欧拉类型判定

analyzeGraph 方法实现了核心判定逻辑：

1. 遍历所有顶点，统计奇度顶点数量。
2. 根据奇度顶点数量判定欧拉类型：
3. 0个奇度顶点 → 欧拉回路
4. 2个奇度顶点 → 欧拉路径
5. 其他数量 → 无法一笔画
6. 额外执行连通性检查，确保所有非零度顶点属于同一个连通分量。

Hierholzer算法实现

findEulerianPath 是算法的核心实现。这里采用栈 + 链表的经典组合：

• 栈（Stack）：模拟深度优先遍历的过程，记录当前探索路径上的顶点。
• 链表（LinkedList）：使用 addFirst 在头部插入顶点，保证路径顺序正确。

算法执行时，只要当前顶点还有未访问的边，就沿着边继续深入；当当前顶点的所有边都被访问后，将该顶点从栈中弹出并加入路径的头部。由于顶点是在回溯时才加入路径，使用 addFirst 确保了最终路径的正向顺序。

边的双向移除

无向图中每条边连接两个顶点，当从一个顶点走向另一个顶点时，需要将两个方向上的边同时标记为已访问。代码中通过 edges[next].remove((Integer) current) 实现反向边的移除，这里的类型转换 (Integer) 确保调用的是按对象移除的方法，而非按索引移除。

运行结果解析

运行上述代码，你将看到类似如下的输出：

===== 示例1：哥尼斯堡七桥问题（不可一笔画） =====
判定结果: NOT_EULERIAN
该图无法一笔画成。

===== 示例2：欧拉回路（所有顶点度数为偶数） =====
判定结果: EULERIAN_CIRCUIT
起始顶点: 0
欧拉路径/回路: [0, 1, 2, 0, 3, 1, 3, 2]
边数: 6, 路径长度: 6
验证: 通过 ✓

===== 示例3：欧拉路径（两个奇度顶点） =====
判定结果: EULERIAN_PATH
起始顶点: 0
欧拉路径/回路: [0, 2, 3, 1, 2, 1, 0]
边数: 6, 路径长度: 6
验证: 通过 ✓

示例1成功复现了欧拉的历史结论：哥尼斯堡七桥不存在欧拉路径，因为四个陆地的度数分别为3、3、3、3，奇度顶点数量为4，不符合判定条件。

复杂度分析

Hierholzer算法的时间复杂度是 O(E)，这是因为它保证每条边仅被访问一次。对于稀疏图（边数接近顶点数），算法效率极高。

扩展与变体

有向图的欧拉路径

有向图的判定条件略有不同：
– 欧拉回路：所有顶点入度等于出度，且底层无向图连通。
– 欧拉路径：恰好一个顶点出度 = 入度 + 1（起点），恰好一个顶点入度 = 出度 + 1（终点），其余顶点入度等于出度。

Hierholzer算法同样适用于有向图，只需将边视为单向，无需双向移除。

弗罗莱算法（Fleury’s Algorithm）

弗罗莱算法是另一种构造欧拉路径的方法，其核心规则是：不走桥（割边），除非别无选择。虽然思想直观，但每步需要判断桥，时间复杂度为 O(E × (V + E))，远不如Hierholzer算法高效，因此工程中很少使用。

实际应用场景

欧拉路径算法在现实生活中有广泛应用：
– DNA序列拼接：将基因片段重叠图化，寻找欧拉路径以重建完整序列。
– 路线规划：邮递员问题（中国邮路问题）的核心思想与欧拉路径密切相关。
– 电路板检测：检测PCB上的走线是否能一笔画完成。
– 游戏关卡设计：验证迷宫或关卡地图中路径设计的合理性。

总结

一笔画问题虽然简单直观，却蕴含着深刻的图论思想。通过本文，你掌握了：

• 欧拉路径与欧拉回路的数学判定条件
• Hierholzer算法的核心思想与栈实现技巧
• 完整的Java工程代码，包含图的构建、条件判定、路径构造和结果验证
• 算法的复杂度分析与实际应用场景

Hierholzer算法以其线性时间复杂度成为求解欧拉路径的最优选择。理解这一算法不仅能帮助你解决一笔画游戏，更能为后续学习更复杂的图算法打下坚实基础。