有向图的可达性

单点可达性：给定一幅有向图和一个起点s，回答“是否存在一条从s到达给定顶点v的有向路径？”等类似问题。
多点可达性：给定一幅有向图和顶点集合，回答“是否存在一条从集合中的任意顶点到达给定顶点v的有向路径？”等类似问题。

我们可以使用深度优先搜索来解决这类问题。

有向图可达性API

在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比。

代码

其中有向图实现为Digraph。

package section4_2;

import section1_3.Bag;

public class DirectedDFS {

    private boolean[] marked;

    public DirectedDFS(Digraph G, int s) {
        marked = new boolean[G.V()];
        dfs(G,s);
    }

    public DirectedDFS(Digraph G, Iterable<Integer> sources) {
        marked = new boolean[G.V()];
        for (int s : sources) {
            if (!marked[s]) dfs(G,s);
        }
    }

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

    public boolean marked(int v) {
        return marked[v];
    }

    public static void main(String[] args) {
        int[][] data = {
                {4,2},
                {2,3},
                {3,2},
                {6,0},
                {0,1},
                {2,0},
                {11,12},
                {12,9},
                {9,10},
                {9,11},
                {8,9},
                {10,12},
                {11,4},
                {4,3},
                {3,5},
                {7,8},
                {8,7},
                {5,4},
                {0,5},
                {6,4},
                {6,9},
                {7,6}
        };
        int vn = 13;
        int en = 22;
        Digraph digraph = new Digraph(vn,en,data);

        //test case1
        Bag<Integer> sources1 = new Bag<>();
        sources1.add(1);
        DirectedDFS reachable1 = new DirectedDFS(digraph,sources1);
        for (int v = 0;v < digraph.V();v++) {
            if (reachable1.marked(v)) {
                System.out.print(v + " ");
            }
        }
        System.out.println();

        //test case2
        Bag<Integer> sources2 = new Bag<>();
        sources2.add(2);
        DirectedDFS reachable2 = new DirectedDFS(digraph,sources2);
        for (int v = 0;v < digraph.V();v++) {
            if (reachable2.marked(v)) {
                System.out.print(v + " ");
            }
        }
        System.out.println();

        //test case3
        Bag<Integer> sources3 = new Bag<>();
        sources3.add(1);
        sources3.add(2);
        sources3.add(6);
        DirectedDFS reachable3 = new DirectedDFS(digraph,sources3);
        for (int v = 0;v < digraph.V();v++) {
            if (reachable3.marked(v)) {
                System.out.print(v + " ");
            }
        }
        System.out.println();
    }

}

输出：

实际应用

标记-清除的垃圾收集

多点可达性的一个重要的实际应用是在典型的内存管理系统中。在一幅有向图中，一个顶点表示一个对象，一条边则表示一个对象对另一个对象的引用。这个模型很好地表现了运行中地Java程序的内存使用状况。在程序执行的任何时候都有某些对象是可以被直接访问的，而不能通过这些对象访问到的所有对象都应该被回收以便释放内存。标记-清除的垃圾回收策略会为每个对象保留一个位做垃圾收集使用。它会周期性地运行一个有向图可达性算法来标记所有可以被访问到的对象，然后清理所有对象，回收没有被标记的对象，以腾出内存供新的对象使用。