DAG是公认的下一代区块链的标志。本文从算法基础去研究分析DAG算法，以及它是如何运用到区块链中，解决了当前区块链的哪些问题。
关键字：DAG，有向无环图，算法，背包，深度优先搜索，栈，BlockChain，区块链
图图是数据结构中最为复杂的一种，我在上大学的时候，图的这一章会被老师划到考试范围之外，作为我们的课后兴趣部分。但实际上，图在信息化社会中的应用非常广泛。图主要包括：
无向图，结点的简单连接
有向图，连接有方向性
加权图，连接带有权值
加权有向图，连接既有方向性，又带有权值
图是由一组顶点和一组能够将两个顶点相连的边组成。
常见的地图，电路，网络等都是图的结构。
术语顶点：图中的一个点
边：连接两个顶点的线段叫做边，edge
相邻的：一个边的两头的顶点称为是相邻的顶点
度数：由一个顶点出发，有几条边就称该顶点有几度，或者该顶点的度数是几，degree
路径：通过边来连接，按顺序的从一个顶点到另一个顶点中间经过的顶点集合
简单路径：没有重复顶点的路径
环：至少含有一条边，并且起点和终点都是同一个顶点的路径
简单环：不含有重复顶点和边的环
连通的：当从一个顶点出发可以通过至少一条边到达另一个顶点，我们就说这两个顶点是连通的
连通图：如果一个图中，从任意顶点均存在一条边可以到达另一个任意顶点，我们就说这个图是个连通图
无环图：是一种不包含环的图
稀疏图：图中每个顶点的度数都不是很高，看起来很稀疏
稠密图：图中的每个顶点的度数都很高，看起来很稠密
二分图：可以将图中所有顶点分为两部分的图
所以树其实就是一种无环连通图。
有向图有向图是一幅有方向性的图，由一组顶点和有向边组成。所以，大白话来讲，有向图是包括箭头来代表方向的。
常见的例如食物链，网络通信等都是有向图的结构。
术语上面我们介绍了顶点的度数，在有向图中，顶点被细分为了：
出度：由一个顶点出发的边的总数
入度：指向一个顶点的边的总数
接着，由于有向图的方向性，一条边的出发点称为头，指向点称为尾。
有向路径：图中的一组顶点可以满足从其中任意一个顶点出发，都存在一条有向边指向这组顶点中的另一个。
有向环：至少含有一条边的起点和终点都是同一个顶点的一条有向路径。
简单有向环：一条不含有重复顶点和边的环。
路径或环的长度就是他们包含的边数。
图的连通性在有向图中表现为可达性，由于边的方向性，可达性必须是通过顶点出发的边的正确方向，与另一个顶点可连通。
邻接表数组可表示图的数据类型，意思就是如何通过一个具体的文件内容，来表示出一幅图的所有顶点，以及顶点间的边。
邻接表数组，以顶点为索引（注意顶点没有权值，只有顺序，因此是从0开始的顺序值），其中每个元素都是和该顶点相邻的顶点列表。
5 vertices, 3 edges 0: 4 1 1: 0 2: 3: 4: 背包做一个背包集合，用来存储与一个顶点连通的顶点集合，因为不在意存储顺序，并且只进不出，所以选择背包结构来存储。温习一下背包
package algorithms.bag; import java.util.Iterator; // 定义一个背包集合，支持泛型，支持迭代 public class Bag<Item> implements Iterable<Item> { private class BagNode<Item> { Item item; BagNode next; } BagNode head; int size; @Override public Iterator<Item> iterator() { return new Iterator<Item>() { BagNode node = head; @Override public boolean hasNext() { return node.next != null; } @Override public Item next() { Item item = (Item) node.item; node = node.next; return item; } }; } public Bag() { head = new BagNode(); size = 0; } // 往前插入 public void add(Item item) { BagNode temp = new BagNode(); // 以下两行代码一定要声明，不可直接使用temp = head，那样temp赋值的是head的引用，对head的所有修改会直接同步到temp，temp就不具备缓存的功能，引发bug。。 temp.next = head.next; temp.item = head.item; head.item = item; head.next = temp; size++; } public boolean isEmpty() { return size == 0; } public int size() { return this.size; } public static void main(String[] args) { Bag<String> bags = new Bag(); bags.add("hello"); bags.add("yeah"); bags.add("liu wen bin"); bags.add("seminar"); bags.add("1243"); System.out.println(bags.size); // for (Iterator i = bags.iterator(); i.hasNext(); ) { // System.out.println(i.next()); // } // 由于Bag实现了Iterable接口，所以支持以下方式遍历 for (String a : bags) { System.out.println(a); } } } 有向图结构