欧拉回路

七桥问题

18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来，如下图(黄色线条代表桥，绿色区域代表小岛和河岸)

有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。

数学家欧拉将河岸与小岛建模为节点，而七座桥建模为边，所以七桥问题建模为上图最右边的图论问题，找到图中经过所有边一次且回到原点的回路，这种回路我们后来称为欧拉回路。

欧拉回路的数学性质

上述的七桥问题很长时间都没有解决，即人们没有找到一条回路，能够只经过每座桥一次，然后回到原点。所以欧拉就猜想是不是根本不存在这种回路，经过他的证明，上述七桥问题的确不存在欧拉回路。

欧拉证明十分的简单，因为要从起点出发回到原点，那么对于每个节点都要一进一出，而每次进出需要消耗两条边，所以每个节点必须具有偶数条边，它才能保证有进有出，才有可能回到原点。所以就得到了欧拉回路一个充分必要条件：

每个节点的度都是偶数 $\Leftrightarrow$ 图中存在欧拉回路

每个节点的度都是偶数是图中存在欧拉回路是充分必要条件，二者可以互推，所以我们只要判断图中每个节点的度是不是偶数即可得到图中是否有欧拉回路这个结论。

回到七桥问题，观察图中的每一个节点，发现它们的度都不是偶数，所以绝对不可能从某点出发，经过所以的边一次然后回到原点，至此欧拉完美的解决了七桥问题，图论领域也是从此开始发展。

下面是判断欧拉回路是否存在的代码：

public class EulerCycle {
    private Graph graph;

    public EulerCycle(Graph graph) {
        this.graph = graph;
    }

    public boolean hasEulerCycle() {

        // 如果图中不只一个联通分量的话，说明肯定没有欧拉回路
        CCGraph ccGraph = new CCGraph(graph);
        if (ccGraph.getCCcount() != 1) {
            return false;
        }

        for (int i = 0; i < graph.V(); i++) {
            if (graph.degree(i) % 2 != 0) {
                return false;
            }
        }
        return true;
    }
}

求解欧拉回路

上面我们只是判断图中欧拉回路是否存在，但是我们没有得到一个具体的欧拉回路，所以在本节中介绍三种方法得到欧拉回路。

回溯法

回溯法就是暴力搜索法，搜索从起点出发的所有路径，直到找到一条欧拉回路

Fleury 算法

考虑下图，当我们从节点 0 来到节点 2 时

对于回溯法，可以选择遍历节点 1，也可以选择遍历节点 3，而 Fleury 算法却会选择接下来遍历节点 3 而不是节点 1，因为边 2-1 它是一个桥，如果选择遍历节点 1，就不可能再次回到节点 2，即节点 2 右边的边 2-3 2-4 不可能被访问到，所以 Fleury 算法的策略就是在遍历边前判断这条边是不是桥，如果是桥的话，就不遍历这条边，选择其他的边。

Hierholzer 算法

上图每个节点的度都是偶数，所以该图一定有欧拉回路。Hierholzer 算法首先在图中随便找到一个环

这个环如果是欧拉回路，那就找到了；如果不是欧拉回路，例如上面找到环 $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 0$，它不是欧拉回路，中间缺失了一环，因为节点 2 还与别的节点相连，上述链中的 $2$ 应该变为 $2 \rightarrow … \rightarrow 2 $，所以我们需要回退到节点 2 开始寻找这个环。

比如我们继续找到了 $2 \rightarrow 4 \rightarrow 5 \rightarrow 2$ 这个环

但是因为 $5$ 还与别的节点相连，所以 $5$ 应该被扩展为 $5 \rightarrow … \rightarrow 5$，所以又需要回退到节点 5 开始寻找新的环

最终我们找到了环 $5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow 5$，将这个结果替换 $2 \rightarrow 4 \rightarrow 5 \rightarrow 2$ 其中的 $5$，得到 $2 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow 5 \rightarrow 2$，最后将这个结果环替换 $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 0$ 其中的 $2$，结果变为 $0 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow 5 \rightarrow 2 \rightarrow 3 \rightarrow 0$。

我们可以使用栈来模拟上面的回退动作，当我们遍历环时，将节点添加进栈 result中，当我们发现来到某个节点不能继续遍历并且还有边未被遍历时，我们便进行回退，从栈中弹出元素，直到栈顶节点还与其他节点相连，从该节点开始寻找新的环。我们会将从栈中弹出的节点添加到另一个栈 back 中，当我们遍历完所有的边时在将 back 这个栈中的节点依次弹入到 result 这个栈中

因为上面有删边的动作，所以我们在 Graph 接口添加了一个 removeEdge(int v, int w)，作用就是将 v-w 这条边删除，具体实现如下

@Override
public void removeEdge(int v, int w) {
    validateVertex(v);
    validateVertex(w);
    sets[v].remove(w);
    sets[w].remove(v);
}

Hierholzer 算法的实现如下

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class EulerCycle {
    private Graph graph;

    public EulerCycle(Graph graph) {
        this.graph = graph;
    }

    public boolean hasEulerCycle() {

        CCGraph ccGraph = new CCGraph(graph);
        if (ccGraph.getCCcount() != 1) {
            return false;
        }

        for (int i = 0; i < graph.V(); i++) {
            if (graph.degree(i) % 2 != 0) {
                return false;
            }
        }
        return true;
    }

    public Iterable<Integer> result() {
        ArrayList res = new ArrayList();
        if (!hasEulerCycle()) return res;

        // 剩余未被遍历的边数
        int left = graph.E();
        Stack<Integer> result = new Stack<>();
        Stack<Integer> back = new Stack<>();

        int curV = 0;
        result.push(curV);
        // 还有边未被遍历就继续遍历
        while (left != 0) {
            // 每次更新 curV 为栈顶节点
            curV = result.peek();
            // 如果栈顶元素有相邻节点，从此寻找新的环
            if (graph.degree(curV) != 0) {
                // 获得一个相邻节点
                int w = graph.adj(curV).iterator().next();
                result.push(w);
                graph.removeEdge(curV, w);
                left--;
            } else {
                // 没有相邻节点，进行回溯
                back.push(result.pop());
            }
        }

        // 将 back 栈中的数据依次弹出到 result
        while (!back.isEmpty()) {
            result.push(back.pop());
        }

        // 将栈中元素弹出到 list 中
        while (!result.isEmpty()) {
            res.add(result.pop());
        }

        Collections.reverse(res);
        return res;
    }
}

验证算法是否正确，新建 g11.txt，内容如下

所表示的图就是示例中的图

测试如下

public static void main(String[] args) {
    Graph graph = new AdjSet("g11.txt");
    EulerCycle eulerCycle = new EulerCycle(graph);
    for (int w: eulerCycle.result()) {
        System.out.print(w + " ");
    }
}