一、图

基本模板

Graph

public class Graph {
    public HashMap<Integer,Node> nodes;
    public HashSet<Edge> edges;

    public Graph() {
        nodes = new HashMap<Integer,Node>();
        edges = new HashSet<>();
    }
}

Edge

public 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;
    }
}

Node

public 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<>();
    }
}

遍历

广度优先

/**
 * 图的广度优先遍历
 * 使用队列，为了保证不重复遍历，所以使用了set进行重复判断
 */
public static void BFS(Node node){
    Queue<Node> queue = new LinkedList<>();
    HashSet<Node> set = new HashSet<>();
    queue.add(node);
    set.add(node);
    while (! queue.isEmpty()){
        //弹出打印
        Node poll = queue.poll();
        System.out.print(poll.value+" ");
        //获取节点的next点
        ArrayList<Node> nexts = poll.nexts;
        for (Node next: nexts){
            //是否在set中
            if (! set.contains(next)){
                set.add(next);
                queue.add(next);
            }
        }
    }

}

深度优先

/**
 * 图的深度优先遍历
 * 准备栈和set集合
 * 在添加元素进入set时，就处理打印
 * 步骤L
 * 依次弹出栈一直到空
 *  获取node的next,遍历next,判断next是否在set中
 *      1.在set中，继续判断下一个next
 *      2.不在set中，将本node和该next压入栈，然后将next加入到set，再处理打印set
 *
 */
public static void DFS(Node node){
    Stack<Node> stack = new Stack<>();
    HashSet<Node> set = new HashSet<>();
    stack.add(node);
    set.add(node);
    System.out.print(node.value+" ");
    while (!set.isEmpty()){
        Node pop = stack.pop();
        ArrayList<Node> nexts = pop.nexts;
        for (Node next: nexts){
            //不在set中
            if (!set.contains(next)){
                //将原node和该next压入栈
                stack.push(pop);
                stack.push(next);
                set.add(next);
                System.out.print(next.value+" ");
                //不在处理后面的next节点，退出进行深度遍历
                break;
            }
        }

    }

}

拓扑排序

/**
 * 拓扑排序
 * 准备HashMap容器，记录每个点的入度
 * 准备queue容器用来实现遍历
 * 将所有node遍历，将每个点的入度对应记录在map中
 *      此时然后将入度为零的点加入到queue中，
 * 遍历从queue开始，遍历到的点，那么该点的nexts中的next点入度--,更新map
 *      更新后，如果该点入度为0,加入到queue中
 * 循环至queue为空
 */
public static List<Node> TopologySort(Graph graph){
    List<Node> result = new ArrayList<>();
    HashMap<Node,Integer> inMap = new HashMap<>();
    Queue<Node> zeroInQueue = new LinkedList<>();
    //node遍历，将每个点的入度对应记录在map中
    for (Node node: graph.nodes.values()){
        inMap.put(node,node.in);
        if (node.in == 0){
            zeroInQueue.add(node);
        }
    }
    //遍历queue
    while (!zeroInQueue.isEmpty()){
        Node poll = zeroInQueue.poll();
        result.add(poll);
        //该点的nexts中的next点入度--,更新map
        for (Node next: poll.nexts){
            //入度更新
            Integer in = inMap.get(next);
            inMap.put(next,in--);
            //入度为0,加入到queue中
            if (in == 0){
                zeroInQueue.add(next);
            }
        }
    }
    return result;
}

Kruskal最小生成树

public class Kruskal {
    public static class MySets{
        //每个节点的所属集合
        private HashMap<Node, List<Node>> setMap;

        //构造
        public MySets(List<Node> nodes){
            for (Node node: nodes){
                //每个节点初始所属集合中只有自己
                List<Node> list = new ArrayList<>();
                list.add(node);
                //为属性赋值
                setMap.put(node,list);
            }
        }
        //接口：判断是否在同一集合中
        public boolean isSameSet(Node from,Node to){
            List<Node> fromList = setMap.get(from);
            List<Node> toList = setMap.get(to);
            return fromList == toList;
        }
        //接口：将集合合并
        public void unionSet(Node from,Node to){
            List<Node> fromList = setMap.get(from);
            List<Node> toList = setMap.get(to);
            //将toList中的节点加入到from集合中，
            //并且！ 更改to集合节点所属
            for (Node node: toList){
                fromList.add(node);
                setMap.put(node,fromList);
            }
        }

    }

