拓扑排序

作者: 一凡呀 | 来源:发表于2017-11-27 21:59 被阅读0次

概念:

对一个有向无环图简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前

思路:

用一个队列存入度为零的节点,用一个HashMap存储节点和其入度,先把图中所有的节点入map,然后把入度为零的点入队列,然后当队列不是空的时候,首先弹出队列的顶,加入到结果list里,然后把这个节点所影响的所有点的入度减去一,如果减去一后后继节点的in为0就加入到存入度为零的队列中去,依次反复即可

代码:

// directed graph and no loop
    public static List<Node> sortedTopology(Graph graph) {
        HashMap<Node, Integer> inMap = new HashMap<>();
        Queue<Node> zeroInQueue = new LinkedList<>();
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroInQueue.add(node);
            }
        }
        List<Node> result = new ArrayList<>();
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            result.add(cur);
            for (Node next : cur.nexts) {
                inMap.put(next, inMap.get(next) - 1);
                if (inMap.get(next) == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }

相关文章

网友评论

    本文标题:拓扑排序

    本文链接:https://www.haomeiwen.com/subject/girjbxtx.html