关于图:面试中图论都考什么这篇文章告诉你

图论〔Graph Theory〕是数学的一个分支。它以图为钻研对象。图论中的图是由若干给定的点及连贯两点的线所形成的图形，这种图形通常用来形容某些事物之间的某种特定关系，用点代表事物，用连贯两点的线示意相应两个事物间具备这种关系。

如下就是一种逻辑上的图构造：

图是一种最简单的数据结构，后面讲的数据结构都能够看成是图的特例。那为什么不都用图就好了，还要分那么多种数据结构呢？

这是因为很多时候不须要用到那么简单的性能，图的很多个性都不具备，如果抽象地都称为图那么十分不利于沟通。你想你和他人沟通总不至于说这道题是考查一种非凡的图，这种图。。。。这未免太啰嗦了，因而给其余图的非凡的图起了非凡的名字，这样就不便沟通了。直到遇到了非常复杂的状况，咱们才会用到 ”真正“的图。

后面章节提到了 数据结构就是为了算法服务的，数据结构就是存储数据用的，目标是为了更高效。 那么什么时候须要用图来存储数据，在这种状况图高效在哪里呢？答案很简略，那就是如果你用其余简略的数据结构无奈很好地进行存储，就应该应用图了。比方咱们须要存储一种双向的敌人关系，并且这种敌人关系是多对多的，那就肯定要用到图，因为其余数据结构无奈模仿。

后面提到了二叉树齐全能够实现其余树结构，相似地，有向图也齐全能够实现无向图和混合图，因而有向图的钻研始终是重点考查对象。

本文讲的所有图都是有向图。

后面提到了咱们用连贯两点的线示意相应两个事物间具备这种关系。因而如果两个事物间的关系是有方向的，就是有向图，否则就是无向图。比方：A 意识 B，那么 B 不肯定意识 A。那么关系就是单向的，咱们须要用有向图来示意。因为如果用无向图示意，咱们无奈辨别 A 和 B 的边示意的是 A 意识 B 还是 B 意识 A。

习惯上，咱们画图的时候用带箭头的示意有向图，不带箭头的示意无向图。

如果边是有权重的是有权图（或者带权图），否则是无权图（或不带权图）。那么什么是有权重呢？比方汇率就是一种有权重的逻辑图。1 货币 A 兑换 5 货币 B，那么咱们 A 和 B 的边的权重就是 5。而像敌人这种关系，就可以看做一种不带权的图。

有多少边指向节点 A，那么节点 A 的入度就是多少。同样地，有多少边从 A 收回，那么节点 A 的出度就是多少。

依然以下面的图为例，这幅图的所有节点的入度和出度都为 1。

有环图〔Cyclic Graph〕下面的图就是一个有环图，因为咱们从图中的某一个点触发，可能从新回到终点。这和事实中的环是一样的。
无环图〔Acyclic Graph〕

我能够将下面的图稍加革新就变成了无环图，此时没有任何一个环路。

在无向图中，若 任意两个顶点 i 与 j 都有门路相通，则称该无向图为连通图。

在有向图中，若 任意两个顶点 i 与 j 都有门路相通，则称该有向图为强连通图。

一个连通图的生成树是指一个连通子图，它含有图中全副 n 个顶点，但只有足以形成一棵树的 n-1 条边。一颗有 n 个顶点的生成树有且仅有 n-1 条边，如果生成树中再增加一条边，则必然成环。在连通网的所有生成树中，所有边的 代价和最小 的生成树，称为最小生成树，其中 代价和 指的是所有边的权重和。

个别图的题目都不会给你一个现成的图的数据结构。当你晓得这是一个图的题目的时候，解题的第一步通常就是建图。

下面讲的都是图的逻辑构造，那么计算机中的图如何存储呢？

咱们晓得图是有点和边组成的。实践上，咱们只有存储图中的所有的边关系即可，因为边中曾经蕴含了两个点的关系。

这里我简略介绍两种常见的建图形式：邻接矩阵（罕用，重要）和邻接表。

第一种形式是应用数组或者哈希表来存储图，这里咱们用二维数组来存储。

应用一个 n * n 的矩阵来形容图 graph，其就是一个二维的矩阵，其中 graphi 形容边的关系。

一般而言，对于无权图我都用 graphi = 1 来示意顶点 i 和顶点 j 之间有一条边，并且边的指向是从 i 到 j。用 graphi = 0 来示意顶点 i 和顶点 j 之间不存在一条边。对于有权图来说，咱们能够存储其余数字，示意的是权重。

能够看出上图是对角线对称的，这样咱们只需看一半就好了，这就造成了一半的空间节约。

这种存储形式的空间复杂度为 O(n ^ 2)，其中 n 为顶点个数。如果是稠密图（图的边的数目远小于顶点的数目），那么会很节约空间。并且如果图是无向图，始终至多会有 50 % 的空间节约。上面的图也直观地反馈了这一点。

邻接矩阵的长处次要有：

直观，简略。
判断两个顶点是否连贯，获取入度和出度以及更新度数，工夫复杂度都是 O(1)

