图-有向无环图拓扑排序算法

2022-4-14 diaba 算法 

package com.jiucaiyuan.net.algrithm.graph;

import java.util.*;

/**
 * 有向无环图拓扑排序（DAG：Direct Acyclic Graph）
 *
 * 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说
 *
 * @Author jiucaiyuan  2022/4/14 22:20
 * @mail services@jiucaiyuan.net
 */

public class TopologySort {
    /**
     * directed graph and no loop
     * 有向图图拓扑排序
     * 适用范围：有向无环图
     * 思路：从入度为0的节点触发，抹掉入度为0的节点，剩下的节点入度更新，再找到入度为0的节点，再次抹掉，再次更新
     * @param graph  有向图 & 存在入度为0的节点 & 无环
     * @return 拓扑排序结果
     */
    public static List<Node> sortedTopology(Graph graph){
        //<节点，该节点的剩余入度>   去除一个节点后，会把该节点的影响全部抹掉
        HashMap<Node,Integer> inMap = new HashMap<>();
        //入度为0的节点队列
        Queue<Node> zeroInQueue = new LinkedList<>();
        //初始化，图中所有节点都处理一遍，记录所有节点的入度以及入度为0的节点
        for(Node currNode : graph.nodes.values()){
            inMap.put(currNode,currNode.in);
            if(0 == currNode.in){
                zeroInQueue.add(currNode);
            }
        }
        //拓扑排序结果集
        List<Node> result = new ArrayList<>();
        //入度为0的节点开始处理，处理过程中有入度为0的节点都入队
        while (!zeroInQueue.isEmpty()){
            Node curr = zeroInQueue.poll();
            result.add(curr);
            //抹掉当前入度为0的节点，后续受影响的节点的入度更新，如果再次产生入度为0的节点进入队列
            for(Node next:curr.nexts){
                inMap.put(next,inMap.get(next) - 1);
                if(inMap.get(next) == 0){
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}

« 算法-前缀树（单词查找树） | 图-最短路径-Dijkstra算法»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022