图论，
Graph[ɡræf] Theory，是数学的一个分支。
图，是由若干给定的点及连接两点的线所构成的图形，通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线代表两个事物间具有这种关系。
图是一种最复杂的数据结构，前面所说的各类数据结构，都可以看作是图的特例，既然如此，直接用图就好，为啥还要分这么多类型？
这是因为，大多时候，我们不需要用到这么复杂的功能，与其称之为图的xx特例，不如干脆分离出来。
数据结构是为算法服务的，其目的是为了更高效地存取数据，那么，什么类型的数据适合用图来存储呢？答案很简单，如果你用其他数据结构无法很好地进行存储，就用图；
举个栗子：如果我们要存储一种双向的朋友关系，并且这种朋友关系是多对多的，那就要用到图，因为其他数据结构无法很好的模拟。
图，分为 无向图（Undirected Graph）& 有向图（Deriected Graph）。
无向图，比如前面提到的二叉树；
有向图，以下重点介绍。
有向图
如果两个事务间的关系是有方向的，就是有向图，反之为无向图；
比如，A认识B，但是B不一定认识A，如果用无向图存储就无法得知到底是A认识B，还是B认识A。
习惯上，我们画图时用箭头标识方向，即，带箭头的为有向图，反之为无向图。
有权图（Weighted Graph）& 无权图（Unweighted Graph）
如果边是有权重的，则为有权图（带权图），反之为无权图（不带权图），该如何理解权重呢？比如，汇率，就是一种有权重的逻辑图。货币A，1个，可以兑换 货币B，7个，那么A和B的边的权重就是7，而上面提到的，朋友关系，这种就属于无权图。
入度（inDegree）&出度（outDegree）
有多少条边指向节点N，那么节点N的入度就是多少；同理，有多少条边从节点N出发，那么节点N的出度就是多少。
如下图所示，所有节点的入度和出度都为 1。
路径&环
- 有环图（Cyclic['saɪklɪk] Graph），上面的图就是一个有环图，因为我们可以从任一节点出发，最终回到起点；
- 无环图（Acyclic[ˌeɪ'saɪklɪk] Graph）：参考 二叉树 结构；
连通图&强连通图
- 无向图中，若任意两个顶点 i 与 j 都有路径相通，则称该无向图为连通图；
- 有向图中，若任意两个顶点 i 与 j 都有路径相通，则称该有向图为强连通图；
生成树
一个连通图的生成树是指：一个连通子图，虽然包含构成图的全部n个顶点，但却只有构成一棵树的 n-1 条边，并且，有且仅有 n-1 条边，如果生成树再添加一条边，则必定构成环。
在连通图的所有生成树中，所有边的【代价和最小】的生成树，称为最小生成树，代价和，指所有边的 权重和。
图的建立
一般来说，LC中的图相关题目，都不会给你一个现成的图的数据结构，所以，当你意识到这是一个图类型的题目时，解题的第一步通常是，建图。
我们知道，图是由点和边组成的，所以我们只要存储图中的所有边的关系即可，因为边中已经包含了两个点的关系。
两种常见的建图方式：邻接矩阵（常用且重要）& 邻接表
邻接矩阵（Adjacency[ə'dʒeɪsənsɪ] Matrixs）
可以使用数组或哈希表来存储图，这里我们使用二维数组。
用一个 n*n 的矩阵来描述图 graph，其中 graph[i][j] 用来描述边的关系。
一般而言，对于无权图，我们可以使用 graph[i][j] = 1 来表示 顶点 i 和顶点 j 之间有一条边，且边的指向是从 i 到 j；
用 graph[i][j] = 0 来表示 顶点 i 和顶点 j 之间不存在一条边；
对于有权图来说，我们可以存储其他数字，用来表示权重。
邻接矩阵的优点主要有：
- 直观，使用起来比较简单；
- 判断两个顶点是否连接，获取入度、出度，及更新度数，时间复杂度都是 O(1)；
因此，如无特殊必要，所有需要建图的题目都可以都用这种方式。
典型题目-LC-743. 网络延迟时间：
// 743. 网络延迟时间
function networkDelayTime($times, $n, $k) {
$graph = [];
foreach ($times as $sub) {
//建立邻接矩阵：From - To: time
$graph[$sub[0]][$sub[1]] = $sub[2];
}
$timeCost = $this->dijkstra($graph, $n, $k);
return $timeCost;
}
// dijkstra 不适用于带 负权 的计算；具体见如下代码
function dijkstra($graph, $n, $k) {
$got = []; // 已获取的，从 k 到 可到达的目标点 v(包含k自身) 的最短路径集合
$dist = []; // 从 k 到 目标点 v(包含k自身) 的最短路径的权值，即 网络延迟 的最短时间；
for ($i=1; $i <= $n; $i++) {
$dist[$i] = PHP_INT_MAX; // 初始均设为最大值 }
$dist[$k] = 0; // k 到达自身的最短时间为 0
$loopCnt = 0;
while ($loopCnt < $n) {
// 本次循环得到的【可到达的】最短路径节点，节点为正数，所以 -1 即可；
$toNode = -1;
for ($i=1; $i <= $n; $i++) {
if (isset($got[$i])) {
// 已获取最短路径的节点，跳过
continue;
}
if ($toNode == -1 || $dist[$i] < $dist[$toNode]) {
$toNode = $i;
}
}
$got[$toNode] = 1; // 标记本次获取的最短路径节点放入大集合，下次不再循环
// 重新计算并入本次获取的最短路径节点后的到达时间
for ($i=1; $i <= $n; $i++) {
if (!isset($graph[$toNode][$i])) {
// 如果未设置，则代表 本次获取的节点 不可直接到达 i 节点
continue;
}
// k 到本次获取的最短节点时间 + 本次节点到 i 的时间，即经过本次节点到 i 的最短时间
$dist[$i] = min($dist[$i], $graph[$toNode][$i] + $dist[$toNode]);
}
$loopCnt++;
}
$timeCost = max($dist);
if ($timeCost == PHP_INT_MAX) {
return -1;
}
return $timeCost;
}
图的遍历
常见的有两种方法：
深度优先遍历（Depth First Search, DFS）；
广度优先搜索（Breadth First Search, BFS）；
不管是哪种遍历方式， 如果图有环，一定要记录节点的访问情况（visited），防止死循环；
DFS 和 BFS 只是一种算法思想，不属于具体的算法，因此其有着很强的适应性，本文讲的图可以用，前文讲的树也可以用。实际上， 只要是非线性的数据结构都可以借用。
常见算法
图类型的题目比较适合套模板，这里介绍几种常见的板子题。主要有：
Dijkstra
Floyd-Warshall
最小生成树（Kruskal & Prim）
A 星寻路算法
二分图（染色法）〔Bipartitie〕
拓扑排序〔Topological Sort〕
这里简单介绍其中一个经典算法：Dijkstra 算法
Dijkstra 算法，俗称，最短距离 或 最短路径 算法；
Dijkstra 这个名字比较难记，可以简单记为DJ 算法。
基本思想是广度优先遍历。实际上搜索的最短路算法基本思想都是广度优先，只不过具体的扩展策略不同而已；
主要解决的是图中任意一点到图中另外任意一个点的最短距离，即单源最短路径。
比如给你几个城市，以及城市之间的距离。让你规划一条最短的从城市 a 到城市 b 的路线。
这个问题，我们就可以先将城市间的距离用图建立出来，然后使用 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 步
代码可参考上面的 LC-743. 网络延迟时间；
Floyd-Warshall 算法
算法主要思路很简洁，可以参考数学中的交换律：
如果 a->b 且 b->c，则a->c；
如果 a 能到b，b能到c，则a可以到c；
如果是带权图，则上面的判断逻辑追加条件即可，如果取最小路径，可以加判断：【a->b->c 】< 【a->c 】，再赋值即可。
代码主要逻辑为 3 层循环；
伪代码（JavaScript）：
function 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 dist;
}
总结
理解图的常见概念，我们就算入门了。接下来就可以做题了。
一般的图题目有两种，一种是搜索题目，一种是动态规划题目。
对于搜索类题目：
- 第一步都是建图
- 第二步都是基于第一步的图进行遍历以寻找可行解
- 如果题目说明了是无环图，我们可以不使用 visited 数组，否则大多数都需要 visited 数组。当然也可以选择原地算法减少空间复杂度，具体的搜索技巧会在专题篇的搜索篇进行讨论。
图的题目相对而言比较难，尤其是代码书写层面。
- 但，搜索类型的图题目，一般套模板就可以解决。因此大家可以多练习模板，多手动敲，确保自己能敲出来。
对于动态规划题目：
一个经典的例子就是 Floyd-Warshall 算法，理解好了之后大家不妨拿 LC-787. K 站中转内最便宜的航班 练习一下。当然这要求大家应该先学习动态规划。
常见的图的板子题有以下几种：
- 最短路：算法有 DJ 算法， floyd 算法 和 bellman 算法。这其中有的是单源算法，有的是多源算法，有的是贪心算法，有的是动态规划。
- 拓扑排序：拓扑排序可以使用 bfs ，也可以使用 dfs。相比于最短路，这种题目属于知道了就简单的类型。
- 最小生成树：最小生成树是这三种题型中出现频率最低的，可以最后突破。
- A 星寻路和二分图：这两种题目比例非常低，大家可以根据自己的情况选择性掌握。
----END----