因为应用起来比较简单，因而我的所有的须要建图的题目根本都用这种形式。

比方力扣 743. 网络延迟时间。题目形容：

有 N 个网络节点，标记为 1 到 N。给定一个列表 times，示意信号通过有向边的传递工夫。times[i] = (u, v, w)，其中 u 是源节点，v 是指标节点，w 是一个信号从源节点传递到指标节点的工夫。当初，咱们从某个节点 K 收回一个信号。须要多久能力使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。示例：输出：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
输入：2
 

留神:

N 的范畴在 [1, 100] 之间。K 的范畴在 [1, N] 之间。times 的长度在 [1, 6000] 之间。所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。

这是一个典型的图的题目，对于这道题，咱们如何用邻接矩阵建图呢？

一个典型的建图代码：

应用哈希表构建邻接矩阵：

    graph = collections.defaultdict(list)
    for fr, to, w in times:
        graph[fr - 1].append((to - 1, w))

应用二维数组构建邻接矩阵：

graph = [[0]*n for _ in range(m)] # 新建一个 m * n 的二维矩阵

for fr, to, w in times:
    graph[fr-1][to-1] = w

这就结构了一个临界矩阵，之后咱们基于这个邻接矩阵遍历图即可。

对于每个点，存储着一个链表，用来指向所有与该点间接相连的点。对于有权图来说，链表中元素值对应着权重。

例如在无向无权图中：

（图片来自 https://zhuanlan.zhihu.com/p/…）

能够看出在无向图中，邻接矩阵对于对角线对称，而邻接链表总有两条对称的边。

而在有向无权图中：

（图片来自 https://zhuanlan.zhihu.com/p/…）

因为邻接表应用起来略微麻烦一点，另外也不罕用。为了缩小初学者的认知累赘，我就不贴代码了。

图建设好了，接下来就是要遍历了。

不论你是什么算法，必定都要遍历的，个别有这两种办法：深度优先搜寻，广度优先搜寻（其余奇葩的遍历形式实际意义不大，没有必要学习）。

不论是哪一种遍历，如果图有环，就肯定要记录节点的拜访状况，避免死循环。当然你可能不须要真正地应用一个汇合记录节点的拜访状况，比方应用一个数据范畴外的数据原地标记，这样的空间复杂度会是 $O(1)$。

这里以有向图为例，有向图也是相似，这里不再赘述。

对于图的搜寻，前面的搜寻专题也会做具体的介绍，因而这里就点到为止。

深度优先遍历图的办法是，从图中某顶点 v 登程，一直拜访街坊，街坊的街坊直到拜访结束。

如上图，如果咱们应用 DFS，并且从 A 节点开始的话，一个可能的 的拜访程序是：A -> C -> B -> D -> F -> G -> E，当然也可能是 A -> D -> C -> B -> F -> G -> E 等，具体取决于你的代码，但他们都是深度优先的。

广度优先搜寻，能够被形象地形容为 “ 浅尝辄止 ”，它也须要一个队列以放弃遍历过的顶点程序，以便按出队的程序再去拜访这些顶点的邻接顶点。

如上图，如果咱们应用 BFS，并且从 A 节点开始的话，一个可能的 的拜访程序是：A -> B -> C -> F -> E -> G -> D，当然也可能是 A -> B -> F -> E -> C -> G -> D 等，具体取决于你的代码，但他们都是广度优先的。

须要留神的是 DFS 和 BFS 只是一种算法思维，不是一种具体的算法。因而其有着很强的适应性，而不是局限于特点的数据结构的，本文讲的图能够用，后面讲的树也能够用。实际上，只有是 非线性的数据结构都能够用。

图的题目的算法比拟适宜套模板。

这里介绍几种常见的板子题。次要有：

Dijkstra
Floyd-Warshall
最小生成树（Kruskal & Prim）目前此大节曾经删除，感觉本人写的不够具体，之后补充实现会再次凋谢。
A 星寻路算法
二分图（染色法）〔Bipartitie〕
拓扑排序〔Topological Sort〕

上面列举常见算法的模板。

以下所有的模板都是基于邻接矩阵建图。

强烈建议大家学习完专题篇的搜寻之后再来学习上面经典算法。大家能够拿几道一般的搜寻题目测试下，如果可能做进去再往下学习。举荐题目：最大化一张图中的门路价值

DIJKSTRA 根本思维是广度优先遍历。实际上搜寻的最短路算法根本思维都是广度优先，只不过具体的扩大策略不同而已。

DIJKSTRA 算法次要解决的是图中 任意一点 到图中 另外任意一个点 的最短距离，即单源最短门路。

Dijkstra 这个名字比拟难记，大家能够简略记为DJ 算法，有没有好记很多？

比方给你几个城市，以及城市之间的间隔。让你布局一条最短的从城市 a 到城市 b 的路线。

这个问题，咱们就能够先将城市间的间隔用图建设进去，而后应用 dijkstra 来做。那么 dijkstra 到底如何计算最短门路的呢？

dj 算法的根本思维是贪婪。从终点 start 开始，每次都遍历所有街坊，并从中找到间隔最小的，实质上是一种广度优先遍历。这里咱们借助堆这种数据结构，使得能够在 $logN$ 的工夫内找到 cost 最小的点。

