C++ 图论算法之欧拉路径、欧拉回路算法（一笔画完）

公众号：编程驿站

本文从哥尼斯堡七桥的故事说起。

哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个话题：怎样不重复地走遍七桥，最后回到出发点。这也是经典的一笔画完问题。

1736年瑞士数学家欧拉（Euler）发表了论文《哥尼斯堡七桥问题》。论文中使用图论理论解决哥尼斯堡七桥问题，欧拉图由此而来。论文中欧拉证明了如下定理：一个非空连通图当且仅当每个顶点的度数都是偶数时才会是欧拉图。

欧拉图的几个概念：

欧拉图的性质：

因为欧拉回路定义只能经过每条边一次，所以，对于每一个节点，至少需要有 2n(n=0,1……) 条边连接该节点。

论证：当 n = 0时，图结构中只含有一个节点v，边数为0，图论中认为自己和自己是能构建成回路的。所以当n=0时，图是欧拉图。

当n>=1时，如果从一个节点出发，经过一个路径后，能够重新回来。相当于一个人要和其他人围成一个圈，每个人必须伸出两只手，否则是不可能形成圈的。故每个节点都连接有2n(n = 0,1,2,...n)条边。

欧拉路径中奇节点（连接该节点的边的数量为奇数）的个数为0或2。若奇节点的个数为0，则图中存在欧拉回路，欧拉回路也是欧拉路径的一种。把欧拉回路变成欧拉路径，只需要抽取出环中的一条边。因为欧拉环的充要条件是节点度数有偶数，抽取出一条边后，会让原来连接边两端的节