标注
正在从小白成长的我想写一个小白看得懂的DAG拓扑排序！不要嫌我啰嗦噢！
目录
1.什么是DAG
2.什么是拓扑排序
3.Kahn算法思想
4.Kahn算法代码实现
5.运行结果
1.DAG
首先，什么是DAG？DAG就是Directed Acyclic Graph 有向五环图。顾名思义，就是结点和结点之间的连接是有方向性的，并且任意两个结点之间不形成回路。 
从如上的图大家应该对DAG有所感知了。因为每两个结点之间的连线是有箭头的，所以在1，2，3中1可以到2，2可以到3，3不能找到1（因为是逆箭头方向）所以这个图是无环的。
2.拓扑排序
简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。——百度百科
这里引用百度百科对拓扑排序的定义。并做一些非官方的解释：
拓扑排序其实就是基于有向无环图，遍历所有的结点，每两个结点之间有先后关系。并且在搜索下一个结点的时候，这个结点之前的结点已经全部被搜索过。
3.Kahn算法思想
了解了DAG和拓扑排序后我们来看看具体的实现。本篇博客用的是java语言，Kahn算法。首先我们要了解算法的目的的是什么，然后再将算法分块分析。
目的：从某一个入度为0的结点开始
代码块解剖：这里我们一个一个类分开来分析
1.第一个类：class Node{}。在Node类中要写如结点的属性String name。（这里要注意的是，虽然我们传入的node是整型的，但是还是写成字符串String类型的比较好。因为我们需要重写toString方法才能让输出的node不是地址，而toString方法返回的是字符串public String toString(){return name};，所以为了避免写toString方法的时候还要强行将int转化为String，我们在定义node的name属性的时候，就直接写成了String类型。）
2.第二个类：class Graph{}在这里我们就可以建立一个包含List的Map：Map<Node,List<Node>> map=new HashMap<Node,List<Node>>();在这里，map是这个图的对象名称，之后我们用这个对象名称来调用图。
3.第三个类：public class DAG{}这是最主要的类，因为我将图的构建，算法的过程和主方法都写在了这里面。我们现在一个一个方法来分析。
在各个方法的前面我们需要定义一些大家都有的东西，比如：结果数组result（用来存储遍历的结果），队列zeroIndegree（用来存储入度为0的结点），图（就是我们所要构建的DAG）。这里每一个定义都要new一下，相当于分配了一个空间。而且这里的< Node >为储存进去的数据的类型。（没有写< Node > 也没关系，最多会在eclipse代码行左边出现小黄灯泡和感叹号，不会影响代码运行。）
（1）先讲一下较为简单的main方法，把精彩的留在后头哈哈哈哈~~在main方法中我们要传入图，并且调用所写的Kahn方法，然后用增强型for循环遍历。调用和遍历就不用说了。我来讲一下如何传入图。就以本文开始的那张图为例子。 
首先每一个结点都定义为了Node ，我们有8个结点，分别为1，2，3，4，5，6，7，8这8个数字。将这8个数字分别写入结点中。 Node n1=new Node("1");
Node n2=new Node("2");
Node n3=new Node("3");
Node n4=new Node("4");
Node n5=new Node("5");
Node n6=new Node("6");
Node n7=new Node("7");
Node n8=new Node("8");
然后我们用邻接表来储存图，实现形式是在Map的value中存List，每一个node定义一个List，然后给每一个List分配空间，并且加入数值。
因为我们将Map定义在了Graph类中，所以我们要通过Graph的对象graph来添加结点。
添加结点的时候我们有一个技巧，叫做逆邻接表。我们在链表List中存的不是结点指出去的箭头，而是结点指回来的箭头。以便于我们在写Kahn算法时找到入度为0的点。如图所示储存： 
具体的写法大家可以参照具体代码。
（2）接着就是重中之重。Kahn算法思想：首先，要明确我们要用什么数据结构，其实这里主要就是队列的运用。我将代码再贴一下方便查看 while(!zeroIndegree.isEmpty())//队列不为空
{
Node node1=zeroIndegree.poll();//队首元素取出
result.add(node1);//放到结果数组中
//遍历map中的key
for(Node node :graph.map.keySet())
{ //如果map中的list含有node1，就删除node1
if(graph.map.get(node).contains(node1)){
graph.map.get(node).remove(node1);
//如果map中的list中有为空的node，将其加入队列
if(graph.map.get(node).isEmpty()){
zeroIndegree.add(node);
} } }
带圈圈的数字表示在List中删掉数字n后进入队列的值
不知道大家能不能看懂注释和示意图。我再次解释一下：
算法刚开始我就传进去了第一个入度为0的key值1（大家可以在main函数中看到）基于这个前提条件，我们进入循环。
要找到入度为0的点，就需要遍历Map中的key值，看一下key值所对应的List是否为空。如果为空，就说明这一个key值没有箭头指向它，即入度为0，我们将它标记为node1。将这node1添加到队列中。并且如果队列不为空，就弹出队首元素到result的结果数组里面。
那么问题来了，如何继续找到加入zeroIndegree队列中的数值？我们需要删除操作，在Map的所有value中（即所有的List中存的值）寻找node1，并且将它删除，这个操作就表示我们删除了node1和其相连结点之间的所有边。接着我们再回到大循环去遍历Map中所有的key，看对应List中是否为空，如果为空，就找到了下一个加到zeroIndegree队列中的数值。
4.Kahn算法代码实现
下面是Kahn算法的java实现
package DataStructure;
import java.lang.reflect.Array;
import java.util.*;
public class DAG {
List result=new ArrayList();//定义结果数组
Queue <Node> zeroIndegree=new LinkedList<Node>();
//用LinkedList接口实现Queue，将入度为0的点放入队列中
Graph graph=new Graph();//定义一个图
public DAG(Graph graph){
this.graph=graph;
}
//Kahn方法实现
public void Kahn(){
//在main函数中先传入一个入度为0的node
while(!zeroIndegree.isEmpty())//队列不为空
{
Node node1=zeroIndegree.poll();//队首元素取出
result.add(node1);//放到结果数组中
//遍历map中的key
for(Node node :graph.map.keySet())
{ //如果map中的list含有node1，就删除node1
if(graph.map.get(node).contains(node1)){
graph.map.get(node).remove(node1);
//如果map中的list中有为空的node，将其加入队列
if(graph.map.get(node).isEmpty()){
zeroIndegree.add(node);
}
}
}
}
//输出结果数组
System.out.print(result);
}
public static void main(String[]args){
//定义每一个node
Node n1=new Node("1");
Node n2=new Node("2");
Node n3=new Node("3");
Node n4=new Node("4");
Node n5=new Node("5");
Node n6=new Node("6");
Node n7=new Node("7");
Node n8=new Node("8");
//将每一个node加到List中
List<Node> list1=new ArrayList<Node>();
list1.add(null);
List<Node> list2=new ArrayList<Node>();
list2.add(n1);
List<Node> list3=new ArrayList<Node>();
list3.add(n1);
list3.add(n2);
List<Node> list4=new ArrayList<Node>();
list4.add(n2);
List<Node> list5=new ArrayList<Node>();
list5.add(n2);
list5.add(n3);
list5.add(n4);
List<Node> list6=new ArrayList<Node>();
list6.add(n5);
List<Node> list7=new ArrayList<Node>();
list7.add(n3);
List<Node> list8=new ArrayList<Node>();
list8.add(n3);
list8.add(n7);
//将定义的node和list加到map中，完成键图
Graph graph=new Graph();
graph.map.put(n1, list1);
graph.map.put(n2, list2);
graph.map.put(n3, list3);
graph.map.put(n4, list4);
graph.map.put(n5, list5);
graph.map.put(n6, list6);
graph.map.put(n7, list7);
graph.map.put(n8, list8);
Set<Node> keys=graph.map.keySet();
//遍历map中的node值，输出图
for(Node key:keys){
System.out.print("key="+key+" value="+graph.map.get(key)+"\n");
}
DAG dag=new DAG(graph);
dag.zeroIndegree.add(n1);
dag.Kahn();
}
}
class Node
{
String name;
public Node(String name){
this.name=name;
}
//toString方法使得输出为字符串而不是地址
public String toString(){
return name;
}
}
class Graph{
Map<Node,List<Node>> map=new HashMap<Node,List<Node>>();//建立一个Map叫map
}
5.运行结果
最后就是代码的运行结果啦：
输出邻接表以及拓扑排序 