而如果应用一般的队列的话，其实是图中所有边权值都雷同的非凡状况。

比方咱们要找从点 start 到点 end 的最短距离。咱们冀望 dj 算法是这样被应用的。

比方一个图是这样的：

E -- 1 --> B -- 1 --> C -- 1 --> D -- 1 --> F
 \                                         /\
  \                                        ||
    -------- 2 ---------> G ------- 1 ------

咱们应用邻接矩阵来结构：

G = {"B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["G", 2]],
    "F": [],
    "G": [["F", 1]],
}

shortDistance = dijkstra(G, "E", "C")
print(shortDistance)  # E -- 3 --> F -- 3 --> C == 6

具体算法：

初始化堆。堆里的数据都是 (cost, v) 的二元祖，其含意是“从 start 走到 v 的间隔是 cost”。因而初始状况，堆中寄存元组 (0, start)
从堆中 pop 进去一个 (cost, v)，第一次 pop 进去的肯定是 (0, start)。如果 v 被拜访过了，那么跳过，避免环的产生。
如果 v 是咱们要找的起点，间接返回 cost，此时的 cost 就是从 start 到该点的最短距离
否则，将 v 的街坊入堆，行将 (neibor, cost + c) 退出堆。其中 neibor 为 v 的街坊，c 为 v 到 neibor 的间隔（也就是转移的代价）。

反复执行 2 – 4 步

代码模板：

Python

import heapq


def dijkstra(graph, start, end):
    # 堆里的数据都是 (cost, i) 的二元祖，其含意是“从 start 走到 i 的间隔是 cost”。heap = [(0, start)]
    visited = set()
    while heap:
        (cost, u) = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        if u == end:
            return cost
        for v, c in graph[u]:
            if v in visited:
                continue
            next = cost + c
            heapq.heappush(heap, (next, v))
    return -1

JavaScript

const dijkstra = (graph, start, end) => {const visited = new Set()
  const minHeap = new MinPriorityQueue();
  // 注：此处 new MinPriorityQueue()用了 LC 的内置 API，它的 enqueue 由两个局部组成：//element 和 priority。// 堆会依照 priority 排序，能够用 element 记录一些内容。minHeap.enqueue(startPoint, 0)

  while(!minHeap.isEmpty()){const {element, priority} = minHeap.dequeue();
    // 上面这两个变量不是必须的，只是便于了解
    const curPoint = element;
    const curCost = priority;

    if(curPoint === end) return curCost;
    if(visited.has(curPoint)) continue;
    visited.add(curPoint);

    if(!graph[curPoint]) continue;
    for(const [nextPoint, nextCost] of graph[curPoint]){if(visited.has(nextPoint)) continue;
      // 留神 heap 外面的肯定是从 startPoint 到某个点的间隔；//curPoint 到 nextPoint 的间隔是 nextCost；但 curPoint 不肯定是 startPoint。const accumulatedCost = nextCost + curCost;
      minHeap.enqueue(nextPoint, accumulatedCost);
    }
  }
  return -1
}

会了这个算法模板，你就能够去 AC 743. 网络延迟时间了。

这里提供残缺代码供大家参考：

Python

class Solution:
    def dijkstra(self, graph, start, end):
        heap = [(0, start)]
        visited = set()
        while heap:
            (cost, u) = heapq.heappop(heap)
            if u in visited:
                continue
            visited.add(u)
            if u == end:
                return cost
            for v, c in graph[u]:
                if v in visited:
                    continue
                next = cost + c
                heapq.heappush(heap, (next, v))
        return -1
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = collections.defaultdict(list)
        for fr, to, w in times:
            graph[fr - 1].append((to - 1, w))
        ans = -1
        for to in range(N):
            dist = self.dijkstra(graph, K - 1, to)
            if dist == -1: return -1
            ans = max(ans, dist)
        return ans

JavaScript

const networkDelayTime = (times, n, k) => {
    // 咳咳这个解法并不是 Dijkstra 在本题的最佳解法
    const graph = {};
    for(const [from, to, weight] of times){if(!graph[from]) graph[from] = [];
        graph[from].push([to, weight]);
    }

    let ans = -1;
    for(let to = 1; to <= n; to++){let dist = dikstra(graph, k, to)
        if(dist === -1) return -1;
        ans = Math.max(ans, dist);
    }
    return ans;
};

const dijkstra = (graph, startPoint, endPoint) => {const visited = new Set()
  const minHeap = new MinPriorityQueue();
  // 注：此处 new MinPriorityQueue()用了 LC 的内置 API，它的 enqueue 由两个局部组成：//element 和 priority。// 堆会依照 priority 排序，能够用 element 记录一些内容。minHeap.enqueue(startPoint, 0)

  while(!minHeap.isEmpty()){const {element, priority} = minHeap.dequeue();
    // 上面这两个变量不是必须的，只是便于了解
    const curPoint = element;
    const curCost = priority;
    if(visited.has(curPoint)) continue;
    visited.add(curPoint)
    if(curPoint === endPoint) return curCost;

    if(!graph[curPoint]) continue;
    for(const [nextPoint, nextCost] of graph[curPoint]){if(visited.has(nextPoint)) continue;
      // 留神 heap 外面的肯定是从 startPoint 到某个点的间隔；//curPoint 到 nextPoint 的间隔是 nextCost；但 curPoint 不肯定是 startPoint。const accumulatedCost = nextCost + curCost;
      minHeap.enqueue(nextPoint, accumulatedCost);
    }
  }
  return -1
}

