有向图的几个算法分析总结

简介

    前面讨论的很多文章里，都是针对无向图进行的分析。无向图的一个特性就是其中一旦两个节点a和b是相连的，这就意味着有路径从a到b，同时也有从b到a的。它具体对应的矩阵表达方式对应着一个对称矩阵。而这里重点是考察有向图。和无向图比起来，有向图更加多了一种出入度的概念。因为方向的有向性，很多以前在无向图里看起来比较简单的问题在这里会变得更加有意思。

 

有向图定义

　　一个常用的有向图会如下图这样：

　　因为每个节点和节点之间对应着一定的方向关系，所以这里用一个箭头来表示从一个节点到另外一个节点的有向关系。在具体保存有向图定义的数据结构里，我们还是可以采用一样的链表组结构。只是因为是有向图，所以加入元素的时候不用考虑对称节点的问题。在实现上其实也更加简化。

　　下面是一个关于有向图的简单定义实现：

 

public class Digraph {
    private final int vertices;
    private int edges;
    private List<LinkedList<Integer>> adj;

    public Digraph(int vertices) {
        if(vertices < 0) throw new IllegalArgumentException(
                "Number of vertices in a Digraph must be nonnegative");
        this.vertices = vertices;
        this.edges = 0;
        adj = new ArrayList<LinkedList<Integer>>();
        for(int i = 0; i < vertices; i++) {
            adj.add(new LinkedList<Integer>());
        }
    }

    public void addEdge(int v, int w) {
        if(v < 0 || v >= vertices) 
            throw new IndexOutOfBoundsException(
                    "vertex " + v + " not in bound.");
        if(w < 0 || w >= vertices) 
            throw new IndexOutOfBoundsException(
                    "vertex " + w + " not in bound.");
        adj.get(v).add(w);
        edges++;
    }
}

　这部分代码很简单，无需解释。

　有了这部分定义之后，我们再来考虑后面的几个典型的问题。

 

环的存在和检测

　和前面无向图的过程有点类似，我们要检测一个图中间是否存在环，肯定也需要通过某种遍历的方式，然后对访问过的元素做标记。如果再次碰到前面访问过的元素，则说明可能存在环。这里，如何来检测环和如果这个环存在的话，我们要返回这个环。在无向图的时候，这个方法确实是很简单可行，我们可以通过广度或者深度优先遍历来解决。在有向图的情况下，前面的办法照搬过来就一定可行吗？

　我们来看下面的一个示例：

 

    在该图中，假设我们从节点１开始去遍历，当按照前面的仅仅是修改marked[] 数组的办法，可能先通过节点２到达节点６，于是就设定了marked[6] = true。如下图：

 

　　当再次遍历到节点６的时候，则如下图所示：

　　这个时候，如果去看marked[6]的话，它已经被标记为true了。可是，如果按照这个条件，我们就确定这种情况存在环，肯定不行。因为现在的这个情况实际上并不是一个环，它仅仅是访问到了一个前面访问过的节点。在这种情况下，要判断一个环的存在，和取得环所在元素的问题根源在于哪里呢？

　　在前面的示例中，我们从节点１到２，然后到６，整个的过程里，这几个点被遍历了，但是光到这一步还没有构成一个环。按照深度优先遍历的过程，这个时候相当于２和６已经遍历完了，要去遍历节点１的另外一个边。实际上，这个时候就算从另外一个边可以遍历到前面的节点２或者６，因为这个时候能访问到２和６的是另外一组有向边了，它们和前面经过的那些有向边是不一定构成环的。

　　另外，从环的构成来说。如果我们按照深度优先的顺序访问到了一个环，必然是在逐步递归推进的过程中能访问到自己前面访问过的节点。这里的差别就在于递归推进所重复访问的节点和前面图深度遍历所访问的节点还又所差别。我们以下图来说明一下它们的详细差别：

　　假定我们从节点１出发，先访问２这边的边，一直到节点６，这个时候按照深度优先遍历是首先一步步递归进去到节点６。因为节点６没有别的出边，所以就要一步步的按照前面的过程返回。这个过程如下图：

　　在前面２，６节点都返回后，这个时候就算后面的节点比如５访问到６了，它们是不构成环的，如下图：

 　　这个时候的节点２和６，它们和节点３,4, 5之间的差别是，２和６已经不在函数递归的栈里了，因为它们已经从前面的递归里返回了，而3,4,5节点还是在里面。所以到后面遍历到节点７,8之后，我们再次碰到了节点４，就可以确认它们是构成了一个环。如下图：

　所以，这里问题的关键点就是，我们再次碰到的节点４它还没有从前面向前递归的函数返回回来，结果又被遍历的时候给碰上了。这样，按照前面的分析，我们的环检测要点就是，找到一个还在遍历中的节点，同时在遍历的时候它如果再次被访问到了，则表示找到了环。而如果它被访问完了之后返回，则再次碰到它的时候就不是环了。

