Queue 应用——拓扑排序

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;

    }

}

巴特西

Queue 应用——拓扑排序

最新文章

热门文章