DJ 算法的工夫复杂度为 $vlogv+e$，其中 v 和 e 别离为图中的点和边的个数。

最初给大家留一个思考题：如果是计算一个点到图中 所有点 的间隔呢？咱们的算法会有什么样的调整？

提醒：你能够应用一个 dist 哈希表记录开始点到每个点的最短距离来实现。想进去的话，能够使劲扣 882 题去验证一下哦~

值得注意的是，Dijkstra 无奈解决边权值为负的状况。即如果呈现负权值的边，那么答案可能不正确。而基于动静布局算法的最短路（下文会讲）则能够解决这种状况。

Floyd-Warshall 能够 解决任意两个点间隔，即多源最短门路，这点和 dj 算法不一样。

除此之外，贝尔曼 - 福特算法也是解决最短门路的经典动静布局算法，这点和 dj 也是不一样的，dj 是基于贪婪的。

相比下面的 dijkstra 算法，因为其计算过程会把两头运算后果保存起来避免反复计算，因而其特地适宜 求图中任意两点的间隔，比方力扣的 1462. 课程安顿 IV。除了这个长处。下文要讲的贝尔曼 - 福特算法相比于此算法最大的区别在于本算法是多源最短门路，而贝尔曼 - 福特则是单源最短门路。不论是复杂度和写法，贝尔曼 - 福特算法都更简略，咱们前面给大家介绍。

当然就不是说贝尔曼算法以及下面的 dijkstra 就不反对多源最短门路，你只须要加一个 for 循环枚举所有的终点罢了。

还有一个十分重要的点是 Floyd-Warshall 算法因为应用了 动静布局 的思维而不是贪婪，因而其 能够解决负权重 的状况，这点须要大家尤为留神。动静布局的具体内容请参考之后的 动静布局专题 和背包问题。

算法也不难理解，简略来说就是：i 到 j 的最短门路 = i 到 k 的最短门路 + k 到 j 的最短门路 的最小值。如下图：

u 到 v 的最短距离是 u 到 x 的最短距离 + x 到 v 的最短距离。上图 x 是 u 到 v 的必经之路，如果不是的话，咱们须要多个两头节点的值，并取最小的。

算法的正确性显而易见，因为从 i 到 j，要么间接到，要么通过图中的另外一个点 k，两头节点 k 可能有多个，通过两头点的状况取出最小的，天然就是 i 到 j 的最短距离。

思考题：最长无环门路能够用动静布局来解么？

该算法的工夫复杂度是 $O(N^3)$，空间复杂度是 $O(N^2)$，其中 N 为顶点个数。

代码模板：

Python

# graph 是邻接矩阵，n 是顶点个数
# graph 形如：graph[u][v] = w

def floyd_warshall(graph, n):
    dist = [[float("inf") for _ in range(n)] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            dist[i][j] = graph[i][j]

    # check vertex k against all other vertices (i, j)
    for k in range(n):
        # looping through rows of graph array
        for i in range(n):
            # looping through columns of graph array
            for j in range(n):
                if (dist[i][k] != float("inf")
                    and dist[k][j] != float("inf")
                    and dist[i][k] + dist[k][j] < dist[i][j]
                ):
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

JavaScript

const floydWarshall = (graph, v)=>{const dist = new Array(v).fill(0).map(() => new Array(v).fill(Number.MAX_SAFE_INTEGER))

  for(let i = 0; i < v; i++){for(let j = 0; j < v; j++){
      // 两个点雷同，间隔为 0
      if(i === j) dist[i][j] = 0;
      //i 和 j 的间隔已知
      else if(graph[i][j]) dist[i][j] = graph[i][j];
      //i 和 j 的间隔未知，默认是最大值
      else dist[i][j] = Number.MAX_SAFE_INTEGER;
    }
  }

  // 查看是否有一个点 k 使得 i 和 j 之间间隔更短，如果有，则更新最短距离
  for(let k = 0; k < v; k++){for(let i = 0; i < v; i++){for(let j = 0; j < v; j++){dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j])
      }
    }
  }
  return 看须要
}

咱们回过头来看下如何套模板解决力扣的 1462. 课程安顿 IV，题目形容：

