读完本文，能够去力扣解决如下题目：
797. 所有可能的门路（Medium）
常常有读者问我「图」这种数据结构，因为咱们公众号什么数据结构和算法都写过了，唯独没有专门介绍「图」。
其实在 学习数据结构和算法的框架思维 中说过，尽管图能够玩出更多的算法，解决更简单的问题，但实质上图能够认为是多叉树的延长。
面试口试很少呈现图相干的问题，就算有，大多也是简略的遍历问题，基本上能够齐全照搬多叉树的遍历。
至于最小生成树，Dijkstra，网络流这些算法问题，他们当然很牛逼，然而，就算法口试来说，学习的老本高但收益低，没什么性价比，不如多刷几道动静布局，真的。
那么，本文仍然秉持咱们号的格调，只讲「图」最实用的，离咱们最近的局部，让你心里对图有个直观的意识。
图的逻辑构造和具体实现
一幅图是由节点和边形成的，逻辑构造如下：
什么叫「逻辑构造」？就是说为了不便钻研，咱们把图形象成这个样子。
依据这个逻辑构造，咱们能够认为每个节点的实现如下：
/* 图节点的逻辑构造 */class Vertex { int id; Vertex[] neighbors;}看到这个实现，你有没有很相熟？它和咱们之前说的多叉树节点简直齐全一样：
/* 根本的 N 叉树节点 */class TreeNode { int val; TreeNode[] children;}所以说，图真的没啥浅近的，就是高级点的多叉树而已。
不过呢，下面的这种实现是「逻辑上的」，实际上咱们很少用这个Vertex类实现图，而是用常说的邻接表和邻接矩阵来实现。
比方还是方才那幅图：
用邻接表和邻接矩阵的存储形式如下：
邻接表很直观，我把每个节点x的街坊都存到一个列表里，而后把x和这个列表关联起来，这样就能够通过一个节点x找到它的所有相邻节点。
邻接矩阵则是一个二维布尔数组，咱们姑且成为matrix，如果节点x和y是相连的，那么就把matrix[x][y]设为true。如果想找节点x的街坊，去扫一圈matrix[x][..]就行了。
那么，为什么有这两种存储图的形式呢？必定是因为他们各有优劣。
对于邻接表，益处是占用的空间少。
你看邻接矩阵外面空着那么多地位，必定须要更多的存储空间。
然而，邻接表无奈疾速判断两个节点是否相邻。
比如说我想判断节点1是否和节点3相邻，我要去邻接表里1对应的街坊列表里查找3是否存在。但对于邻接矩阵就简略了，只有看看matrix[1][3]就晓得了，效率高。
所以说，应用哪一种形式实现图，要看具体情况。
好了，对于「图」这种数据结构，能看懂下面这些就绰绰够用了。
那你可能会问，咱们这个图的模型仅仅是「有向无权图」，不是还有什么加权图，无向图，等等……
其实，这些更简单的模型都是基于这个最简略的图衍生进去的。
有向加权图怎么实现？很简略呀：
如果是邻接表，咱们不仅仅存储某个节点x的所有街坊节点，还存储x到每个街坊的权重，不就实现加权有向图了吗？
如果是邻接矩阵，matrix[x][y]不再是布尔值，而是一个 int 值，0 示意没有连贯，其余值示意权重，不就变成加权有向图了吗？
无向图怎么实现？也很简略，所谓的「无向」，是不是等同于「双向」？
如果连贯无向图中的节点x和y，把matrix[x][y]和matrix[y][x]都变成true不就行了；邻接表也是相似的操作。
把下面的技巧合起来，就变成了无向加权图……
好了，对于图的根本介绍就到这里，当初不论来什么乌七八糟的图，你心里应该都有底了。
上面来看看所有数据结构都逃不过的问题：遍历。
图的遍历
图怎么遍历？还是那句话，参考多叉树，多叉树的遍历框架如下：
/* 多叉树遍历框架 */void traverse(TreeNode root) { if (root == null) return; for (TreeNode child : root.children) traverse(child);}图和多叉树最大的区别是，图是可能蕴含环的，你从图的某一个节点开始遍历，有可能走了一圈又回到这个节点。
所以，如果图蕴含环，遍历框架就要一个visited数组进行辅助：
Graph graph;boolean[] visited;/* 图遍历框架 */void traverse(Graph graph, int s) { if (visited[s]) return; // 通过节点 s visited[s] = true; for (TreeNode neighbor : graph.neighbors(s)) traverse(neighbor); // 来到节点 s visited[s] = false; }好吧，看到这个框架，你是不是又想到了 回溯算法外围套路 中的回溯算法框架？
这个visited数组的操作很像回溯算法做「做抉择」和「撤销抉择」，区别在于地位，回溯算法的「做抉择」和「撤销抉择」在 for 循环外面，而对visited数组的操作在 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); }}前者会正确打印所有节点的进入和来到信息，而后者唯独会少打印整棵树根节点的进入和来到信息。
为什么回溯算法框架会用后者？因为回溯算法关注的不是节点，而是树枝，不信你看 回溯算法外围套路 外面的图，它能够疏忽根节点。
显然，对于这里「图」的遍历，咱们应该把visited的操作放到 for 循环里面，否则会漏掉起始点的遍历。
当然，当有向图含有环的时候才须要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();}这道题就这样解决了。
最初总结一下，图的存储形式次要有邻接表和邻接矩阵，无论什么花里胡哨的图，都能够用这两种形式存储。
在口试中，最常考的算法是图的遍历，和多叉树的遍历框架是十分相似的。
当然，图还会有很多其余的乏味算法，比方二分图断定呀，环检测呀（编译器循环援用检测就是相似的算法）等等，当前有机会再讲吧，本文就到这了。
查看更多优质算法文章 点击这里，手把手带你刷力扣，致力于把算法讲清楚！我的 算法教程 曾经取得 90k star，欢送点赞！