1. 拓扑排序
题目描述：对一个有向无环图(Directed Acyclic Graph, DAG)G进行拓扑排序，是将G中所有顶点排成线性序列，是的图中任意一堆顶点u和v，若边(u, v)在E(G)中，则u在线性序列中出现在v之前。
如：
分析：
1）首先我们要将图G存入一个邻接矩阵中，保存该图；
2）计算每个顶点的入度，存储一个一维数组中；
3）从有向图中选择一个没有前驱（即入度为0）的节点并输出；
4）从图中删除该节点，并且删除从该节点发出的全部有向边；
5）重复上面两个步骤，直至剩余的图中不再存在没有前驱的节点为止。
进一步思考：
1）拓扑排序的本质是不断输出入度为0的点，这种方法可以用于判断图中是否有环；
2）拓扑排序其实给出的是节点之间的偏序关系；
Answer：
class TopologySort {
private int[][] aja = {{0,1,0,0,0,1,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,0,0,1,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0}};
public int[][] getEdge() {
return aja;
}
/**
* 该函数根据邻接矩阵计算每个节点的入度
* @param edge
* @return
*/
public int[] getInDegree(int[][] edge) {
int len = edge.length;
int[] inDegree = new int[len];
for(int j=0; j<len; j++) {
int count = 0;
for(int i=0; i<len; i++)
if(edge[i][j] == 1)
count++;
inDegree[j] = count;
}
return inDegree;
}
public List<Integer> topoSort(int[][] edge) {
List<Integer> res = new ArrayList<Integer>();
int len = edge.length;
int[] inDegree = getInDegree(edge);
Queue<Integer> q = new LinkedList<Integer>();
//将入度为0的节点压入队列中
for(int i=0; i<inDegree.length; i++)
if(inDegree[i] == 0) {
q.add(i);
res.add(i);
}
//对于队列中的元素（入度为0的元素）
while(!q.isEmpty()) {
int element = q.remove();
for(int j=0; j<len; j++) {
if(edge[element][j] == 1) {
inDegree[j]--;
if(inDegree[j] == 0) {
q.add(j);
res.add(j);
}
}
}
}
return res;
}
}