你总共须要上 n 门课，课程编号顺次为 0 到 n-1。有的课会有间接的先修课程，比方如果想上课程 0，你必须先上课程 1，那么会以 [1,0] 数对的模式给出先修课程数对。给你课程总数 n 和一个间接先修课程数对列表 prerequisite 和一个查问对列表 queries。对于每个查问对 queries[i]，请判断 queries[i][0] 是否是 queries[i][1] 的先修课程。请返回一个布尔值列表，列表中每个元素顺次别离对应 queries 每个查问对的判断后果。留神：如果课程 a 是课程 b 的先修课程且课程 b 是课程 c 的先修课程，那么课程 a 也是课程 c 的先修课程。示例 1：输出：n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输入：[false,true]
解释：课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。示例 2：输出：n = 2, prerequisites = [], queries = [[1,0],[0,1]]
输入：[false,false]
解释：没有先修课程对，所以每门课程之间是独立的。示例 3：输出：n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输入：[true,true]
示例 4：输出：n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
输入：[false,true]
示例 5：输出：n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
输入：[true,false,true,false]
 

提醒：2 <= n <= 100
0 <= prerequisite.length <= (n * (n - 1) / 2)
0 <= prerequisite[i][0], prerequisite[i][1] < n
prerequisite[i][0] != prerequisite[i][1]
先修课程图中没有环。先修课程图中没有反复的边。1 <= queries.length <= 10^4
queries[i][0] != queries[i][1]

这道题也能够应用 Floyd-Warshall 来做。你能够这么想，如果从 i 到 j 的间隔大于 0，那不就是先修课么。而这道题数据范畴 queries 大略是 10 ^ 4，用下面的 dijkstra 算法必定超时，，因而 Floyd-Warshall 算法是理智的抉择。

我这里间接套模板，略微改下就过了。残缺代码：
Python

class Solution:
    def Floyd-Warshall(self, dist, v):
        for k in range(v):
            for i in range(v):
                for j in range(v):
                    dist[i][j] = dist[i][j] or (dist[i][k] and dist[k][j])

        return dist

    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        graph = [[False] * n for _ in range(n)]
        ans = []

        for to, fr in prerequisites:
            graph[fr][to] = True
        dist = self.Floyd-Warshall(graph, n)
        for to, fr in queries:
            ans.append(bool(dist[fr][to]))
        return ans

JavaScript

// 咳咳这个写法不是本题最优
var checkIfPrerequisite = function(numCourses, prerequisites, queries) {const graph = {}
    for(const [course, pre] of prerequisites){if(!graph
) graph

 = {}

        graph

[course] = true

    }
    const ans = []
    const dist = Floyd-Warshall(graph, numCourses)

    for(const [course, pre] of queries){

        ans.push(dist

[course])

    }
    return ans

};
var Floyd-Warshall = function(graph, n){

    dist = Array.from({length: n + 1}).map(() => Array.from({length: n + 1}).fill(false))

    for(let k = 0; k < n; k++){

        for(let i = 0; i < n; i++){

            for(let j = 0; j < n; j++){

                if(graph[i] && graph[i][j]) dist[i][j] = true

                if(graph[i] && graph[k]){

                    dist[i][j] = (dist[i][j])|| (dist[i][k] && dist[k][j])

                }else if(graph[i]){

                    dist[i][j] = dist[i][j]

                }

            }

        }

    }

    return dist

}


如果这道题你能够解决了，我再举荐一道题给你 1617. 统计子树中城市之间最大间隔，国际版有一个题解代码挺清晰，挺好了解的，只不过没有应用状态压缩性能不是很好罢了，地址：https://leetcode.com/problems…
图上的动静布局算法大家还能够拿这个题目来练习一下。

787. K 站直达内最便宜的航班

和下面的算法相似。这种解法次要解决单源最短门路，即图中某一点到其余点的最短距离。

其根本思维也是动静布局。

外围算法为：

初始化终点间隔为 0
对图中的所有边进行 若干次 解决，直到稳固。解决的根据是：对于每一个有向边 (u,v)，如果 dist[u] + w 小于 dist[v]，那么意味着咱们 找到了一条达到 v 更近的路，更新之。
下面的若干次的下限是顶点 V 的个数，因而无妨间接进行 n 次解决。
最初检查一下是否存在负边引起的环。（留神）

举个例子。对于如下的一个图，存在一个 B -> C -> D -> B，这样 B 到 C 和 D 的间隔实践上能够无限小。咱们须要检测到这一种状况，并退出。

此算法工夫复杂度：$O(V*E)$，空间复杂度：$O(V)$。

代码示例：
Python

# return -1 for not exsit
# else return dis map where dis[v] means for point s the least cost to point v
def bell_man(edges, s):
    dis = defaultdict(lambda: math.inf)
    dis[s] = 0
    for _ in range(n):
        for u, v, w in edges:
            if dis[u] + w < dis[v]:
                dis[v] = dis[u] + w

    for u, v, w in edges:
        if dis[u] + w < dis[v]:
            return -1

    return dis

JavaScript

const BellmanFord = (edges, startPoint)=>{
  const n = edges.length;
  const dist = new Array(n).fill(Number.MAX_SAFE_INTEGER);
  dist[startPoint] = 0;

  for(let i = 0; i < n; i++){for(const [u, v, w] of edges){if(dist[u] + w < dist[v]){dist[v] = dist[u] + w;
        }
    }
  }

  for(const [u, v, w] of edges){if(dist[u] + w < dist[v]) return -1;
  }

  return dist
}

