拓扑排序（java）

在一个有向图G中，将G中所有顶点排成一个线性序列，该序列满足这样的条件——对于图中的任意两个顶点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。
拓扑排序存在的前提：当且仅当一个图为有向无环图，才存在拓扑排序。

算法思路：

1. 从有向图中找到全部入度为0的顶点，并入队。
2. 删除队列中的一个顶点A，并输出。同时更新其他顶点的入度（即若存在A指向当前顶点的弧，则当前节点的入度减1）
3. 再次将更新后的入度为0的顶点入队，如此反复，直到队列为空。

代码

/**
 * 拓扑排序
 * @param vertexArray 顶点数组
 * @param adjacencyMatrix 邻接矩阵
 */
void topoSort(int[] vertexArray, int[][] adjacencyMatrix){
    if (vertexArray == null || vertexArray.length <= 0 || adjacencyMatrix == null || adjacencyMatrix.length <= 0) {
        return;
    }
    // 保存各个顶点的入度
    int[] inDegrees = new int[vertexArray.length];

    // 从邻接矩阵中计算各个顶点的入度
    for (int[] ind : adjacencyMatrix) {
        for (int i = 0 ; i <  ind.length; i ++) {
            if (ind[i] == 1) {
                inDegrees[i] ++;
            }
        }
    }

    Queue<Integer> queue = new LinkedList<>();
    List<Integer> topoResult = new ArrayList<>();

    // 将入度为0的顶点入队
    for (int i= 0; i < inDegrees.length; i++) {
        if (inDegrees[i] == 0) {
            queue.offer(i);
        }
    }

    while (!queue.isEmpty()) {
        int node = queue.poll(); // 顶点出队
        topoResult.add(vertexArray[node]);
        for (int i = 0; i < adjacencyMatrix[node].length; i++) {
            // 更新其他顶点的入度，若更新后的入度为0，则入队
            if (adjacencyMatrix[node][i] == 1) {
                inDegrees[i] --;
                if (inDegrees[i] == 0) {
                    queue.offer(i);
                }
            }

        }
    }

    // 判断有没有环
    if (topoResult.size() != vertexArray.length) {
        throw new RuntimeException("has circle!!");
    }

        // 打印拓扑排序结果
    for (int i : topoResult) {
        System.out.print(i + " ");
    }
    return;
}