拓扑排序算法

08/05 15:30
阅读数 15
/**
     * 拓扑排序算法,拓扑都是有向无环图
     * 使用场景:编译的时候,比如,springboot启动的时候要读取docker系统环境变量,还要读取各配置文件按照顺序
     * 还有比如,a的包依赖b包,a,b包各有自己的配置文件,按照依赖顺序依次读取,所以不要循环依赖
     * 拓扑排序就是从最底层开始编译,往上编译,才能编译成功
     * 算法过程:依次找入度为0的点,依次删掉
     */
    public static List<Node> sortedTopology(Graph graph) {
        //<某个Node,剩余的入度>
        Map<Node, Integer> inMap = new HashMap<>();
        //剩余入度为0的点,才能进这个队列
        Deque<Node> zeroInQueue = new LinkedList<>();

        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroInQueue.add(node);
            }
        }

        List<Node> res = new ArrayList<>();
        while (!zeroInQueue.isEmpty()) {
            Node poll = zeroInQueue.poll();
            res.add(poll);
            //消除删掉节点的影响
            for (Node next : poll.nexts) {
                inMap.put(next, inMap.get(next) - 1);
                if (inMap.get(next) == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return res;
    }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部