举荐浏览：

bellman-ford-algorithm

题目举荐：

Best Currency Path

在计算机科学畛域，有向图的拓扑排序是对其顶点的一种线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv，u 在排序中都在之前。当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。

典型的题目就是给你一堆课程，课程之间有先修关系，让你给出一种可行的学习门路形式，要求先修的课程要先学。任何有向无环图至多有一个拓扑排序。已知有算法能够在线性工夫内，构建任何有向无环图的拓扑排序。

简略来说，假如 L 是寄存后果的列表，先找到那些入度为零的节点，把这些节点放到 L 中，因为这些节点没有任何的父节点。而后把与这些节点相连的边从图中去掉，再寻找图中的入度为零的节点。对于新找到的这些入度为零的节点来说，他们的父节点曾经都在 L 中了，所以也能够放入 L。反复上述操作，直到找不到入度为零的节点。如果此时 L 中的元素个数和节点总数雷同，阐明排序实现；如果 L 中的元素个数和节点总数不同，阐明原图中存在环，无奈进行拓扑排序。

def topologicalSort(graph):
    """Kahn's Algorithm is used to find Topological ordering of Directed Acyclic Graph
    using BFS
    """
    indegree = [0] * len(graph)
    queue = collections.deque()
    topo = []
    cnt = 0

    for key, values in graph.items():
        for i in values:
            indegree[i] += 1

    for i in range(len(indegree)):
        if indegree[i] == 0:
            queue.append(i)

    while queue:
        vertex = queue.popleft()
        cnt += 1
        topo.append(vertex)
        for x in graph[vertex]:
            indegree[x] -= 1
            if indegree[x] == 0:
                queue.append(x)

    if cnt != len(graph):
        print("Cycle exists")
    else:
        print(topo)


# Adjacency List of Graph
graph = {0: [1, 2], 1: [3], 2: [3], 3: [4, 5], 4: [], 5: []}
topologicalSort(graph)

首先咱们来看下什么是生成树。

首先生成树是原图的一个子图，它实质是一棵树，这也是为什么叫做生成树，而不是生成图的起因。其次生成树应该包含图中所有的顶点。如下图因为没有蕴含所有顶点，换句话说所有顶点没有在同一个联通域，因而不是一个生成树。

黄色顶点没有包含在内

你能够将生成树看成是根节点不确定的多叉树，因为是一棵树，那么肯定不蕴含环。如下图就不是生成树。

因而不难得出，最小生成树的边的个数是 n – 1，其中 n 为顶点个数。

接下来咱们看下什么是最小生成树。

最小生成树是在生成树的根底上加了最小关键字，是最小权重生成树的简称。从这句话也能够看出，最小生成树解决正是有权图。生成树的权重是其所有边的权重和，那么 最小生成树就是权重和最小的生成树，由此可看出，不论是生成树还是最小生成树都可能不惟一。

最小生成树在理论生存中有很强的价值。比方我要建筑一个地铁，并笼罩 n 个站，这 n 个站要相互都能够达到（同一个联通域），如果建造能力使得破费最小？因为每个站之间的路线不同，因而造价也不一样，因而这就是一个最小生成树的理论应用场景，相似的例子还有很多。

（图来自维基百科）

不难看出，计算最小生成树就是从边汇合中筛选 n – 1 个边，使得其满足生成树，并且权值和最小。

Kruskal 和 Prim 是两个经典的求最小生成树的算法，这两个算法又是如何计算最小生成树的呢？本节咱们就来理解一下它们。

Kruskal 绝对比拟容易了解，举荐把握。

Kruskal 算法也被形象地称为 加边法，每后退一次都抉择权重最小的边，退出到后果集。为了避免环的产生（减少环是无意义的，只有权重是负数，肯定会使后果更差），咱们须要查看下以后抉择的边是否和曾经抉择的边联通了。如果联通了，是没有必要选取的，因为这会使得环产生。因而算法上，咱们可应用并查集辅助实现。对于并查集，咱们会在之后的进阶篇进行解说。

上面代码中的 find_parent 局部，实际上就是并查集的外围代码，只是咱们没有将其封装并应用罢了。

Kruskal 具体算法：

对边依照权值从小到大进行排序。
将 n 个顶点初始化为 n 个联通域
依照权值从小到大抉择边退出到后果集，每次 贪婪地 抉择最小边。如果以后抉择的边是否和曾经抉择的边联通了（如果强行加就有环了），则放弃抉择，否则进行抉择，退出到后果集。
反复 3 直到咱们找到了一个联通域大小为 n 的子图

代码模板：

其中 edge 是一个数组，数组每一项都形如：(cost, fr, to)，含意是从 fr 到 to 有一条权值为 cost 的边。

class DisjointSetUnion:
    def __init__(self, n):
        self.n = n
        self.rank = [1] * n
        self.f = list(range(n))
    
    def find(self, x: int) -> int:
        if self.f[x] == x:
            return x
        self.f[x] = self.find(self.f[x])
        return self.f[x]
    
    def unionSet(self, x: int, y: int) -> bool:
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False

        if self.rank[fx] < self.rank[fy]:
            fx, fy = fy, fx
        
        self.rank[fx] += self.rank[fy]
        self.f[fy] = fx
        return True

