一、概念

图（Graph）是用于示意物体与物体之间存在某种关系的构造。数学形象后的“物体”称作节点或顶点（Vertex，node或point），节点间的相干关系则称作边。在描述一张图的时候，通常用一组点或小圆圈示意节点，其间的边则应用直线或曲线。

1、有向图和无向图

图中的边能够是有方向或没有方向的。

例如在一张图中，如果节点示意团聚上的人，而边示意两人已经握手，则该图就是没有方向的，因为甲和乙握过手也意味着乙肯定和甲握过手。相同，如果一条从甲到乙的边示意甲欠乙的钱，则该图就是有方向的，因为“已经欠钱”这个关系不肯定是双向的。前一种图称为无向图，后一种称为有向图。

同时，无向图也能够认为是有向图，即能够设想成两个节点之间有从A到B的边，也有B到A的边，所以从宽泛的角度能够认为所有图都是有向图。

二、图的示意

教材上的表示法：邻接表、邻接矩阵

1、邻接表

2、邻接矩阵

如果图G有n个节点，则邻接矩阵是一个 n*n 的矩阵，定义为：

G[ i ][ j ] = 1（或权重值），若<Vi, Vj>是G中的边；否则G[ i ][ j ] = 无穷大。对于对角线的设置，视状况具体设置。

3、常见的表示法

以上两种表示法在理论刷题的过程中简直不会遇到。

更多的是给你一个 n*3 的矩阵[ [weight, fromNode, toNode] ]，例如[ [3, A, B], [2, B, M], [5, A, R] ]，第一个值示意权重，第二个值示意from节点，第三个值示意to节点。也就是一条边一条边的间接示意。

三、图的解决思路

图的算法都不算难，只不过coding的代价比拟高

（1）先用本人最纯熟的形式，实现图构造的表白

（2）在本人相熟的构造上，实现所有罕用的图算法作为模板

（3）把面试题提供的图构造转化为本人相熟的图构造，再调用模板或改写即可

图的示意办法这么多种，并且每次给你的模式还可能不同，所以就有必要形象一个本人的示意办法，当前对于不同的模式，写一个能转换为本人定义模式的办法即可（有种适配器的感觉），这样能力以不变应万变，把不相熟的示意办法转换为本人相熟的办法

