读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：
797. 所有可能的门路（中等）
———–
常常有读者问我「图」这种数据结构，其实我在 学习数据结构和算法的框架思维 中说过，尽管图能够玩出更多的算法，解决更简单的问题，但实质上图能够认为是多叉树的延长。
面试口试很少呈现图相干的问题，就算有，大多也是简略的遍历问题，基本上能够齐全照搬多叉树的遍历。
那么，本文仍然秉持咱们号的格调，只讲「图」最实用的，离咱们最近的局部，让你心里对图有个直观的意识，文末我给出了其余经典图论算法，了解本文后应该都能够拿下的。
图的逻辑构造和具体实现
一幅图是由 节点 和边 形成的，逻辑构造如下：
什么叫「逻辑构造」？就是说为了不便钻研，咱们把图形象成这个样子。
依据这个逻辑构造，咱们能够认为每个节点的实现如下：
/* 图节点的逻辑构造 */
class Vertex {
int id;
Vertex[] neighbors;}看到这个实现，你有没有很相熟？它和咱们之前说的多叉树节点简直齐全一样：
/* 根本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;}所以说，图真的没啥浅近的，就是高级点的多叉树而已。
不过呢，下面的这种实现是「逻辑上的」，实际上咱们很少用这个 Vertex 类实现图，而是用常说的 邻接表和邻接矩阵 来实现。
比方还是方才那幅图：
用邻接表和邻接矩阵的存储形式如下：
邻接表很直观，我把每个节点 x 的街坊都存到一个列表里，而后把 x 和这个列表关联起来，这样就能够通过一个节点 x 找到它的所有相邻节点。
邻接矩阵则是一个二维布尔数组，咱们姑且称为 matrix，如果节点 x 和 y 是相连的，那么就把 matrix[x][y] 设为 true（上图中绿色的方格代表 true）。如果想找节点 x 的街坊，去扫一圈 matrix[x][..] 就行了。
如果用代码的模式来体现，邻接表和邻接矩阵大略长这样：
// 邻接矩阵
// graph[x] 存储 x 的所有街坊节点
List<Integer>[] graph;
// 邻接矩阵
// matrix[x][y] 记录 x 是否有一条指向 y 的边
boolean[][] matrix;那么，为什么有这两种存储图的形式呢？必定是因为他们各有优劣。
对于邻接表，益处是占用的空间少。
你看邻接矩阵外面空着那么多地位，必定须要更多的存储空间。
然而，邻接表无奈疾速判断两个节点是否相邻。
比如说我想判断节点 1 是否和节点 3 相邻，我要去邻接表里 1 对应的街坊列表里查找 3 是否存在。但对于邻接矩阵就简略了，只有看看 matrix[1][3] 就晓得了，效率高。
所以说，应用哪一种形式实现图，要看具体情况。
好了，对于「图」这种数据结构，能看懂下面这些就绰绰够用了。
那你可能会问，咱们这个图的模型仅仅是「有向无权图」，不是还有什么加权图，无向图，等等……
其实，这些更简单的模型都是基于这个最简略的图衍生进去的。
有向加权图怎么实现？很简略呀：
如果是邻接表，咱们不仅仅存储某个节点 x 的所有街坊节点，还存储 x 到每个街坊的权重，不就实现加权有向图了吗？
如果是邻接矩阵，matrix[x][y] 不再是布尔值，而是一个 int 值，0 示意没有连贯，其余值示意权重，不就变成加权有向图了吗？
如果用代码的模式来体现，大略长这样：
// 邻接矩阵
// graph[x] 存储 x 的所有街坊节点以及对应的权重
List<int[]>[] graph;
// 邻接矩阵
// matrix[x][y] 记录 x 指向 y 的边的权重，0 示意不相邻
int[][] matrix;无向图怎么实现？也很简略，所谓的「无向」，是不是等同于「双向」？
如果连贯无向图中的节点 x 和 y，把 matrix[x][y] 和 matrix[y][x] 都变成 true 不就行了；邻接表也是相似的操作，在 x 的街坊列表里增加 y，同时在 y 的街坊列表里增加 x。
把下面的技巧合起来，就变成了无向加权图……
好了，对于图的根本介绍就到这里，当初不论来什么乌七八糟的图，你心里应该都有底了。
上面来看看所有数据结构都逃不过的问题：遍历。
图的遍历
学习数据结构和算法的框架思维 说过，各种数据结构被创造进去无非就是为了遍历和拜访，所以「遍历」是所有数据结构的根底。
图怎么遍历？还是那句话，参考多叉树，多叉树的遍历框架如下：
/* 多叉树遍历框架 */
void traverse(TreeNode root) {if (root == null) return;
for (TreeNode child : root.children) {traverse(child);
}
}图和多叉树最大的区别是，图是可能蕴含环的，你从图的某一个节点开始遍历，有可能走了一圈又回到这个节点。
所以，如果图蕴含环，遍历框架就要一个 visited 数组进行辅助：
// 记录被遍历过的节点
boolean[] visited;
// 记录从终点到以后节点的门路
boolean[] onPath;
/* 图遍历框架 */
void traverse(Graph graph, int s) {if (visited[s]) return;
// 通过节点 s，标记为已遍历
visited[s] = true;
// 做抉择：标记节点 s 在门路上
onPath[s] = true;
for (int neighbor : graph.neighbors(s)) {traverse(graph, neighbor);
}
// 撤销抉择：节点 s 来到门路
onPath[s] = false;
}留神 visited 数组和 onPath 数组的区别，因为二叉树算是非凡的图，所以用遍历二叉树的过程来了解下这两个数组的区别：
上述 GIF 形容了递归遍历二叉树的过程，在 visited 中被标记为 true 的节点用灰色示意，在 onPath 中被标记为 true 的节点用绿色示意，这下你能够了解它们二者的区别了吧。
如果让你解决门路相干的问题，这个 onPath 变量是必定会被用到的，比方 拓扑排序 中就有使用。
另外，你应该留神到了，这个 onPath 数组的操作很像 回溯算法外围套路 中做「做抉择」和「撤销抉择」，区别在于地位：回溯算法的「做抉择」和「撤销抉择」在 for 循环外面，而对 onPath 数组的操作在 for 循环里面。
在 for 循环外面和里面惟一的区别就是对根节点的解决。
比方上面两种多叉树的遍历：
void traverse(TreeNode root) {if (root == null) return;
System.out.println("enter:" + root.val);
for (TreeNode child : root.children) {traverse(child);
}
System.out.println("leave:" + root.val);
}
void traverse(TreeNode root) {if (root == null) return;
for (TreeNode child : root.children) {System.out.println("enter:" + child.val);
traverse(child);
System.out.println("leave:" + child.val);
}
}前者会正确打印所有节点的进入和来到信息，而后者唯独会少打印整棵树根节点的进入和来到信息。
为什么回溯算法框架会用后者？因为回溯算法关注的不是节点，而是树枝，不信你看 回溯算法外围套路 外面的图。
显然，对于这里「图」的遍历，咱们应该把 onPath 的操作放到 for 循环里面，否则会漏掉记录起始点的遍历。
说了这么多 onPath 数组，再说下 visited 数组，其目标很显著了，因为图可能含有环，visited 数组就是避免递归反复遍历同一个节点进入死循环的。
当然，如果题目通知你图中不含环，能够把 visited 数组都省掉，根本就是多叉树的遍历。
题目实际
上面咱们来看力扣第 797 题「所有可能门路」，函数签名如下：
List<List<Integer>> allPathsSourceTarget(int[][] graph);题目输出一幅 有向无环图，这个图蕴含 n 个节点，标号为 0, 1, 2,..., n - 1，请你计算所有从节点 0 到节点 n - 1 的门路。
输出的这个 graph 其实就是「邻接表」示意的一幅图，graph[i] 存储这节点 i 的所有街坊节点。
比方输出 graph = [[1,2],[3],[3],[]]，就代表上面这幅图：
算法应该返回 [[0,1,3],[0,2,3]]，即 0 到 3 的所有门路。
解法很简略，以 0 为终点遍历图，同时记录遍历过的门路，当遍历到起点时将门路记录下来即可。
既然输出的图是无环的，咱们就不须要 visited 数组辅助了，间接套用图的遍历框架：
// 记录所有门路
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
// 保护递归过程中通过的门路
LinkedList<Integer> path = new LinkedList<>();
traverse(graph, 0, path);
return res;
}
/* 图的遍历框架 */
void traverse(int[][] graph, int s, LinkedList<Integer> path) {
// 增加节点 s 到门路
path.addLast(s);
int n = graph.length;
if (s == n - 1) {
// 达到起点
res.add(new LinkedList<>(path));
path.removeLast();
return;
}
// 递归每个相邻节点
for (int v : graph[s]) {traverse(graph, v, path);
}
// 从门路移出节点 s
path.removeLast();}这道题就这样解决了，留神 Java 的语言个性，向 res 中增加 path 时须要拷贝一个新的列表，否则最终 res 中的列表都是空的。
最初总结一下，图的存储形式次要有邻接表和邻接矩阵，无论什么花里胡哨的图，都能够用这两种形式存储。
在口试中，最常考的算法是图的遍历，和多叉树的遍历框架是十分相似的。
当然，图还会有很多其余的乏味算法，比方 二分图断定，环检测和拓扑排序（编译器循环援用检测就是相似的算法），最小生成树，Dijkstra 最短门路算法 等等，有趣味的读者能够去看看，本文就到这了。
_____________
查看更多优质算法文章 点击我的头像，手把手带你刷力扣，致力于把算法讲清楚！我的 算法教程 曾经取得 90k star，欢送点赞！