图论之拓扑排序

CSDN

package com.zhang.reflection.面试.算法模版.图.拓扑排序;
/**
 * 1.有向无环图；
 * 2.序列里的每一个点只能出现一次；
 * 3.序列里的每一个点只能出现一次；3.任何一对 u 和 v ，u 总在 v 之前
 * （这里的两个字母分别表示的是一条线段的两个端点，u 表示起点，v 表示终点）；
 */
import java.util.*;
public class 拓扑排序 {
    //图
    static class Graph{
        //点集<编号，实际的点>
        public HashMap<Integer, Node> nodes;
        //边集
        public HashSet<Edge> edges;
        public Graph(){
            nodes=new HashMap<>();
            edges=new HashSet<>();
        }
    }
    //点
    static class Node{
        //点上的值
        public int value;
        //点的入度
        public int in;
        //点的出度
        public int out;
        //相邻节点集,以该节点为起点
        public ArrayList<Node> nexts;
        //相邻边集，以该节点为起点
        public ArrayList<Edge> edges;
        public Node(int value){
            this.value=value;
            in=0;
            out=0;
            nexts=new ArrayList<>();
            edges=new ArrayList<>();
        }
    }
    //边
    static class Edge{
        //边得权值
        public int weight;
        //边的起点
        public Node from;
        //边的终点
        public Node to;
        public Edge(int weight, Node from, Node to){
            this.weight=weight;
            this.from=from;
            this.to=to;
        }
    }
    //拓扑排序
    public static List<Node> sortedTopology(Graph graph){
        //放入节点以及节点对应的入度
        HashMap<Node,Integer> inMap=new HashMap<>();
        //将入度为0的节点放入队列
        Deque<Node> queue=new LinkedList<>();
        for(Node node:graph.nodes.values()){
            inMap.put(node,node.in);
            //找到入度为0的节点放入队列
            if(node.in==0){
                queue.offer(node);
            }
        }
        List<Node> result=new ArrayList<>();
        while(!queue.isEmpty()){
            Node cur=queue.poll();
            result.add(cur);
            for(Node next:cur.nexts){
                //将该节点的下面的节点的入度减1
                inMap.put(next,inMap.get(next)-1);
                //如果该节点的下面的节点的入度变为0则放入队列中
                if(inMap.get(next)==0){
                    queue.offer(next);
                }
            }
        }
        return result;
    }
}