class Solution:
    def Kruskal(self, edges) -> int:
        n = len(points)
        dsu = DisjointSetUnion(n)
        
        edges.sort()
        
        ret, num = 0, 1
        for length, x, y in edges:
            if dsu.unionSet(x, y):
                ret += length
                num += 1
                if num == n:
                    break
        
        return ret

Prim 算法也被形象地称为 加点法，每后退一次都抉择权重最小的点，退出到后果集。形象地看就像一个一直成长的真实世界的树。

Prim 具体算法：

初始化最小生成树点集 MV 为图中任意一个顶点，最小生成树边集 ME 为空。咱们的指标是将 MV 填充到和 V 一样，而边集则依据 MV 的产生主动计算。
在汇合 E 中（汇合 E 为原始图的边集）选取最小的边 <u, v> 其中 u 为 MV 中已有的元素，而 v 为 MV 中不存在的元素（像不像下面说的 一直成长的真实世界的树），将 v 退出到 MV，将 <u, v> 加到 ME。
反复 2 直到咱们找到了一个联通域大小为 n 的子图

代码模板：

其中 dist 是二维数组，disti = x 示意顶点 i 到顶点 j 有一条权值为 x 的边。

class Solution:
    def Prim(self, dist) -> int:
        n = len(dist)
        d = [float("inf")] * n # 示意各个顶点与退出最小生成树的顶点之间的最小间隔.
        vis = [False] * n # 示意是否曾经退出到了最小生成树外面
        d[0] = 0
        ans = 0
        for _ in range(n):
            # 寻找目前这轮的最小 d
            M = float("inf") 
            for i in range(n):
                if not vis[i] and d[i] < M:
                    node = i
                    M = d[i]
            vis[node] = True
            ans += M
            for i in range(n):
                if not vis[i]:
                    d[i] = min(d[i], dist[i][node])
        return ans

为了前面形容不便，咱们令 V 为图中的顶点数，E 为图中的边数。那么 KruKal 的算法复杂度是 $O(ElogE)$，Prim 的算法工夫复杂度为 $E + VlogV$。因而 Prim 适宜实用于浓密图，而 KruKal 则适宜稠密图。

大家也能够参考一下维基百科 – 最小生成树的材料作为补充。

另外这里有一份视频学习材料，其中的动画做的不错，大家能够作为参考，地址：https://www.bilibili.com/vide…

大家能够应用 LeetCode 的 1584. 连贯所有点的最小费用来练习该算法。

A 星寻路解决的问题是在一个二维的表格中找出任意两点的最短距离或者最短门路。罕用于游戏中的 NPC 的挪动计算，是一种罕用启发式算法。个别这种题目都会有障碍物。除了障碍物，力扣的题目还会减少一些限度，使得题目难度减少。

这种题目个别都是力扣的艰难难度。了解起来不难，然而要残缺地没有 bug 地写进去却不那么容易。

在该算法中，咱们从终点开始，查看其相邻的四个方格并尝试扩大，直至找到指标。A 星寻路算法的寻路形式不止一种，感兴趣的能够自行理解一下。

公式示意为：f(n)=g(n)+h(n)。

其中：

f(n) 是从初始状态经由状态 n 到指标状态的预计代价，
g(n) 是在状态空间中从初始状态到状态 n 的理论代价，
h(n) 是从状态 n 到指标状态的最佳门路的预计代价。

如果 g(n)为 0，即只计算任意顶点 n 到指标的评估函数 h(n)，而不计算终点到顶点 n 的间隔，则算法转化为应用贪婪策略的最良优先搜寻，速度最快，但可能得不出最优解；
如果 h(n)不大于顶点 n 到指标顶点的理论间隔，则肯定能够求出最优解，而且 h(n)越小，须要计算的节点越多，算法效率越低，常见的评估函数有——欧几里得间隔、曼哈顿间隔、切比雪夫间隔；
如果 h(n)为 0，即只需要出终点到任意顶点 n 的最短门路 g(n)，而不计算任何评估函数 h(n)，则转化为单源最短门路问题，即 Dijkstra 算法，此时须要计算最多的顶点；

这里有一个重要的概念是 估价算法 ，个别咱们应用 曼哈顿间隔 来进行估价，即 H(n) = D * (abs ( n.x – goal.x) + abs (n.y – goal.y) )。

（图来自维基百科 https://zh.wikipedia.org/wiki/A*%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95）

一个残缺的代码模板：

grid = [[0, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 0],
    [0, 0, 0, 0, 1, 0],
]

"""
heuristic = [[9, 8, 7, 6, 5, 4],
             [8, 7, 6, 5, 4, 3],
             [7, 6, 5, 4, 3, 2],
             [6, 5, 4, 3, 2, 1],
             [5, 4, 3, 2, 1, 0]]"""

init = [0, 0]
goal = [len(grid) - 1, len(grid[0]) - 1]  # all coordinates are given in format [y,x]
cost = 1