/** * 自定义图的信息 * * @author Java和算法学习：周一 */public class Graph {    /**     * 点集，Key：用户给的点，Value：自定义点信息     */    public HashMap<Integer, Node> nodes;    /**     * 边集     */    public HashSet<Edge> edges;    public Graph() {        this.nodes = new HashMap<>();        this.edges = new HashSet<>();    }    /**     * 将用户输出的示意边的 N*3 的矩阵转换为自定义的图     *     * @param matrix N*3 的矩阵，[3, 0, 5], [2, 2, 5]     */    public static Graph createGraph(int[][] matrix) {        Graph graph = new Graph();        for (int[] m : matrix) {            // 拿到用户给的边的权重信息、边的from、to节点            int weight = m[0];            int from = m[1];            int to = m[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.edges.add(edge);            // 入度、出度批改            fromNode.out++;            toNode.in++;            // 增加图的边集信息            graph.edges.add(edge);        }        return graph;    }}

四、图的宽度优先和深度优先遍历

1、宽度优先遍历

（1）筹备一个队列，一个Set（寄存遍历过的节点，登记表），登程节点为A，把A放到队列和Set中

（2）弹出队列的顶点M，打印M的值。获取M的所有街坊节点next，查看Set中有没有这些next节点，无则放到Set和队列中，有则跳过此next节点

（3）始终执行第2步，直到队列为空

/** * 图的宽度优先遍历 * * @author Java和算法学习：周一 */public static void bfs(Node node) {    if (node == null) {        return;    }    Node current = node;    Queue<Node> queue = new LinkedList<>();    HashSet<Node> set = new HashSet<>();    queue.add(current);    set.add(current);    while (!queue.isEmpty()) {        current = queue.poll();        System.out.println(current.value);        for (Node next : current.nexts) {            if (!set.contains(next)) {                queue.add(next);                set.add(next);            }        }    }}

2、深度优先遍历

一条路没走完就始终走，走完了就往回走，看哪些岔路还没有走。（不能走出环路，走过的中央就不能再走了）

（1）筹备一个栈（寄存目前的整条门路），一个Set（寄存遍历过的节点，登记表），登程节点为A，把A放到栈和Set中，同时打印A的值（入栈就打印）

（2）弹出栈顶元素M，遍历M的所有街坊节点next，查看Set中有没有这些next节点，无则将M和此时的next节点入栈、next放到Set中，打印next的值（入栈就打印），终止遍历next节点（即只入栈一个Set中不蕴含的节点）

（3）始终执行第2步，直到栈为空

/** * 图的深度优先遍历 * * @author Java和算法学习：周一 */public static void dfs(Node node) {    if (node == null) {        return;    }    Stack<Node> stack = new Stack<>();    HashSet<Node> set = new HashSet<>();    Node current = node;    stack.add(current);    set.add(current);    // 入栈就打印    System.out.println(current.value);    while (!stack.isEmpty()) {        current = stack.pop();        for (Node next : current.nexts) {            if (!set.contains(next)) {                stack.add(current);                stack.add(next);                set.add(next);                System.out.println(next.value);                // 只入栈一个Set中不蕴含的节点                break;            }        }    }}

3、图的拓扑排序

有向无环图才有拓扑排序

（1）打印以后图中入度为0的节点（多个为0，先打印谁均可）

（2）从图中移除曾经打印的节点（天然，这些节点间接连贯的边也移除）

（3）始终执行1、2步，直到图的节点为空

/** * 图的拓扑排序 * * @author Java和算法学习：周一 */public static List<Node> topologySort(Graph graph) {    // Key：节点，Value：残余入度    HashMap<Node, Integer> inMap = new HashMap<>();    // 寄存入度为0的节点    Queue<Node> zeroInQueue = new LinkedList<>();    for (Node node : graph.nodes.values()) {        // 将最后给定的图中所有节点放到inMap中        inMap.put(node, node.in);        if (node.in == 0) {            // 最后入度为0的节点            zeroInQueue.add(node);        }    }    List<Node> result = new ArrayList<>();    while (!zeroInQueue.isEmpty()) {        Node current = zeroInQueue.poll();        result.add(current);        for (Node next : current.nexts) {            // 将曾经遍历过的节点的街坊节点的入度减一（能够了解为从图中移除current节点）            inMap.put(next, inMap.get(next) - 1);            if (inMap.get(next) == 0) {                // 批改后的节点入度为0，放到zeroInQueue队列中                zeroInQueue.add(next);            }        }    }    return result;}

五、最小生成树算法

要求是无向图，在所有点都连通的状况下，所有权重值加起来最小的边造成的树。

1、Kruskal算法

应用并查集

（1）总是从权值最小的边开始找，顺次找权值顺次变大的边（权值相等任选其一）

（2）如果以后的边进入最小生成树的汇合中不会造成环，就要以后边；否则舍弃

（3）找完所有边之后，最小生成树的汇合也就失去了

/** * Kruskal算法——应用并查集 * * @author Java和算法学习：周一 */public static Set<Edge> kruskal(Graph graph) {    UnionFind unionFind = new UnionFind(graph.nodes.values());    // 以权重值为规范的小根堆    PriorityQueue<Edge> smallEdgeQueue = new PriorityQueue<>((a, b) -> a.weight - b.weight);    // 小根堆放入所有的边    for (Edge edge : graph.edges) {        smallEdgeQueue.offer(edge);    }    Set<Edge> result = new HashSet<>();    while (!smallEdgeQueue.isEmpty()) {        Edge edge = smallEdgeQueue.poll();        // 小根堆堆顶的边对应的节点不会造成环（即两个点不在同一个汇合中），才往后果集中增加，否则舍弃        if (!unionFind.isSameSet(edge.from, edge.to)) {            result.add(edge);            unionFind.union(edge.from, edge.to);        }    }    return result;}

2、Prim算法

（1）能够从任意节点登程来寻找最小生成树

（2）某个点退出到被选取的点中后，解锁这个点登程的所有新边

（3）在所有解锁的边当选最小的边，而后看这个边退出到被解锁的点中后会不会造成环

（4）如果会，舍弃以后边，返回第3步；如果不会，保留以后边，将该边的指向点解锁，此边退出到后果中，返回第2步

（5）当所有点都被解锁时，最小生成树就失去了

/** * 最小生成树算法-Prim算法 * * @author Java和算法学习：周一 */public static Set<Edge> prim(Graph graph) {    Collection<Node> nodes = graph.nodes.values();    if (nodes.isEmpty()) {        return null;    }    // 解锁的边依照权重值规范放到小根堆中    PriorityQueue<Edge> smallEdgeQueue = new PriorityQueue<>((a, b) -> a.weight - b.weight);    // 曾经解锁的点    Set<Node> nodeSet = new HashSet<>();    Set<Edge> result = new HashSet<>();    // 1.从任意节点登程来寻找最小生成树    for (Node node : nodes) {        if (!nodeSet.contains(node)) {            // 点解锁            nodeSet.add(node);            // 2.此点连贯的所有边解锁            for (Edge edge : node.edges) {                smallEdgeQueue.offer(edge);            }            // 3.在所有解锁的边当选最小的边，而后看这个边退出到被选取的点中后会不会造成环            while (!smallEdgeQueue.isEmpty()) {                // 从解锁的边中弹出最小的边                Edge currentEdge = smallEdgeQueue.poll();                Node toNode = currentEdge.to;                // 该边的指向点未解锁，则解锁                if (!nodeSet.contains(toNode)) {                    nodeSet.add(toNode);                    result.add(currentEdge);                    // 指向点连贯的所有边解锁                    for (Edge edge : toNode.edges) {                        smallEdgeQueue.offer(edge);                    }                }                // 该边的指向点曾经解锁，间接舍弃此边            }            // 为了避免森林，所以不break            // 如果明确晓得不会呈现森林（或不须要避免森林），能够break            // break;        }    }    return result;}

六、Dijkstra算法（迪杰斯特拉算法）

1、含意

以一个顶点作为源节点而后找到该顶点到图中所有其它结点的最短门路，无奈达到的节点不论。该算法解决了图上带权的单源最短门路问题。

2、作用

罕用于路由、寻路、交通、布局。举例来说，如果图中的顶点示意城市，而边上的权重示意城市间开车行经的间隔，该算法能够用来找到两个城市之间的最短门路。

该当留神，Dijkstra算法用于解决有向无负权重的图。

3、代码思路

（1）定义一个Map用于寄存从指定点A到指标点的间隔。从指定点A开始，到指标点A的间隔为0，A可能间接一步到的点的间隔等于边上的权重值，不能间接到的点的间隔则是无穷大，更新Map。A点锁定。

（2）从Map中找出到指标点权重最小的边B，从B可能间接一步到点C的间隔加上第1步得出的A到B的间隔 小于 第1步得出的A到C的间隔[（A -> B）+（B -> C）< （A -> C）]则更新Map中到C的间隔，否则不变；按此条件始终查看从B可能间接一步到的所有点的间隔，查看结束则B点锁定。

（3）始终执行第2步，直到所有点被锁定。

/** * Dijkstra算法——原始版本 * * @author Java和算法学习：周一 */public static Map<Node, Integer> dijkstra1(Node head) {    // 从head到指标点的间隔，key：指标点，value：间隔    Map<Node, Integer> distanceMap = new HashMap<>();    // 本人到本人的最短距离必定是0    distanceMap.put(head, 0);    // 曾经锁定的点    Set<Node> selectedNode = new HashSet<>();    // 此时minNode必定是head点    Node minNode = getMinDistanceFromUnSelectedNode(distanceMap, selectedNode);    while (minNode != null) {        // 从head到minNode的最短距离        int distance = distanceMap.get(minNode);        for (Edge edge : minNode.edges) {            Node toNode = edge.to;            if (!distanceMap.containsKey(toNode)) {                // toNode不存在，则从head到toNode此时的最短距离为 head到minNode的最短距离 + 此边的权重值                distanceMap.put(toNode, distance + edge.weight);            } else {                // toNode存在，则更新最短距离                distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance + edge.weight));            }        }        // minNode使命实现（minNode所有间接到的点都遍历实现）        selectedNode.add(minNode);        // 从新找出下一个minNode        minNode = getMinDistanceFromUnSelectedNode(distanceMap, selectedNode);    }    return distanceMap;}

4、应用增强堆优化

能够应用增强堆改良。将从Map中找出到未锁定目标点间隔最短的点的工夫复杂度从O(N)调整到O(logN)程度。

/** * 改良后的dijkstra算法 *  * 从head登程，所有head能达到的节点，生成达到每个节点的最短门路记录并返回 * * @author Java和算法学习：周一 */public static Map<Node, Integer> dijkstra1(Node head, int size) {    // 应用增强堆进行优化    NodeHeap nodeHeap = new NodeHeap(size);    // head到head的间隔必定是0    nodeHeap.addOrUpdateOrIgnore(head, 0);    Map<Node, Integer> result = new HashMap<>();    while (!nodeHeap.isEmpty()) {        NodeRecord record = nodeHeap.pop();        Node node = record.node;        int distance = record.distance;        for (Edge edge : node.edges) {            nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);        }        result.put(node, distance);    }    return result;}

七、本文所有代码地址

Github：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/graph

Gitee：https://gitee.com/monday-pro/algorithm-study/tree/master/src/basic/graph