startSet是入参条件，只有一个值为2，即在图中找寻2的有效路径，通过图中的边我们可以看出，2的有效路径只有3，所以输出是正确的。
可达性的一种应用：垃圾收集我们都知道一般的对象垃圾收集都是计算它的引用数。在图结构中，把对象作为顶点，引用作为边，当一个对象在一段时间内未被他人引用的时候，这个顶点就是孤立的，对于其他有效路径上的顶点来说它就是不可达的，因此就不会被标记，这时候，例如JVM就会清除掉这些对象释放内存，所以JVM也是一直在跑类似以上这种DFS的程序，不断找到那些未被标记的顶点，按照一定时间规则进行清除。
有向无环图不包含有向环的有向图就是有向无环图，DAG，Directed Acyclic Graph。
上面我们循序渐进的介绍了图，有向图，本节开始介绍有向无环图，概念也已经给出，可以看出有向无环图是有向图的一种特殊结构。那么第一个问题就是
如何监测有向图中没有有向环，也就是如何确定一个DAG。
寻找有向环基于上面的问题，我们要做一个寻找有向环的程序，这个程序还是依赖DFS深度优先搜索算法，如果找不到，则说明这个有向图是DAG。
栈先来补个坑，其实前面包括背包我在之前都写过，但因为前面那篇文章是我第一篇博文，我还太稚嫩，没有掌握好的编辑器，也没有粘贴代码，所以这里有必要重新填坑。
package algorithms.stack; import ioutil.StdOut; import java.util.Iterator; import java.util.NoSuchElementException; public class Stack<Item> implements Iterable<Item> { private int SIZE; private Node first;// 栈顶 public Stack() {// 初始化成员变量 SIZE = 0; first = null; } private class Node { private Item item; private Node next; } // 栈：往first位置插入新元素 public void push(Item item) { Node temp = first; first = new Node(); first.item = item; first.next = temp; SIZE++; } // 栈：从first位置取出新元素，满足LIFO，后进先出。 public Item pop() { if (isEmpty()) throw new RuntimeException("Stack underflow"); Item item = first.item; first = first.next; SIZE--; return item; } public boolean isEmpty() { return first == null; } public int size() { return this.SIZE; } @Override public Iterator<Item> iterator() { return new Iterator<Item>() { Node node = first; @Override public boolean hasNext() { return first != null; } @Override public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = node.item; node = node.next; return item; } }; } public static void main(String[] args){ Stack<String> stack = new Stack<>(); stack.push("heyheyhey"); stack.push("howau"); stack.push("231"); StdOut.println(stack.SIZE); StdOut.println(stack.pop()); } }我们要做寻找有向环的程序的话，要依赖栈的结构，所以上面把这个坑给填了，下面回归到寻找有向环的程序。（当然，你也可以直接使用java.util.Stack类）
package algorithms.graph; import ioutil.StdOut; import java.util.Stack; public class DirectedCycle { private boolean[] marked;// 以顶点为索引，值代表了该顶点是否标记过（是否可达） private Stack<Integer> cycle; // 用来存储有向环顶点。 // *****重点理解这里start**** private int[] edgeTo;// edgeTo[0]=1代表顶点1->0, to 0的顶点为1。 // *****重点理解这里end**** private boolean[] onStack;// 顶点为索引，值为该顶点是否参与dfs递归，参与为true public DirectedCycle(Digraph digraph) { // 初始化成员变量 marked = new boolean[digraph.V()]; onStack = new boolean[digraph.V()]; edgeTo = new int[digraph.V()]; cycle = null; // 检查是否有环 for (int v = 0; v < digraph.V(); v++) { dfs(digraph, v); } } private void dfs(Digraph digraph, int v) { onStack[v] = true;// 递归开始，顶点上栈 marked[v] = true; for (int w : digraph.adj(v)) {// 遍历一条边，v-> w // 终止条件：找到有向环 if (hasCycle()) return; // 使用onStack标志位来记录有效路径上的点，如果w在栈上，说明w在前面当了出发点， if (!marked[w]) { edgeTo[w] = v;// to w的顶点为v dfs(digraph, w); } else if (onStack[w]) {// 如果指到了已标记的顶点，且该顶点递归栈上。（栈上都是出发点，而找到了已标记的顶点是终点，说明出发点和终点相同了。） cycle = new Stack<Integer>(); for (int x = v; x != w; x = edgeTo[x]) {//起点在第一次循环中已经push了，不要重复 cycle.push(x);// 将由v出发，w结束的环上中间的结点遍历push到cycle中。 } cycle.push(w);// push终点 } } onStack[v] = false;// 当递归开始结算退出时，顶点下栈。 } public boolean hasCycle() { return cycle != null; } public Iterable<Integer> cycle() { return cycle; } public static void main(String[] args) { Digraph d = new Digraph(6); d.addEdge(0, 1); d.addEdge(1, 2); d.addEdge(2, 3); d.addEdge(3, 0); DirectedCycle directedCycle = new DirectedCycle(d); if (directedCycle.hasCycle()) { for (int a : directedCycle.cycle()) { StdOut.println(a); } } else { StdOut.println("DAG"); } } }这段代码不长但其中算法比较复杂，我尽力在注释中做了详细解释，如有任何不明之处，欢迎随时留言给我。
以上程序的测试用图为
6 vertices, 4 edges 0: 1 1: 2 2: 3 3: 0 4: 5:肉眼可以看出，这是一个0-1-2-3-0的一个有向环，所以以上程序的执行结果为：
3 2 1 0先入栈的在后面，可以看出是0-1-2-3的有向环结构。如果我们将图的内容改为：
6 vertices, 4 edges 0: 1 1: 2 2: 3 3: 4: 5: 0则明显最后一个拼图3-0被我们打破了，变成了无所谓的5-0，这时该有向图就不存在有向环。此时以上程序执行结果为：
DAG DAG与BlockChain