美文网首页
332. Reconstruct Itinerary

332. Reconstruct Itinerary

作者: xxxcoder | 来源:发表于2020-05-24 20:53 被阅读0次

key tips

属于欧拉路径问题

欧拉路径问题

  • 欧拉回路：
    遍历图中所有的边，每条边只遍一次，并且回到开始节点
  • 欧拉路径
    遍历图中所有的边，每条边只遍历一次

存在性充要条件

  • 无向图：
    欧拉路径：所有节点度数为偶数，有0/2个节点度数为奇数
    欧拉回路：所有节点度数为偶数

  • 有向图
    欧拉路径：所有节点出度等于入度，有一个节点入度比出度大1，有一个节点入度比出度小1
    欧拉回路：所有节点出度等于入度

算法

算法1 Fleury's algorithm

算法2 Hierholzer's algorithm

算法步骤：
从节点u开始，当u的邻接节点不为空时，选取邻接节点其中一个节点v，将v从u的邻接节点中删除，以v为根结点进行dfs遍历。当u的邻接节点均遍历完成后，将u加入到最终的路径中。

NOTE：似乎只能应用于存在欧拉回路的图中

相关文章

网友评论

      本文标题：332. Reconstruct Itinerary

      本文链接：https://www.haomeiwen.com/subject/abjjahtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|332. Reconstruct Itinerary|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！