　从实现的角度来说，相当于对这个节点递归访问前要设置一个对应的值，表示它在一个递归顺序里。然后在它访问退出这个递归后，要将这个值设置回来。一种简单的方式就是设置一个boolean[] onstack这样的数组，每个元素对应这里面的一个值。然后，因为要记录访问过的节点，肯定要用一个boolean[] marked数组。另外，既然还要记录环的结果，肯定还要一个记录前向访问的数组int[] edgeTo。

　　按照前面的讨论，可以得到一个检验环并保存环的代码实现：

public class DirectedCycle {
    private boolean[] marked;
    private int[] edgeTo;
    private Stack<Integer> cycle;
    private boolean[] onStack;

    public DirectedCycle(Digraph g) {
        onStack = new boolean[g.getVertices()];
        edgeTo = new int[g.getVertices()];
        marked = new boolean[g.getVertices()];
        for(int v = 0; v < g.getVertices(); v++) {
            if(!marked[v]) dfs(g, v);
        }
    }

    private void dfs(Digraph g, int v) {
        onStack[v] = true;
        marked[v] = true;
        for(int w : g.adj(v)) {
            if(hasCycle()) return;
            if(!marked[w]) {
                edgeTo[w] = v;
                dfs(g, w);
            } else if(onStack[w]) {
                cycle = new Stack<Integer>();
                for(int x = v; x != w; x = edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }
｝

 　前面代码的要点在于dfs方法。当我们要访问某个节点v的时候，首先设置它对应的onStack[v] = true。而这个节点被访问结束后，肯定是在它后面遍历的递归都结束了，所以要在for循环之后重新将onStack[v] = false。在找到环的时候，我们根据当前节点v不断回退到某个节点，这个节点刚好就是w。因为这是属于函数递归调用里面的，如果检测到w被遍历过，必然也能够找到w。于是讲这些节点压入栈中。这样整个环就找到了。

　前面代码里引用到的方法hasCycle就很简单，它和返回整个环的代码如下：

public boolean hasCycle() {
        return cycle != null;
    }

    public Iterable<Integer> cycle {
        return cycle;
    }

 　查找和返回有向图里的环需要遍历所有的节点，同时根据每次递归推进的过程中保证覆盖到在同一个递归序列里的元素。这是实现的两个要点。

 　这里我们讨论了有向图环的检测和引用，它在后续的问题应用里有很重要的作用。在后续的小节里会继续说明。这里先埋下一个伏笔。

 

深度优先遍历排序

　我们在对图做一些遍历的时候，有的时候会发现一个和访问树很类似的规律。比如说，访问一棵二叉树的时候，我们访问它的序列关系不同，会产生不同的序列。比如说前序，中序和后序。在访问图的时候，假定以深度优先遍历为例。当我们每次遍历到一个节点的时候就访问它，也可以称其访问序为前序，而如果等它遍历递归后返回的时候再访问它，这就相当于一个后序。以前面的图为例：

　　这里，我们如果按照前序的过程来遍历的话，首先就是1, 2, 6。然后是3, 4, 5, 7, 8。这就是典型的深度优先递归访问的步骤。而按照后序的过程来考虑呢，它访问的顺序则如下：6, 2, 8, 7, 5, 4, 3, 1。这里的序列相当于是将每个遍历访问的节点先入栈，然后当遍历到一个没有出边的节点时，这将作为一个返回条件。递归再逐步返回。

　要实现这两种遍历的方法其实很简单，无非就是在深度优先遍历的时候在访问某个节点前或者访问结束后将节点加入到队列里。具体的实现如下：

 

public class DepthFirstOrder {
    private boolean[] marked;
    private Queue<Integer> pre;
    private Queue<Integer> post;

    public DepthFirstOrder(Digraph g) {
        pre = new LinkedList<Integer>();
        post = new LinkedList<Integer>();
        marked = new boolean[g.getVertices()];

        for(int v = 0; v < g.getVertices(); v++)
            if(!marked[v]) dfs(g, v);
    }

    private void dfs(Digraph g, int v) {
        pre.add(v);
        marked[v] = true;
        for(int w : g.adj(v)) {
            if(!marked[w])
                dfs(g, w);
        }
        post.add(v);
    }

    public Iterable<Integer> pre() {
        return pre;
    }

    public Iterable<Integer> post() {
        return post;
    }
}

 　重点就是在dfs方法里。在pre里面添加元素的时候是每次刚第一次访问某个节点时。而在post里面添加元素的时候则表示通过该节点以及它所关联的节点都已经遍历结束了。这两个序列有什么作用呢？在后序一些计算里，还是很有用的。

 

　比如说后序的序列，因为每次我们放入队列的是已经被遍历过的节点，而且通过这个节点已经不可能再访问到别的节点了。这就意味着从这个节点要么是出度为０的节点，要么是通过它所能访问到的节点都已经被访问过了。因为这些节点将作为递归结束的条件返回。所以说它们是优先返回的。也说明这些被返回的节点是可以被其他节点所遍历访问到的。而如果图里面有孤立的节点或者入度为０的节点呢？对于它们，因为没有办法通过其他节点所遍历到，它们被返回的可能性就越晚。这种特性在后面的讨论里有一个很重要的作用。这里先不详细的阐述。

 

拓扑排序和DAG

　拓扑排序和DAG如果每接触过看起来会觉得很新奇。它们的定义是很紧密相连的。 该怎么来理解它们呢？我们先看看它们的定义。DAG(Directed acyclic graph)，表示有向无环图。就是对应一个有向图，但是它里面却没有环。像下面的这些个图，都可以称为DAG:

 

 

    对于这个定义，当我们要检测一个有向图是不是DAG的时候就很简单了。有了前面检测环的方法，直接用那个办法就可以了。现在，拓扑排序又是什么意思呢？

　这个概念结合一些具体的问题来说可能更加好理解一些。在一些任务安排和调度的问题里。不同的问题或者任务之间又一些依赖的关系，有的任务需要在某些任务完成之后才能做。就像一些学校的教学课程安排。设置某一门课程需要依赖于一个前置的课程，只有学生学习了前置课程之后才能取学习该课程。如果将一门课程当做一个节点，从它引出一个指针指向后序依赖它的课程。就可能有一个类似这样的图：

    如果将上图中每个课程用一个数字节点表示，这不正是前面的一个图吗？对于这种图来说，最大的特点就是它们肯定就不能存在环。不然就有逻辑上的错误。因此，前面检测一个图是否为DAG的方法就是看图中是否有环。而拓扑排序则是在确定没有环的情况下，输出一个正常的序列。这个序列表示从一个不依赖任何元素的节点到后序的节点。这些序列正好符合课程安排或者任务调度的逻辑顺序。

 　我们已经知道了，对于一个有向图来说，如果它不存在环，则它应该为DAG。现在的问题是怎么找出这个拓扑序列来呢？前面一节里讲到的深度优先排序的过程在这里就起到作用了。实际上，对于深度优先遍历的后序序列，如果我们将它们的顺序完全倒过来，得到的序列就是满足我们要求的序列。对于这部分的证明书上有详细的说明，这里就不再赘述，只是直接搬过来这个结论。

 　有了前面这两个结论的支持，要实现拓扑排序就已经比较简单了。就是我们首先判断一下图中间是否存在环，然后如果没有存在的话，则取其中后序遍历序列的相反就可以了。具体的实现如下：

public class Topological {
    private Iterable<Integer> order;

    public Topological(Digraph g) {
        DIrectedCycle cycleFinder = new DirectedCycle(g);
        if(!cycleFinder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(g);
            order = dfs.reversePost();
        }
    }
}

　因为这部分代码就是糅合前面几个部分的代码到一块，所以就很简单了。 

 

另外一种思路

　针对前面的判断DAG以及求拓扑序列的问题。我们如果仔细观察的话，会发现一个这么有意思的现象。就是拓扑序列要求的序列必然是开始于一系列入度为０的节点。如果没有入度为０的节点，则表示这个图不是DAG，这样连遍历都没有必要了。当然，如果只是因为这个图里有入度为０的节点，并不代表这个图就一定是DAG。只是有了这么一个特征之后有一个好处，我们判断图是否为DAG时还是要检查是否存在环。

　但是，一旦判断出图里没有存在环，剩下的给出拓扑排序序列可以更加简化。我们只要去取这些入度为０的节点，然后从这些节点遍历图。然后给出的序列就是拓扑排序的序列。

 　现在还要一个问题就是，我们怎么来求这些节点的入度呢？一个简单的办法就是在定义Digraph的时候增加一个数组int[] inDegree。每次我们添加一个边u->v到图里时，inDegree[v]++。剩下的事，你懂的。

 

总结

　有向图虽然看起来在定义的很多方面和无向图很近似，但是当考虑到它的一些具体特性时。很多原来在无向图里比较简单的问题就变得更加复杂化了。比如说判断环和求图中的环时，需要利用深度优先递归的序列来判断。另外，有向图里前序、后序遍历在判断图是否为DAG以及求图的拓扑排序时很有帮助。里面的详细实现细节值得好好琢磨。这篇文章相对比较长，不过在讨论这些问题的时候能够有点小小的收获和一些想法，也算是挺不错的。

 

参考材料

Algorithms 

http://algs4.cs.princeton.edu/42directed/Digraph.java.html

http://algs4.cs.princeton.edu/42directed/DepthFirstOrder.java.html

http://algs4.cs.princeton.edu/44sp/DirectedCycle.java.html