C++给出代码示例

### C++ 中 Hierholzer 算法的代码示例 Hierholzer 算法是一种高效的算法，用于在连通图中寻找欧拉路径或欧拉回路。下面是一个完整的 C++ 实现示例，展示了如何构建邻接表、使用栈记录路径，并通过深度优先搜索（DFS）完成欧拉路径的查找。 ```cpp #include <iostream> #include <vector> #include <stack> using namespace std; // 定义最大节点数量和边的数量 const int MAX_N = 10010; int head[MAX_N], cnt_edge = 0; struct Edge { int to, next; } edges[MAX_N * 2]; void add_edge(int from, int to) { edges[++cnt_edge] = {to, head[from]}; head[from] = cnt_edge; } vector<int> euler_path(int start, int n) { vector<int> result; stack<int> stk; stk.push(start); while (!stk.empty()) { int u = stk.top(); if (head[u] != -1) { // 存在未访问的边 int idx = head[u]; head[u] = edges[idx].next; // 更新头指针 stk.push(edges[idx].to); // 将目标节点压入栈中 } else { result.push_back(u); stk.pop(); // 没有更多边时弹出当前节点 } } reverse(result.begin(), result.end()); return result; } bool check_eulerian(int n) { int odd_degree_count = 0, start_node = -1; for (int i = 1; i <= n; ++i) { int degree = 0; for (int j = head[i]; j != -1; j = edges[j].next) { degree++; } if (degree % 2 != 0) { odd_degree_count++; start_node = i; } } if (odd_degree_count == 0 || odd_degree_count == 2) { return true; } return false; } int main() { int n, m; cin >> n >> m; // 输入节点数n 和 边数m memset(head, -1, sizeof(head)); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; add_edge(u, v); } if (!check_eulerian(n)) { cout << "-1"; // 图不满足欧拉路径/回路条件 return 0; } int start = 1; for (int i = 1; i <= n; ++i) { if (head[i] != -1) { start = i; // 找到第一个有效节点作为起点 break; } } vector<int> path = euler_path(start, n); if ((int)path.size() != m + 1) { cout << "-1"; // 路径长度不符合预期 } else { for (auto &node : path) { cout << node << " "; } } return 0; } ``` --- ### 关键点解析 - **邻接表存储结构**：为了高效地表示图的数据结构，采用链式前向星方式存储边的信息[^1]。 - **深度优先搜索（DFS）**：通过栈模拟 DFS 过程，每次从当前节点出发尝试访问所有与其相连的未访问过的边。 - **欧拉路径验证**：在执行主逻辑之前先检查图是否具有合法的欧拉路径或欧拉回路。这一步骤可以通过统计每个节点的度数来完成[^1]。 - **结果反转**：由于栈的工作机制，最终的结果需要进行一次翻转才能获得正确的顺序[^3]。 --- ###