    /**
     * kruskal算法最小生成树
     * 接口：1.是否处于一个集合
     *      2.将集合合并
     *
     * 按照边的权值从小到大开始连接图，查看时候会出现环（也就是对应代码中两个节点的所属集合是同一个）
     * 如果在连接后出现环，则不连接
     * 如果不出现环，则连接，并更新from节点的所属集合（将集合合并，用于判断环），将节点添加到结果集中
     */
    public static Set<Edge> kruskalMST(Graph graph){
        List<Node> list = (List<Node>) graph.nodes.values();
        //初始化mysets
        MySets mySets = new MySets(list);
        //按照边的权值大小，加入到queue中并排序
        PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x.weight));
        queue.addAll(graph.edges);
        //结果集
        Set<Edge> result = new HashSet<>();

        while (! queue.isEmpty()){
            Edge edge = queue.poll();
            //不在一个集合中
            if (!mySets.isSameSet(edge.from, edge.to)){
                //则连接，并更新from节点的所属集合
                result.add(edge);
                mySets.unionSet(edge.from,edge.to);
            }
        }
        return result;
    }
}

Prim

/**
 * 准备queue用来遍历
 * 准备set用来判断是否已经加入过
 * 先将所有边从小到大加入到queue中
 * 循环：从queue中取出边，判断该边的目的点是否已经在set中（k算法在此步是判断是否会成环）
 *      如果不在set中，则说明没有，加入到set中，并且将该点的edges加入到queue中，此时会产生重复，但set会判断
 *      如果在set中，弹出下一个，继续循环
 */
public static Set<Edge> primMST(Graph graph) {
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(x -> x.weight));
    //判断旧值是否添加过
    HashSet<Node> set = new HashSet<>();
    Set<Edge> result = new HashSet<>();
    //循环是防止图为森林，可以不加
    for (Node node : graph.nodes.values()) {
        if (!set.contains(node)) {
            set.add(node);

            //在队列中加入所有边，排序
            priorityQueue.addAll(node.edges);
            while (!priorityQueue.isEmpty()) {
                //弹出最小权值的边
                Edge edge = priorityQueue.poll();
                Node toNode = edge.to;
                //toNode没加入过set
                if (!set.contains(toNode)) {
                    //加入set
                    set.add(toNode);
                    result.add(edge);
                    //结果集中再加入该node的边（会有重复边，但是set会将已经添加过的点忽略）
                    priorityQueue.addAll(toNode.edges);
                }
            }


        }
    }
    return result;
}

Dijkstra

public class Dijkstra {    /**     *  准备一个hashMap用来维持，源点到该node的最短路径,     *  准备一个set，用来表示已经锁住的node     *     *  步骤：     *  将源节点的对应路径加入map     *  从这些路径中找到最小权值的边，获取对应的node     *  获取node的edege对应的toNode     *      如果toNode不在map中，说明距离为无穷大，直接更新距离为 源到该node+node到toNode的距离     *      如果在map中，判断  源到该node+node到toNode的距离  和 原来源到该toNode的距离大小     *       如果原来大，则不更新，反之更新最小路径     *  遍历完该node的所有边后，就将该node加入到set中，代表已经扫描过，后续不在扫描     *     *  重新从这些路径中找到最小权值的边，获取对应的node     *     */    public static HashMap<Node, Integer> dijkstra1(Node head) {        //源点到该node的最短路径        HashMap<Node,Integer> map = new HashMap<>();        //锁住的node        HashSet<Node> set = new HashSet<>();        //加入第一个节点到map中，到自己的距离为零        map.put(head,0);        //获取最小权值的node        Node minNode = getMinDisUnSelect(map, set);        //能获取到没被锁定的权值最小边        while (minNode != null){            int distance = map.get(minNode);            for (Edge edge: minNode.edges){                //获取node的edeges对应的toNode                Node toNode = edge.to;                //不在map中                if (!map.containsKey(toNode)){                    map.put(toNode, distance+edge.weight);                }                else {                    map.put( toNode,Math.min( distance+edge.weight,map.get(toNode) ) );                }            }            //当前节点完成遍历，加入到被锁set中            set.add(minNode);            //再获取一个minNode            minNode = getMinDisUnSelect(map, set);        }        return map;    }    //从没有被锁定的点中，获取权值最小的边，并返回对应节点    public static Node getMinDisUnSelect(HashMap<Node,Integer> map,HashSet<Node> set){        int minDistance = Integer.MAX_VALUE;        Node minNode = null;        for (Entry<Node,Integer> entry: map.entrySet()){            Node node = entry.getKey();            int distance = entry.getValue();            //没被锁住，并且较小            if (! set.contains(node) && distance<minDistance){                minNode = node;                minDistance = distance;            }        }        return minNode;    }}