All paths in a graph

问题描述

　　给定一个图中间两个节点，我们需要返回这两个节点之间所有的simple path。什么是simple path呢？就是图中间不包含有重复节点的路径。

 

问题分析

　　对于这个问题，我们比较容易想到一些和其他问题近似的地方。比如说给定两个节点要判断它们是否连通。而且在连通的时候我们可以找到一条这两个节点之间的路径。对于这个相对简化的问题来说，我们可以通过图的某种遍历方式，每次遍历的时候记录节点之间的访问关系，一直到目标节点。

　　对于我们这个问题本身来说，它和那个简化的问题不一样。因为这里要列出所有到达目标节点的路径。对于两个节点之间，它们可能有多个路径是连通的。比如说节点a和c之间构成一个如下的图：

　　那么，从上图中我们可以看到从a到c的路径可以有a-> c，也有a --> b -->  c。假设我们用前面的深度优先遍历来访问图的时候，如果我们一开始是走的路径a --> c，那么这就是找到了一个路径了。而要找到另外一个路径，我们就需要将前面访问过的c节点重置一下。因为一般的情况下我们遍历时会将访问过的节点做一个标记，而这里因为有多个路径要记录，我们需要将达到目的节点的路径重置。这样下次访问的时候才能不会有可选的路径被覆盖。

　　因此在这里我们就可以发现，我们需要在函数递归调用返回的时候将当前访问的节点重置。也就是在递归调用回溯的阶段要做的事情。这样，我们在深度优先遍历查找的时候设置两个参数v, t。一个表示当前节点，一个表示目标节点。当当前节点v == t的时候，则说明找到了一个路径，我们需要将当前路径里的值给记录下来。而为了保存这个访问的记录，我们需要用一个栈来保存每次走过的节点。

　　按照前面所描述的，在调用返回的时候，我们需要进行重置，也就是将当前节点从栈里弹出来，然后当前节点的访问标识设置回去。

　　这样，我们可以得到一个如下的实现： 

 

public class AllPaths {
    private boolean[] onPath;
    private Stack<Integer> path;
    private int List<List<Integer>> result;
    private int numberOfPaths;

    public AllPaths(Graph g, int s, int t) {
        onPath = new boolean[g.vertices()];
        path = new Stack<>();
        result = new ArrayList<>();
        dfs(g, s, t);
    }

    private void dfs(Graph g, int s, int t) {
        path.push(v);
        onPath[v] = true;
        if(v == t) {
            // process current path
            processCurrentPath();
            numberOfPaths++;
        } else {
            for(int w : g.adj(v)) {
                if(!onPath[w])
                    dfs(g, w, t);
            }
        }
        path.pop();
        onPath[v] = false;
    }

    private void processCurrentPath() {
        List<Integer> list = new ArrayList<>();
        list.addAll(path);
        Collections.reverse(list);
        result.add(list);
    }

    public int numberOfPaths() {
        return numberOfPaths;
    }

    public List<List<Integer>> allPaths() {
        return result;
    }
}

　　总的来说，上述的代码无非就是深度优先遍历这个递归函数调用的变体。在函数递归调用结束开始回溯的时候，我们可以有一些巧妙的应用。这样就能将所有合适的路径给记录下来。 

 

总结

　　利用一些函数的递归调用和回溯关系，我们不仅可以找到图里面两个节点之间所有可能的路径。同时在其他很多问题的典型应用中也得到很好的利用。比如n皇后问题里递归回溯的推导利用，比如求树中间两个节点的最低公共父节点。这里的应用很巧妙，值得深入分析。 

 

参考材料

http://algs4.cs.princeton.edu/41graph/AllPaths.java.html