有向图-可达性分析

图的数据结构常用邻接矩阵或邻接表来表示

这里用邻接表来实现一个有向图

顶点链表节点（邻接表）

public class Vertex {
    public int v;　　　　//当前顶点编号
    public Vertex n;    //指向的下一个顶点对象

    public Vertex(int v) {
        this.v = v;
    }

    public int getV() {
        return v;
    }
}

有向图

public class Digraph {

    Vertex[] vs; //邻接表数组
    int e;

    public Digraph(int vCount) {
        vs = new Vertex[vCount];
    }

    public Digraph(Graph g) {
        vs = new Vertex[g.v()];
        for (int u = 0; u < g.v(); u++) {
            for (int v : g.adj(u))
                addEdge(u, v);
        }
    }

    public void addEdge(int v, int w) { //添加一条v顶点指向w顶点的边
        Vertex vwvic = new Vertex(w);
        vwvic.n = vs[v];
        vs[v] = vwvic;
        e++;
    }

    public boolean hasEdge(int u, int v) { //是否存在u顶点指向v顶点的边
        for (int w : adj(u)) {
            if (w == v)
                return true;
        }
        return false;
    }

    public int e() {       //有向图中边的数量
        return e;
    }

    public int v() {　　　　//有向图中顶点的数量
        return vs.length;
    }

    //反向有向图
    public Digraph reverse() {
        Digraph rd = new Digraph(v());
        for (int u = 0; u < v(); u++) {
            for (int v : adj(u))
                rd.addEdge(v, u);
        }
        return rd;
    }

    public static class VertexIt implements Iterable {
        VertexItor vi;

        public VertexIt(Vertex h) {
            vi = new VertexItor(h);
        }

        @Override
        public Iterator iterator() {
            return vi;
        }
    }

    public static class VertexItor implements Iterator {
        Vertex h;

        public VertexItor(Vertex h) {
            this.h = h;
        }

        @Override
        public boolean hasNext() {
            return h != null;
        }

        @Override
        public Object next() {
            Vertex tmp = h;
            h = h.n;
            return tmp.v;
        }

        @Override
        public void remove() {
            throw new RuntimeException("unsuport!");
        }
    }

    public Iterable<Integer> adj(int v) {  //获得从顶点v指向其他顶点的边 的迭代器
        return new VertexIt(vs[v]);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < v(); i++) {
            sb.append(i + " : ");
            for (int w : adj(i)) {
                sb.append(w + " ");
            }
            sb.append('
');
        }
        return sb.toString();
    }
}

然后基于深度优先，从一个起点，访问周围可达顶点，已经访问过的用 marked[v] = true 标记

//有向图可达性
public class DirectedDFS {
    Digraph dg;
    boolean[] marked;

    public DirectedDFS(Digraph dg, int s) {
        this.dg = dg;
        marked = new boolean[dg.v()];
        dfs(s);
        this.dg = null;
    }

    public DirectedDFS(Digraph dg, Iterable<Integer> s) {
        this.dg = dg;
        marked = new boolean[dg.v()];
        for (int u : s) {
            if (!marked[u]) {
                dfs(u);
            }
        }
    }

    private void dfs(int u) {
        marked[u] = true;
        for (int v : dg.adj(u)) {
            if (!marked[v])
                dfs(v);
        }
    }

    //是否可达 v点
    public boolean isMarked(int v) {
        return marked[v];
    }

    public static void main(String[] a) {
        //模仿JAVA 的垃圾回收机制
        //通过以GCRoot为起点(0)，探测可达的点（这些对象不被回收），而不可达的点被回收（说明不存在从GCRoot指向他们的引用)
        Digraph digraph = new Digraph(5);
        digraph.addEdge(0, 1);          //0:是GCroot,1:是activity
        digraph.addEdge(1, 2);          //2:是handle
        digraph.addEdge(3, 2);          //3:runnable对象 持有2:handler
//        digraph.addEdge(2,3);         //持有handler 接触持有的 runnable对象引用,  runnable已经不被handle持有
        digraph.addEdge(3, 4);          //3:runnable 对象持有一个非static的内部成员变量 4:Object

        DirectedDFS directedDFS = new DirectedDFS(digraph, 0);
        List<Integer> needGcObj = new LinkedList<>();
        for (int v = 0; v < digraph.v(); v++)
            if (!directedDFS.isMarked(v))
                needGcObj.add(v);

        System.out.println("需要被回收的对象有 :" + needGcObj);
    }
}

输出：

需要被回收的对象有 :[3, 4]

java虚拟机中的GC可达性分析，和这里的原理类似，从GCRoot不可达的，表示这类对象没有有效的引用，当GC发生时，会清理掉。

在C/C++ 这类没有一个类似虚拟机，运行时状态 管理的程序中，这类对象，如果程序员没有手动  del , free 掉，那么会产生内存泄漏

而java中也有类似的问题，虽然这类GC不可达的对象，垃圾回收机制帮我们清理了，还有另外一种内存泄露，比如下面的hanle，可能

之后的业务逻辑中，再也不会用到这个handle对象了，但是由于GC可达，而我们又没有释放它的引用，那么这类情况也算作内存泄露（只是不那么明显，而且必须从业务角度出发去判断）

存在的内存泄露类型:

java：　　1.GC可达但业务上不需要的

C/C++：　1.GC可达但业务上不需要的 2.GC不可达业务也不需要（忘记了del，free）　

GCroot -> activity -> handle

                        ^

                        |

                      runnable  -> object