数据结构

图的表示

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Graph {
    // 点集
    public Map<Integer, Node> nodes;
    // 边集
    public Set<Edge> edges;
    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
    public Graph(Map<Integer, Node> nodes, Set<Edge> edges) {
        this.nodes = nodes;
        this.edges = edges;
    }
}

点结构

import java.util.ArrayList;
import java.util.List;
public class Node {
    public int value;
    // 点的入度（有几个点指向该点）
    public int in;
    // 点的出度（指向了几个点）
    public int out;
    // 从该点发散出去的点（该点指向的 点）
    public List<Node> nexts ;
    // 属于该点的边（该点指向其他点的边）
    public List<Edge> edges;
    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

边结构

public class Edge {
    // 权重，一般情况下是指两个点之间的距离，也可以给与权重一些特殊的意义
    public int weight;
    // 有向边的 from点 和 to点，如果是无向图，可以使用两条有向边来表示无向边
    public Node from;
    public Node to;
    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

上图可表示为，注意这里按照上面的 Node 类是编译不过的……这么写是为了和上面的图片一致，如果改成数字结果是一样的

// 五个点
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
// 六条边
// A -> B
Edge edgeAB = new Edge(1, nodeA, nodeB);
// A -> C
Edge edgeAC = new Edge(1, nodeA, nodeC);
// B -> C
Edge edgeBC = new Edge(3, nodeB, nodeC);
// C -> E
Edge edgeCE = new Edge(3, nodeC, nodeE);
// D -> A
Edge edgeDA = new Edge(3, nodeD, nodeA);
// E -> D
Edge edgeED = new Edge(2, nodeE, nodeD);
// 点集
Map nodes = new HashMap();
nodes.put(0, nodeA);
nodes.put(1, nodeB);
nodes.put(2, nodeC);
nodes.put(3, nodeD);
nodes.put(4, nodeE);
// 边集
Set edges = new HashSet();
edges.add(edgeAB);
edges.add(edgeAC);
edges.add(edgeBC);
edges.add(edgeCE);
edges.add(edgeDA);
edges.add(edgeED);
// ================ NodeA ================
// 只有 nodeD 指向 nodeA
nodeA.in = 1;
// nodeA 指向 nodeB nodeC
nodeA.out = 2;
nodeA.nexts = Arrays.asList(nodeB, nodeC);
nodeA.edges = Arrays.asList(edgeAB, edgeAC);
// ================ NodeB ================
nodeB.in = 1;
nodeC.out = 1;
nodeB.nexts = Arrays.asList(nodeC);
nodeB.edges = Arrays.asList(edgeBC);
// ================ NodeC ================
nodeB.in = 2;
nodeC.out = 1;
nodeB.nexts = Arrays.asList(nodeE);
nodeB.edges = Arrays.asList(edgeCE);
// ================ NodeD ================
nodeB.in = 1;
nodeC.out = 1;
nodeB.nexts = Arrays.asList(nodeA);
nodeB.edges = Arrays.asList(edgeDA);
// ================ NodeE ================
nodeB.in = 1;
nodeC.out = 1;
nodeB.nexts = Arrays.asList(nodeD);
nodeB.edges = Arrays.asList(edgeED);
Graph graph = new Graph(nodes, edges);

图的存储方式

邻接表
邻接矩阵

无论是什么形式表示的图结构，都写一个函数来“加工”为以上代码数据结构，方便按照常见的步骤来解题
如：存在数组 [[1,0,5],[1,2,3],[0,2,7]] 每个数组的非别为 [form, to, weight]，就可以用如下方法加工为上面的数据结构

public class GraphGenerator {
    /**
     * 将特定结构转换为有向图
     *
     * @param matrix 所有的边 [form, to, weight]
     * @return
     */
    public static Graph getDigraph(int[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            int from = matrix[i][0];
            int to = matrix[i][1];
            int weight = matrix[i][2];

            if (!graph.nodes.containsKey(from))
                graph.nodes.put(from, new Node(from));

            if (!graph.nodes.containsKey(to))
                graph.nodes.put(to, new Node(to));

            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);

            Edge edge = new Edge(weight, fromNode, toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(edge);
            graph.edges.add(edge);
        }
        return graph;
    }

