用 Hierholzer 算法求解欧拉回路

欧拉回路是图论中的一个经典概念，其核心在于寻找一条路径，使得该路径遍历图中的每一条边且仅遍历一次，并最终回到起点。作为图论入门的第一个问题，我们已经对欧拉回路的两个基本判定条件很了解了：

1. 偶数度顶点条件：图中每个顶点的度数（即连接到该顶点的边的数量）必须为偶数。这是因为路径进入一个顶点时必须能够离开该顶点，度数为奇数将导致路径在该顶点被中断。
2. 连通性条件：对于无向图，从任意一点出发，能够遍历到图中所有的边。这保证了路径的完整性。

这两个条件的正确性可以从路径的构造性质来理解。偶数度顶点条件确保路径不会在中途终止，而连通性条件保证路径能覆盖图中的所有边而不遗漏。

Hierholzer算法求解具体路径

在满足欧拉回路条件的前提下，如何有效地求解一条具体欧拉回路？Hierholzer算法是一种经典且高效的解决方法。它的基本思想是从一个顶点出发，逐步扩展路径，直到回到起点形成一个闭合路径；随后检查是否有未访问的边，并通过将新路径嵌入已有路径的方式最终构造完整的欧拉回路。

1. 选择起点：从图中任意一个顶点开始作为起点。
2. 构造初始路径：从当前顶点出发，沿着未访问过的边前进，并标记这些边为已访问，直到回到起点，形成一个闭合路径。
3. 处理剩余边：如果闭合路径中存在顶点尚有未访问的边，从该顶点重新出发，构造新的闭合路径，并将其嵌入原始路径中。
4. 完成路径：重复上述步骤，直到所有边都被访问过。

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
#include <list>
using namespace std;

void findEulerianCircuit(unordered_map<int, list<int>>& graph, vector<int>& circuit) {
    stack<int> currentPath;  // 用于存储当前路径
    vector<int> tempCircuit;  // 用于存储最终的欧拉回路

    int currentNode = graph.begin()->first;  // 任意选择起点
    currentPath.push(currentNode);

    while (!currentPath.empty()) {
        if (!graph[currentNode].empty()) {
            currentPath.push(currentNode);
            int nextNode = graph[currentNode].front();
            graph[currentNode].pop_front();
            graph[nextNode].remove(currentNode);  // 移除双向边
            currentNode = nextNode;
        } else {
            tempCircuit.push_back(currentNode);
            currentNode = currentPath.top();
            currentPath.pop();
        }
    }

    circuit.assign(tempCircuit.rbegin(), tempCircuit.rend());  // 反转路径得到最终结果
}

int main() {
    // 示例图的邻接表表示
    unordered_map<int, list<int>> graph = {
        {0, {1, 2}},
        {1, {0, 2}},
        {2, {0, 1, 3}},
        {3, {2}}
    };

    vector<int> circuit;
    findEulerianCircuit(graph, circuit);

    if (!circuit.empty()) {
        cout << "Eulerian Circuit: ";
        for (int node : circuit) {
            cout << node << " ";
        }
        cout << endl;
    } else {
        cout << "No Eulerian Circuit exists." << endl;
    }

    return 0;
}

算法正确性

Hierholzer算法的正确性来源于以下几点：

1. 局部闭合路径构造：算法保证每次从一个顶点出发，形成的路径是闭合的，即回到起点后不遗漏任何已走过的边。
2. 全局路径合并：新路径嵌入已有路径时不会破坏路径的连续性，因为路径的合并总是在共享顶点处完成。
3. 边的完全覆盖：由于每条边在第一次访问时被标记为已访问，算法最终能够覆盖所有边，形成完整的欧拉回路。

可以简单理解，只要满足欧拉回路的条件，我们就不停的往前，有边就走，一定可以走出回路。

时间复杂度

Hierholzer算法的时间复杂度为 \(O(E)\)，其中 \(E\) 是图中的边数。原因是每条边仅被访问两次（一次从起点出发，一次从终点回到起点），效率很高。