# the cost map which pushes the path closer to the goal
heuristic = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
for i in range(len(grid)):
    for j in range(len(grid[0])):
        heuristic[i][j] = abs(i - goal[0]) + abs(j - goal[1])
        if grid[i][j] == 1:
            heuristic[i][j] = 99  # added extra penalty in the heuristic map


# the actions we can take
delta = [[-1, 0], [0, -1], [1, 0], [0, 1]]  # go up  # go left  # go down  # go right


# function to search the path
def search(grid, init, goal, cost, heuristic):

    closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))
    ]  # the reference grid
    closed[init[0]][init[1]] = 1
    action = [[0 for col in range(len(grid[0]))] for row in range(len(grid))
    ]  # the action grid

    x = init[0]
    y = init[1]
    g = 0
    f = g + heuristic[init[0]][init[0]]
    cell = [[f, g, x, y]]

    found = False  # flag that is set when search is complete
    resign = False  # flag set if we can't find expand

    while not found and not resign:
        if len(cell) == 0:
            return "FAIL"
        else:  # to choose the least costliest action so as to move closer to the goal
            cell.sort()
            cell.reverse()
            next = cell.pop()
            x = next[2]
            y = next[3]
            g = next[1]

            if x == goal[0] and y == goal[1]:
                found = True
            else:
                for i in range(len(delta)):  # to try out different valid actions
                    x2 = x + delta[i][0]
                    y2 = y + delta[i][1]
                    if x2 >= 0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]):
                        if closed[x2][y2] == 0 and grid[x2][y2] == 0:
                            g2 = g + cost
                            f2 = g2 + heuristic[x2][y2]
                            cell.append([f2, g2, x2, y2])
                            closed[x2][y2] = 1
                            action[x2][y2] = i
    invpath = []
    x = goal[0]
    y = goal[1]
    invpath.append([x, y])  # we get the reverse path from here
    while x != init[0] or y != init[1]:
        x2 = x - delta[action[x][y]][0]
        y2 = y - delta[action[x][y]][1]
        x = x2
        y = y2
        invpath.append([x, y])

    path = []
    for i in range(len(invpath)):
        path.append(invpath[len(invpath) - 1 - i])
    print("ACTION MAP")
    for i in range(len(action)):
        print(action[i])

    return path


a = search(grid, init, goal, cost, heuristic)
for i in range(len(a)):
    print(a[i])

典型题目 1263. 推箱子

二分图我在这两道题中讲过了，大家看一下之后把这两道题做一下就行了。其实这两道题和一道题没啥区别。

0886. 可能的二分法
0785. 判断二分图

举荐程序为：先看 886 再看 785。

了解图的常见概念，咱们就算入门了。接下来，咱们就能够做题了。

个别的图题目有两种，一种是搜寻题目，一种是动静布局题目。

对于搜寻类题目，咱们能够：

第一步都是建图
第二步都是基于第一步的图进行遍历以寻找可行解

如果题目阐明了是无环图，咱们能够不应用 visited 数组，否则大多数都须要 visited 数组。当然也能够抉择原地算法缩小空间复杂度，具体的搜寻技巧会在专题篇的搜寻篇进行探讨。

图的题目相对而言比拟难，尤其是代码书写层面。然而就面试题目而言，图的题目类型却不多。

就搜寻题目来说，很多题目都是套模板就能够解决。因而倡议大家多练习模板，并本人多手敲，确保能够本人敲进去。
而对于动静布局题目，一个经典的例子就是Floyd-Warshall 算法，了解好了之后大家无妨拿 787. K 站直达内最便宜的航班 练习一下。当然这要求大家应该先学习动静布局，对于动静布局，咱们会在前面的《动静布局》以及《背包问题》中进行深度解说。

常见的图的板子题有以下几种：

最短路。算法有 DJ 算法，floyd 算法和 bellman 算法。这其中有的是单源算法，有的是多源算法，有的是贪婪算法，有的是动静布局。
拓扑排序。拓扑排序能够应用 bfs，也能够应用 dfs。相比于最短路，这种题目属于晓得了就简略的类型。
最小生成树。最小生成树是这三种题型中呈现频率最低的，能够最初冲破。
A 星寻路和二分图题目比例非常低，大家能够依据本人的状况选择性把握。

关于图:面试中图论都考什么这篇文章告诉你

图

基本概念

无向图 & 有向图〔Undirected Graph & Deriected Graph〕

有权图 & 无权图〔Weighted Graph & Unweighted Graph〕

入度 & 出度〔Indegree & Outdegree〕

门路 & 环〔门路：Path〕

连通图 & 强连通图

生成树

图的建设

邻接矩阵（常见）〔Adjacency Matrixs〕

邻接表〔Adjacency List〕

图的遍历

深度优先遍历〔Depth First Search, DFS〕

广度优先搜寻〔Breadth First Search, BFS〕

常见算法

最短距离，最短门路

Dijkstra 算法

Floyd-Warshall 算法

贝尔曼 - 福特算法

拓扑排序

Kahn 算法

最小生成树

Kruskal

Prim

两种算法比拟

其余算法

A 星寻路算法

二分图

总结