    /**
     * 将特定结构转换为无向图
     *
     * @param matrix 所有的边 [form, to, weight]
     * @return
     */
    public static Graph getUndirectedGraph(int[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            int from = matrix[i][0];
            int to = matrix[i][1];
            int weight = matrix[i][2];

            if (!graph.nodes.containsKey(from))
                graph.nodes.put(from, new Node(from));

            if (!graph.nodes.containsKey(to))
                graph.nodes.put(to, new Node(to));

            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);

            Edge edge = new Edge(weight, fromNode, toNode);
            fromNode.out++;
            fromNode.in++;
            fromNode.nexts.add(toNode);
            fromNode.edges.add(edge);

            Edge edge1 = new Edge(weight, toNode, fromNode);
            toNode.out++;
            toNode.in++;
            toNode.edges.add(edge1);
            toNode.nexts.add(fromNode);

            graph.edges.add(edge);
            graph.edges.add(edge1);
        }
        return graph;
    }
}

遍历

宽度优先

利用队列实现
从源节点开始依次按照宽度进队列，然后弹出
每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
直到队列变空 ```java import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Set;

public class BFS { public static void bfs(Node node) { if (node == null) return;

    Queue<Node> queue = new LinkedList<>();
    Set set = new HashSet();
    queue.add(node);
    set.add(node);

    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        for (Node next : cur.nexts) {
            if (!set.contains(next)) {
                queue.add(next);
                set.add(next);
            }
        }
    }
}

public static void main(String[] args) {
    Graph graph = GraphGenerator.getUndirectedGraph(new int[][]{{1, 0, 5}, {1, 2, 3}, {0, 2, 7}});
    bfs(graph.nodes.get(0));
}

}

<a name="uzpar"></a>
## 广度优先

1. 利用栈实现
1. 从源节点开始把节点按照深度放入栈，然后弹出
1. 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
1. 直到栈变空
```java
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class DFS {
    public static void dfs(Node node) {
        if (node == null) return;

        Stack<Node> stack = new Stack<>();
        Set<Node> set = new HashSet<>();

        stack.push(node);
        set.add(node);

        System.out.println(node.value);
        while (!stack.empty()) {
            Node cur = stack.pop();
            for (Node next : cur.nexts) {
                if (!set.contains(next)) {
                    // 这里需要将 当前节点 push 回去
                    stack.push(cur);
                    stack.push(next);
                    set.add(next);
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = GraphGenerator.getUndirectedGraph(new int[][]{{1, 0, 5}, {1, 2, 3}, {0, 2, 7}});
        dfs(graph.nodes.get(0));
    }
}

拓扑排序算法

使用范围：要求有向图，且有入度为 0 的节点，且没有环
如：在没有 SpringBoot 出现之前，如果需要搭建一个项目，就会出现如下情况
搭建项目A，项目中需要依赖的 jar 包有：B.jar、C.jar、D.jar。而 B.jar 需要依赖 D.jar、C.jar、E.jar。这样的话就必须按照一定的顺序才能搭建项目，而这些 jar 包间的关系就形成了下图的结构，项目中不能有循环依赖的情况，也就是说这个图是无环的

思路：

遍历图的所有节点 nodes，由于没有环，一定存在入度为 0 的 node（在上图中就是 A）找到后将该节点放入队列中
从队列中弹出节点，然后消除该节点“影响”，就是将和该节点连接的节点入度减一，在上图中就是 A 入队列，BCD三个节点的入度减一
循环执行第 1 步，直到队列为空
每次弹出的节点就是拓扑排序的结果 ```java import java.util.*;

public class TopologYSort {

public static List<Node> sort(Graph graph) {
    // <node， 入度>
    Map<Node, Integer> inMap = new HashMap<>();
    // 入度为 0 的点，进入队列
    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> list = new ArrayList<>();
    // 将入度为 0 的 node 弹出，并消除该 node 的影响
    while (!zeroInQueue.isEmpty()) {
        Node cur = zeroInQueue.poll();
        list.add(cur);
        for (Node node : cur.nexts) {
            inMap.put(node, inMap.get(node) - 1);
            if (inMap.get(node) == 0) zeroInQueue.add(node);
        }
    }
    return list;
}

}


<a name="PqSST"></a>
# 最小生成树

最小生成树：最小生成树其实是**最小权重生成树**的简称。一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/12779665/1619510351424-30aecc52-1280-4a19-ae9a-a0527d72a72d.png#align=left&display=inline&height=254&margin=%5Bobject%20Object%5D&name=image.png&originHeight=338&originWidth=738&size=44146&status=done&style=none&width=554)
<a name="faqJc"></a>
## Kruskal 算法

适用范围：**无向图**<br />思路：<br />将所有的边排序，将排序遍历，依次相加，如果新加入的边和已经相加的边形成了环就跳过。直到将所有的边遍历完，此时相加未成环的边就是是最小生成树

```java
import java.util.*;
import java.util.stream.Collectors;

public class Kruskal {

    static class MySet {
        public Map<Node, List<Node>> setMap;

        public MySet(List<Node> nodes) {
            setMap = new HashMap<>();
            for (Node node : nodes) {
                List<Node> set = new ArrayList<>();
                set.add(node);
                setMap.put(node, set);
            }
        }

        // 判断在集合中是否已经存在了
        public boolean isSameSet(Node from, Node to) {
            List<Node> fromSet = setMap.get(from);
            List<Node> toSet = setMap.get(to);
            return fromSet == toSet;
        }

        public void union(Node from, Node to) {
            List<Node> fromSet = setMap.get(from);
            List<Node> toSet = setMap.get(to);
            for (Node node : toSet) {
                fromSet.add(node);
                // 这样处理，所有 toSet 的 node 都会指向 fromSet
                setMap.put(node, fromSet);
            }
        }
    }

    public static Set<Edge> kruskalMST(Graph graph) {

        MySet mySet = new MySet(graph.nodes.values().stream().collect(Collectors.toList()));
        // 小根堆
        PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));

        for (Edge edge : graph.edges) {
            queue.add(edge);
        }

        Set<Edge> set = new HashSet<>();
        while (!queue.isEmpty()) {
            Edge edge = queue.poll();
            if (!mySet.isSameSet(edge.from, edge.to)) {
                set.add(edge);
                mySet.union(edge.from, edge.to);
            }
        }
        return set;
    }

    public static void main(String[] args) {
        // 这里 1，2，3，4 代表 A，B，C，D
        Node nodeA = new Node(1);
        Node nodeB = new Node(2);
        Node nodeC = new Node(3);
        Node nodeD = new Node(4);

        Edge edgeAB = new Edge(3, nodeA, nodeB);
        Edge edgeBA = new Edge(3, nodeB, nodeA);
        Edge edgeAC = new Edge(10, nodeA, nodeC);
        Edge edgeCA = new Edge(10, nodeC, nodeA);
        Edge edgeAD = new Edge(7, nodeA, nodeD);
        Edge edgeDA = new Edge(7, nodeD, nodeA);

        Edge edgeBC = new Edge(5, nodeB, nodeC);
        Edge edgeCB = new Edge(5, nodeC, nodeB);
        Edge edgeBD = new Edge(2, nodeB, nodeD);
        Edge edgeDB = new Edge(2, nodeD, nodeB);

        Edge edgeDC = new Edge(9, nodeD, nodeC);
        Edge edgeCD = new Edge(9, nodeC, nodeD);

        nodeA.nexts = Arrays.asList(nodeB,nodeC,nodeD);
        nodeB.nexts = Arrays.asList(nodeA,nodeC,nodeD);
        nodeC.nexts = Arrays.asList(nodeB,nodeA,nodeD);
        nodeD.nexts = Arrays.asList(nodeB,nodeA,nodeC);

        nodeA.edges = Arrays.asList(edgeAB, edgeBA, edgeAC, edgeCA, edgeAD, edgeDA);
        nodeB.edges = Arrays.asList(edgeBA, edgeAB, edgeBC, edgeCB, edgeBD, edgeDB);
        nodeC.edges = Arrays.asList(edgeCA, edgeAC, edgeCB, edgeBC, edgeCD, edgeDC);
        nodeD.edges = Arrays.asList(edgeDA, edgeAD, edgeDB, edgeBD, edgeDC, edgeCD);

        Map<Integer, Node> nodes = new HashMap<>();
        nodes.put(1, nodeA);
        nodes.put(2, nodeB);
        nodes.put(3, nodeC);
        nodes.put(4, nodeD);

        Set<Edge> edges = new HashSet<>();
        edges.add(edgeAB);
        edges.add(edgeBA);
        edges.add(edgeAC);
        edges.add(edgeCA);
        edges.add(edgeAD);
        edges.add(edgeDA);
        edges.add(edgeBC);
        edges.add(edgeCB);
        edges.add(edgeBD);
        edges.add(edgeDB);
        edges.add(edgeDC);
        edges.add(edgeCD);

        Graph graph = new Graph();
        graph.nodes = nodes;
        graph.edges = edges;

        Set<Edge> res = kruskalMST(graph);
        for (Edge edge : res) {
            System.out.println(edge.weight);
        }
    }
}

运行结果

3
5
2

Prim 算法

适用范围：无向图
存在如下的图求最小生成树

思路：
随机选择一个点，如 A

A 通过 AB、AC、AD 和其他的点相连，选权重最小的边 AC，并把点A、点C 视为一个点AC
点AC 通过 CB、CD、CE、CF 和其他节点相连，选权重最小的边 CF，并把点AC、点F 视为一个点ACF
点ACF 通过 FE、FD 和其他节点相连，选权重最小的边 FD，并把点ACF、点D 视为一个点ACFD
点ACFD 通过 CB、CE 和其他节点相连，选权重最小的边 CB，并把点ACFD、点B 视为一个点ACFDB
点ACFDB 通过 BE 和其他节点相连，选权重最小的边 BE，并把点ACFDB、点E 视为一个点ACFDBE
最小生成树完成，结束了

import java.util.*;

public class Prim {

    public static Set<Edge> primMST(Graph graph) {
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
        Set<Node> set = new HashSet<>();

        Set<Edge> result = new HashSet<>();

        // 这里使用所有的点进行循环，主要是排除一种特殊情况：一个图是有几个互不连通的新图组成
        // 如果确认不会出现这种情况，完全可用没有下面的这个 for 循环
        for (Node node : graph.nodes.values()) {
            // 随机拿一个点做起点
            if (!set.contains(node)) {
                set.add(node);
                for (Edge edge : node.edges) {
                    priorityQueue.add(edge);
                }

                while (!priorityQueue.isEmpty()) {
                    // 权重最小的边
                    Edge edge = priorityQueue.poll();
                    Node to = edge.to;
                    if (!set.contains(to)) {
                        // 不包含，说明这个点没有被视为和起点为 “同一个点”
                        set.add(to);
                        result.add(edge);
                        // 将该点和其他点连接的边放入队列
                        for (Edge nextEdge : to.edges) {
                            priorityQueue.add(nextEdge);
                        }
                    }
                }
            }
        }
        return result;
    }
}

最短路径

点 A 到其他点的最短距离为

B：A -> B 3
C：A -> B -> C 5
D：A -> D 9
E：A -> B -> C -> E 19
Dijkstra 算法

迪克斯特拉算法

适用范围：没有权值为负的边

思路：
假设 A 到其他点的距离为图 - 图5 ，A 到 A 的距离为 0，初始时，A 到所有点的最短距离为

	A	B	C	D	E
A 到该点的最短路径	0

然后看 A 的边有没有让 A 到某点的距离变小，如果有就更新/保存最短路径

	A	B	C	D	E
A 到该点的最短路径	0	3	15	9

A 点已经被使用过了，将 A 锁定，从其他记录中选出最短的路径 B，B 的边有没有让 A 到某点的距离变小，如果有就更新/保存最短路径

A -> B -> C : 3 + 2 < 15 更新
A -> B -> E : 3 + 200 < 更新 | | A | B | C | D | E | | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | | A 到该点的最短路径 | 0 | 3 | 5 | 9 | 203 |

B 点已经被使用过了，将 B 锁定，从其他记录中选出最短的路径 C，C 的边有没有让 A 到某点的距离变小，如果有就更新/保存最短路径

A -> B -> C -> D : 5 + 7 > 9 不更新
A -> B -> C -> E : 5 + 14 < 203 更新 | | A | B | C | D | E | | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | | A 到该点的最短路径 | 0 | 3 | 5 | 9 | 19 |

C 点已经被使用过了，将 C 锁定，从其他记录中选出最短的路径 D，D 的边有没有让 A 到某点的距离变小，如果有就更新/保存最短路径

A -> B -> C -> D -> E : 9 + 16 > 9 不更新

D 点已经被使用过了，将 D 锁定，从其他记录中选出最短的路径 E，E 的边有没有让 A 到某点的距离变小，如果有就更新/保存最短路径
E 点已经被使用过了，将 E 锁定。完成

import java.util.*;

public class Dijkstral {
    public static Map<Node, Integer> dijkstral(Node node) {
        // key：从 head 出发到的 点
        // value：最短距离
        Map<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(node, 0);

        // 起到了“锁定”的功能
        Set<Node> set = new HashSet<>();

        PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
        queue.addAll(node.edges);
        while (!queue.isEmpty()) {
            // 最短的边
            Edge edge = queue.peek();

            // 锁定当前点，本次就会计算出最短距离，之后不需要计算
            set.add(edge.from);
            // 遍历所有的边，判断是否需要更新最短距离
            while (!queue.isEmpty()) {
                Edge curEdge = queue.poll();
                // 点 A 到该点的最短距离
                Integer weightCount = distanceMap.get(curEdge.from);

                if (distanceMap.get(curEdge.to) == null) {
                    distanceMap.put(curEdge.to, curEdge.weight);
                } else {
                    // 如果 点 A 到该点的最短距离 + 权重 < 记录的最短距离 就更新
                    if (curEdge.weight + weightCount < distanceMap.get(curEdge.to)) {
                        distanceMap.put(curEdge.to, curEdge.weight + weightCount);
                    }
                }
            }
            for (Edge e : edge.to.edges) {
                if (set.contains(e.to)) continue;
                queue.add(e);
            }
        }
        return distanceMap;
    }

    public static void main(String[] args) {
        Node nodeA = new Node(1);
        Node nodeB = new Node(2);
        Node nodeC = new Node(3);
        Node nodeD = new Node(4);
        Node nodeE = new Node(5);

        Edge edgeAB = new Edge(3, nodeA, nodeB);
        Edge edgeBA = new Edge(3, nodeB, nodeA);
        Edge edgeAC = new Edge(15, nodeA, nodeC);
        Edge edgeCA = new Edge(15, nodeC, nodeA);
        Edge edgeAD = new Edge(9, nodeA, nodeD);
        Edge edgeDA = new Edge(9, nodeD, nodeA);
        Edge edgeBC = new Edge(2, nodeB, nodeC);
        Edge edgeCB = new Edge(2, nodeC, nodeB);
        Edge edgeBE = new Edge(200, nodeB, nodeE);
        Edge edgeEB = new Edge(200, nodeE, nodeB);
        Edge edgeCD = new Edge(7, nodeC, nodeD);
        Edge edgeDC = new Edge(7, nodeD, nodeC);
        Edge edgeCE = new Edge(14, nodeC, nodeE);
        Edge edgeEC = new Edge(14, nodeE, nodeC);
        Edge edgeDE = new Edge(16, nodeD, nodeE);
        Edge edgeED = new Edge(16, nodeE, nodeD);

        nodeA.nexts = Arrays.asList(nodeB, nodeC, nodeD);
        nodeA.edges = Arrays.asList(edgeAB, edgeAC, edgeAD);
        nodeB.nexts = Arrays.asList(nodeA, nodeC, nodeE);
        nodeB.edges = Arrays.asList(edgeBA, edgeBC, edgeBE);
        nodeC.nexts = Arrays.asList(nodeA, nodeB, nodeD, nodeE);
        nodeC.edges = Arrays.asList(edgeCA, edgeCB, edgeCD, edgeCE);
        nodeD.nexts = Arrays.asList(nodeA, nodeC, nodeE);
        nodeD.edges = Arrays.asList(edgeDA, edgeDC, edgeDE);
        nodeE.nexts = Arrays.asList(nodeB, nodeC, nodeD);
        nodeE.edges = Arrays.asList(edgeEB, edgeEC, edgeED);

        Map<Node, Integer> dijkstral = dijkstral(nodeA);
        for (Map.Entry<Node, Integer> entry : dijkstral.entrySet()) {
            System.out.println(nodeA.value + " - " + entry.getKey().value + " 最短距离为： " + entry.getValue());
        }
    }
}

结果：使用 1、2、3、4、5 表示 A、B、C、D、E

1 - 5 最短距离为： 19
1 - 3 最短距离为： 5
1 - 1 最短距离为： 0
1 - 4 最短距离为： 9
1 - 2 最短距离为： 3

优化

使用堆结构来优化，使用一个小根堆，每次都会自动取出最小的距离

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Dijkstral1 {

    /**
     * 维护一个小跟堆
     */
    static class NodeHeap {
        private Node[] nodes;
        // 堆当前大小
        private int size;
        // node 对应 nodes 的下标
        private Map<Node, Integer> heapIndexMap;
        // node 的距离
        private Map<Node, Integer> distanceMap;

        public NodeHeap(int size) {
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            this.size = 0;
        }


        /**
         * 如果第一次出现 ==> add
         * 已经存在并且新值更小 ==> update
         * 已经存在 新值没有更小 ==> ignore
         *
         * @param node
         * @param distance
         */
        public void addOrUpdateOrIgnore(Node node, int distance) {
            if (inHeap(node)) {
                distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                insertHeapify(node, heapIndexMap.get(node));
            }
            if (!isEntered(node)) {
                nodes[size] = node;
                heapIndexMap.put(node, size);
                distanceMap.put(node, distance);
                insertHeapify(node, size++);
            }
        }

        // node 是否进入过堆
        private boolean isEntered(Node node) {
            return heapIndexMap.containsKey(node);
        }

        private void insertHeapify(Node node, Integer index) {
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapify(int i, int size) {
            // 左子节点
            int left = i * 2 + 1;

            while (left < size) {
                // 右子节点
                int right = left + 1;
                int largestIndex = right < size && nodes[right].value > nodes[left].value ? right : left;
                largestIndex = nodes[largestIndex].value > nodes[i].value ? largestIndex : i;
                if (largestIndex == i) break;
                swap(largestIndex, i);
                i = largestIndex;
                left = i * 2 + 1;
            }
        }

        private boolean inHeap(Node node) {
            return isEntered(node) && heapIndexMap.get(node) != -1;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public NodeRecord pop() {
            NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
            size--;
            swap(0, size);
            // 弹出的节点 记录下标为 -1，这样即使是已经弹出的节点也能记录该点曾经进入过堆
            heapIndexMap.put(nodes[size], -1);
            distanceMap.remove(nodes[size]);
            nodes[size] = null;
            heapify(0, size);
            return nodeRecord;
        }

        private void swap(int i, int i1) {
            heapIndexMap.put(nodes[i], i1);
            heapIndexMap.put(nodes[i1], i);
            Node temp = nodes[i];
            nodes[i] = nodes[i1];
            nodes[i1] = temp;
        }
    }

    private static class NodeRecord {
        public Node node;
        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    public static Map<Node, Integer> dijkstral(Node head, int size) {
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(head, 0);

        Map<Node, Integer> result = new HashMap<>();

        while (!nodeHeap.isEmpty()) {
            NodeRecord record = nodeHeap.pop();
            Node cur = record.node;

            int distance = record.distance;
            result.put(cur, distance);

            for (Edge edge : cur.edges) {
                // 堆的天然好处，不会去更新已经确定的最短距离
                nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Node nodeA = new Node(1);
        Node nodeB = new Node(2);
        Node nodeC = new Node(3);
        Node nodeD = new Node(4);
        Node nodeE = new Node(5);

        Edge edgeAB = new Edge(3, nodeA, nodeB);
        Edge edgeBA = new Edge(3, nodeB, nodeA);
        Edge edgeAC = new Edge(15, nodeA, nodeC);
        Edge edgeCA = new Edge(15, nodeC, nodeA);
        Edge edgeAD = new Edge(9, nodeA, nodeD);
        Edge edgeDA = new Edge(9, nodeD, nodeA);
        Edge edgeBC = new Edge(2, nodeB, nodeC);
        Edge edgeCB = new Edge(2, nodeC, nodeB);
        Edge edgeBE = new Edge(200, nodeB, nodeE);
        Edge edgeEB = new Edge(200, nodeE, nodeB);
        Edge edgeCD = new Edge(7, nodeC, nodeD);
        Edge edgeDC = new Edge(7, nodeD, nodeC);
        Edge edgeCE = new Edge(14, nodeC, nodeE);
        Edge edgeEC = new Edge(14, nodeE, nodeC);
        Edge edgeDE = new Edge(16, nodeD, nodeE);
        Edge edgeED = new Edge(16, nodeE, nodeD);

        nodeA.nexts = Arrays.asList(nodeB, nodeC, nodeD);
        nodeA.edges = Arrays.asList(edgeAB, edgeAC, edgeAD);
        nodeB.nexts = Arrays.asList(nodeA, nodeC, nodeE);
        nodeB.edges = Arrays.asList(edgeBA, edgeBC, edgeBE);
        nodeC.nexts = Arrays.asList(nodeA, nodeB, nodeD, nodeE);
        nodeC.edges = Arrays.asList(edgeCA, edgeCB, edgeCD, edgeCE);
        nodeD.nexts = Arrays.asList(nodeA, nodeC, nodeE);
        nodeD.edges = Arrays.asList(edgeDA, edgeDC, edgeDE);
        nodeE.nexts = Arrays.asList(nodeB, nodeC, nodeD);
        nodeE.edges = Arrays.asList(edgeEB, edgeEC, edgeED);

        Map<Node, Integer> dijkstral = dijkstral(nodeA, 5);
        for (Map.Entry<Node, Integer> entry : dijkstral.entrySet()) {
            System.out.println(nodeA.value + " - " + entry.getKey().value + " 最短距离为： " + entry.getValue());
        }
    }

}