code前端网图论算法基础 - 本质上是多树的扩展，
图可以发挥更多的算法，解决更复杂的问题，但本质上图可以认为是多树的扩展。
笔试中很少有与图表相关的问题。即使有，大多数都是简单的遍历问题。基本上，多树的遍历是可以完全复制的。
所以这篇文章还是沿袭了我们账号的风格，只讲“图”最实用、最贴近的部分，让大家对图有一个直观的认识。在文章的最后我给出了其他经典的图论算法。看完这篇文章你应该能明白了。
图的逻辑结构及具体实现
图由节点和边组成。逻辑结构如下： 什么是“逻辑结构”？也就是说，为了方便研究，我们将图像抽象为这样。 根据这个逻辑结构，我们可以想到每个节点的实现如下： 这个实现你熟悉吗？它和我们之前提到的多树节点几乎一模一样： 所以，这个图并不是真正高级的，它只是一个高级的多树。 然而，上述实现是“合乎逻辑的”。事实上，我们很少使用这个 比如现在的图片： 使用邻接列表和邻接矩阵的存储方法如下： 邻接区域列表非常直观。我将每个节点 邻接矩阵是一个二维布尔矩阵，我们称之为 用代码来表达，邻接表和邻接矩阵是这样的： 那么，为什么会有这两种存储图的方式呢？一定是因为他们各有各的优点和缺点。 对于连接列表来说，优点是占用空间少。 你看邻接矩阵中有这么多空位置，这肯定需要更多的存储空间。 但是链表无法快速判断两个节点是否相邻。 例如，如果我想查出节点 所以用哪种方法来实现图需要根据具体情况而定。 好吧，对于“图”这样的数据结构，理解上面就足够了。 那么你可能会问，我们图的模型只是一个“有向无权图”，是不是还有一些其他的带权图、无向图等等…… 其实这些更复杂的模型都是基于在这个最简单的图表上。 如何在有向加权图中实现？很简单： 如果是邻接表，我们不仅存储特定节点 如果是邻接矩阵， 如果用代码的形式表达的话，可能是这样的： 如何实现无向图？这也很简单。所谓“无向”和“双向”一样吗？中 如果节点 将上述技术放在一起会产生一个无向加权图... 好吧，这就是图的基本介绍。现在，无论出现什么混乱的图表，您都应该有一个好主意。 。 我们来看一个所有数据结构都无法逃避的问题：遍历。 学习数据结构和算法的框架。有人说，各种数据结构的发明就是为了遍历和访问，所以“遍历”是所有数据结构的基础。 如何遍历图？再次参考多树。多树的遍历框架如下： 图与多树的主要区别在于图可以包含环。如果从图中的某个节点开始遍历，有可能逛了一会又回到这个节点。 所以，如果图包含环，则遍历框架需要一个 注意 上面的GIF描述了递归遍历二叉树的过程，在 如果让你处理路径相关的问题，肯定会用到这个变量 另外，大家应该注意到了，这个 for循环内部和外部唯一的区别就是根节点的处理。 例如下面两个多树遍历： 前者会正确打印所有节点的输入输出信息，而后者只会打印整棵树的根节点的少量输入输出信息。 为什么回溯算法框架采用后者？因为回溯算法关注的不是节点而是分支。不信你看《回溯算法核心例程》中的图。 为了回顾这里的“图”，我们当然应该在for循环之外添加 讲了这么多 当然，如果问题告诉你图中没有循环，你可以省略 我们来看看理口第797题“所有可能的方法”。函数签名如下： 问题输入一个有向无环图。该图包含 有 n 表示的 例如，输入 算法应返回 解决办法非常简单。以 由于输入图是非循环的，所以我们不需要 这个问题是这样解决的，通过Java，当你添加 最后，总结一下，存储图形最重要的方式是页列表和邻接矩阵。无论图表多么花哨，都可以用这两种方式存储。 笔试中，考的最多的算法是图遍历，它和多树遍历框架非常相似。 当然，还有很多其他有趣的图算法，比如二分图判定、循环检测和拓扑排序（编译器的循环引用检测是类似的算法）、最小生成树、Dijkstra 的最短路径算法等。 ，如果有兴趣的读者可以去看一下，本文到此结束。 作者：labuladong 公众号：labuladong
/* 图节点的逻辑结构 */
class Vertex {
int id;
Vertex[] neighbors;
}
/* 基本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;
}
Vertex类实现图。相反，我们使用经常提到的 邻接列表和邻接矩阵 来实现这一点。 
x存储在列表中，然后将x与这个列表关联起来，这样就可以通过节点x找到它的所有相邻节点。 矩阵。如果节点 x 和 y 连接，则 matrix[x][y] （上图中的绿色方块代表true ）。如果你想在节点x找到邻居，只需扫描matrix[x][..]即可。 // 邻接矩阵
// graph[x] 存储 x 的所有邻居节点
List<Integer>[] graph;
// 邻接矩阵
// matrix[x][y] 记录 x 是否有一条指向 y 的边
boolean[][] matrix;
1是否与节点3相邻，我需要查明3是否存在于邻接列表中与1对应的邻居列表中。但对于邻接矩阵来说，这很容易。只要看看 matrix[1][3] 就知道它是有效的。 x的所有邻居节点，还存储❀x中每个邻居的权重xx。权重有向图？ matrix[x][y]不再是boolean值，而是int值。 0表示不相关，其他值代表权重，否则对权重进行修正。你想象到了吗？ // 邻接矩阵
// graph[x] 存储 x 的所有邻居节点以及对应的权重
List<int[]>[] graph;
// 邻接矩阵
// matrix[x][y] 记录 x 指向 y 的边的权重，0 表示不相邻
int[][] matrix;
x 和 y 
visited❙ onPath 的区别数组之间，因为二叉树是一种特殊的图，我们通过遍历二叉树的过程来理解两个矩阵的区别： 矩阵 [x] [y] ] 和 [xy♝] 和 ♶y 都变成 真实。邻接表也是类似的操作。将y添加到x的邻居名单中，同时添加xx，同时添加 x❝y。 遍历图
/* 多叉树遍历框架 */
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 (visitedSpread收缩) return;
// 经过节点 s，标记为已遍历
visitedSpread收缩 = true;
// 做选择：标记节点 s 在路径上
onPathSpread收缩 = true;
for (int neighbor : graph.neighbors(s)) {
traverse(graph, neighbor);
}
// 撤销选择：节点 s 离开路径
onPathSpread收缩 = false;
}
中标记为true已访问的 节点以灰色表示，在 onPath 中标记为 true 的节点以绿色 表示。现在您可以了解它们之间的区别了。 onPath，比如拓扑排序时用到。 onPath数组的操作与回溯算法核心例程中的“做出选择”和“撤消选择”非常相似。不同之处在于回溯算法中“做出选择”的位置。 “撤消选择”位于 for 循环内部，而对 onPath 数组的操作位于 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的操作，否则会错过记录起点的交叉。 onPath数组，我们来谈谈visited数组。目的很明显。由于图可能包含循环，visited防止递归重复遍历同一个节点会进入无限循环。 visited矩阵，这基本上是多树遍历。 题目练习
List<List<Integer>> allPathsSourceTarget(int[][] graph);
0, 1, 2,..., n - 1。计算从节点 0 到节点 n - 1 路径的所有节点。图实际上是一个用“链表”表示的图。 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 : graphSpread收缩) {
traverse(graph, v, path);
}
// 从路径移出节点 s
path.removeLast();
}
路径到res，必须复制一个新列表，否则res中的列表将为空。
版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
