第一百三十四章 欧拉路径遍历理论（计算） (第2/2页)

对欧拉来说，遍历最麻烦的事情就是走回头路。

很多问题的解决，只有在少走回头路的时候才能顺利解决。

解决七桥问题之后，欧拉开始研究把很多遍历问题，转化成图论里的最短遍历路径问题。

对欧拉来说，最简单的路径遍历，就是二叉树遍历。

但不是所有图都可以转化成二叉树遍历问题，容易造成浪费。

求欧拉回路的思路：

循环的找到出发点。

从某个节点开始，然后查出一个从这个出发回到这个点的环路径。

这种方法不保证每个边都被遍历。

如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。

这样，整个图就被连接到一起了。

具体步骤：

1，如果此时与该点无相连的点，那么就加入路径中。

2，如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。

3，处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。

4，这个其实是个递归过程。

这是最短的最合理的方式了。