当前位置: 首页 > article >正文

《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(47)乾坤图演路径 - 欧拉路径(Hierholzer 算法)

《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(47)乾坤图演路径 - 欧拉路径(Hierholzer 算法)

哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的乾坤图林,林中有一幅巨大的乾坤图,图中路径错综复杂。图的入口处有一块巨大的石碑,上面刻着一行文字:“欲破此图,需以乾坤图之力,演路径,欧拉路径显真身。”

哪吒定睛一看,石碑上还有一行小字:“图的邻接表表示为[ (0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) ],欧拉路径为0 -> 1 -> 2 -> 3 -> 4。”哪吒心中一动,他知道这是一道关于寻找欧拉路径的难题,需要通过Hierholzer算法来解决。

暴力解法:乾坤图的初次尝试

哪吒心想:“要寻找欧拉路径,我可以尝试所有可能的路径组合。”他催动乾坤图之力,从图中的一个节点开始,逐个节点访问,试图找到一条包含所有边恰好一次的路径。

vector<int> eulerPath(vector<vector<int>>& graph) {
   
    int n = graph.size();
    vector<int> path;
    for (int i = 0; i < n; ++i) {
   
        if (graph[i].size() % 2 != 0) {
   
            // 从奇度节点开始
            return findPath(graph, i);
        }
    }
    // 如果所有节点度数都为偶数,从任意节点开始
    return findPath(graph, 0);
}

vector<int> findPath(vector<vector<int>>& graph, int start) {
   
    vector<int> path;
    stack<int> stk;
    stk.push(start);
    while (!stk.empty()) {
   
        int u = stk.top();
        if (graph[u].empty()) {
   
            path.push_back(u);
            stk.pop();
        } else {
   
            int v = graph[u].back();
            graph[u].pop_back();
            stk.push(v);
        }
    }
    reverse(path.begin(), path.end());
    return path;
}

哪吒成功地找到了欧拉路径,但乾坤图的光芒却黯淡了下来。他意识到,这种方法虽然可行,但效率低下,尤其是当图的节点数量很多时,灵力消耗巨大。

C++语法点

在C++中,Hierholzer算法涉及到图的邻接表表示和栈的操作。以下是一些重要特性:

  • 邻接表

    • 使用vector<vector<int>>表示图的邻接表。
    • 常用操作:
      • graph[u].push_back(v):添加有向边u -> v
      • graph[u].pop_back():移除最后一条边。
    • 使用stack<int>来辅助构建路径。
    • 常用操作:
      • push(u):将节点u压入栈。
      • pop():弹出栈顶元素。
      • top():获取栈顶元素。

高阶优化:Hierholzer算法的智慧

哪吒元神中突然浮现金色铭文——「乾坤图演路径,欧拉路径显真身」。他意识到,可以通过Hierholzer算法优化欧拉路径的寻找过程。


http://www.kler.cn/a/587330.html

相关文章:

  • 使用DeepSeek和墨刀AI,写PRD文档、画原型图的思路、过程及方法
  • linux系统命令——权限
  • 【图论】并查集的学习和使用
  • 背诵--2
  • 如何用Deepseek制作流程图?
  • 2025年1月-3月Java面试题、笔记、简历模版汇总(需要自取)
  • 解锁C++:指针与数组、字符串的深度探秘
  • MySQL复习(检查本地MySQL是否安装、DataGrip数据库可视化工具使用、增删改查基础语法、唯一索引、SQL简单函数)
  • 【科研绘图系列】R语言绘制网络相关图(cor network plot)
  • 11 | 给 Gin 服务器添加中间件
  • Mac下安装Zed以及Zed对MCP(模型上下文协议)的支持
  • PyQt基础——简单闹钟ui实现(图形化界面、定时器事件)
  • C#的简单工厂模式、工厂方法模式、抽象工厂模式
  • Umi-OCR 全家桶
  • C++20 `<bit>` 中的整数 2 的幂运算和 `std::bit_cast`:由浅入深的探索
  • 定制开发开源 AI 智能名片 S2B2C 商城小程序源码在小程序直播营销中的应用与价值
  • matlab 量化交易投资策略研究
  • 基于 Verilog 的 4 位二进制计数器设计与实验:从理论到实践的深度剖析
  • 数据库版本问题导致的查询bug
  • 宇数科技激光雷达L2