> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/10.-graph/introduction.md). # Introduction 一幅图是由**节点**和**边**构成的，逻辑结构如下： [![](https://labuladong.github.io/algo/images/%e5%9b%be/0.jpg)](https://labuladong.github.io/algo/images/%e5%9b%be/0.jpg) **什么叫「逻辑结构」？就是说为了方便研究，我们把图抽象成这个样子**。 根据这个逻辑结构，我们可以认为每个节点的实现如下： ```java /* 图节点的逻辑结构 */ class Vertex { int id; Vertex[] neighbors; } ``` 看到这个实现，你有没有很熟悉？它和我们之前说的多叉树节点几乎完全一样： ```java /* 基本的 N 叉树节点 */ class TreeNode { int val; TreeNode[] children; } ``` 所以说，图真的没啥高深的，就是高级点的多叉树而已。 不过呢，上面的这种实现是「逻辑上的」，实际上我们很少用这个 `Vertex` 类实现图，而是用常说的**邻接表和邻接矩阵**来实现。 比如还是刚才那幅图： [![](https://labuladong.github.io/algo/images/%e5%9b%be/0.jpg)](https://labuladong.github.io/algo/images/%e5%9b%be/0.jpg) 用邻接表和邻接矩阵的存储方式如下： [![](https://labuladong.github.io/algo/images/%e5%9b%be/2.jpeg)](https://labuladong.github.io/algo/images/%e5%9b%be/2.jpeg) 邻接表很直观，我把每个节点 `x` 的邻居都存到一个列表里，然后把 `x` 和这个列表关联起来，这样就可以通过一个节点 `x` 找到它的所有相邻节点。 邻接矩阵则是一个二维布尔数组，我们权且称为 `matrix`，如果节点 `x` 和 `y` 是相连的，那么就把 `matrix[x][y]` 设为 `true`（上图中绿色的方格代表 `true`）。如果想找节点 `x` 的邻居，去扫一圈 `matrix[x][..]` 就行了。 如果用代码的形式来表现，邻接表和邻接矩阵大概长这样： ```java // 邻接矩阵 // graph[x] 存储 x 的所有邻居节点 List[] graph; // 邻接矩阵 // matrix[x][y] 记录 x 是否有一条指向 y 的边 boolean[][] matrix; ``` **那么，为什么有这两种存储图的方式呢？肯定是因为他们各有优劣**。 对于邻接表，好处是占用的空间少。 你看邻接矩阵里面空着那么多位置，肯定需要更多的存储空间。 但是，邻接表无法快速判断两个节点是否相邻。 比如说我想判断节点 `1` 是否和节点 `3` 相邻，我要去邻接表里 `1` 对应的邻居列表里查找 `3` 是否存在。但对于邻接矩阵就简单了，只要看看 `matrix[1][3]` 就知道了，效率高。 所以说，使用哪一种方式实现图，要看具体情况。 好了，对于「图」这种数据结构，能看懂上面这些就绰绰够用了。 那你可能会问，我们这个图的模型仅仅是「有向无权图」，不是还有什么加权图，无向图，等等…… **其实，这些更复杂的模型都是基于这个最简单的图衍生出来的**。 **有向加权图怎么实现**？很简单呀： 如果是邻接表，我们不仅仅存储某个节点 `x` 的所有邻居节点，还存储 `x` 到每个邻居的权重，不就实现加权有向图了吗？ 如果是邻接矩阵，`matrix[x][y]` 不再是布尔值，而是一个 int 值，0 表示没有连接，其他值表示权重，不就变成加权有向图了吗？ 如果用代码的形式来表现，大概长这样： ```java // 邻接矩阵 // graph[x] 存储 x 的所有邻居节点以及对应的权重 List[] graph; // 邻接矩阵 // matrix[x][y] 记录 x 指向 y 的边的权重，0 表示不相邻 int[][] matrix; ``` **无向图怎么实现**？也很简单，所谓的「无向」，是不是等同于「双向」？ [![](https://labuladong.github.io/algo/images/%e5%9b%be/3.jpeg)](https://labuladong.github.io/algo/images/%e5%9b%be/3.jpeg) 如果连接无向图中的节点 `x` 和 `y`，把 `matrix[x][y]` 和 `matrix[y][x]` 都变成 `true` 不就行了；邻接表也是类似的操作，在 `x` 的邻居列表里添加 `y`，同时在 `y` 的邻居列表里添加 `x`。 把上面的技巧合起来，就变成了无向加权图…… 好了，关于图的基本介绍就到这里，现在不管来什么乱七八糟的图，你心里应该都有底了。 下面来看看所有数据结构都逃不过的问题：遍历。 #### 图的遍历 [**学习数据结构和算法的框架思维**](https://labuladong.github.io/algo/1/2/) **说过，各种数据结构被发明出来无非就是为了遍历和访问，所以「遍历」是所有数据结构的基础**。 图怎么遍历？还是那句话，参考多叉树，多叉树的遍历框架如下： ```java /* 多叉树遍历框架 */ void traverse(TreeNode root) { if (root == null) return; for (TreeNode child : root.children) { traverse(child); } } ``` 图和多叉树最大的区别是，图是可能包含环的，你从图的某一个节点开始遍历，有可能走了一圈又回到这个节点。 所以，如果图包含环，遍历框架就要一个 `visited` 数组进行辅助： ```java // 记录被遍历过的节点 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` 数组的区别，因为二叉树算是特殊的图，所以用遍历二叉树的过程来理解下这两个数组的区别： [![](https://labuladong.github.io/algo/images/%e8%bf%ad%e4%bb%a3%e9%81%8d%e5%8e%86%e4%ba%8c%e5%8f%89%e6%a0%91/1.gif)](https://labuladong.github.io/algo/images/%e8%bf%ad%e4%bb%a3%e9%81%8d%e5%8e%86%e4%ba%8c%e5%8f%89%e6%a0%91/1.gif) **上述 GIF 描述了递归遍历二叉树的过程，在 `visited` 中被标记为 true 的节点用灰色表示，在 `onPath` 中被标记为 true 的节点用绿色表示**，这下你可以理解它们二者的区别了吧。 如果让你处理路径相关的问题，这个 `onPath` 变量是肯定会被用到的，比如 [拓扑排序](https://labuladong.github.io/algo/2/19/35/) 中就有运用。 另外，你应该注意到了，这个 `onPath` 数组的操作很像 [回溯算法核心套路](https://labuladong.github.io/algo/4/29/105/) 中做「做选择」和「撤销选择」，区别在于位置： **回溯算法的「做选择」和「撤销选择」在 for 循环****里面**， **`onPath` 数组的操作在 for 循环****外面**。 在 for 循环里面和外面唯一的区别就是对根节点的处理。 比如下面两种多叉树的遍历： ```java 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); } } ``` 前者会正确打印所有节点的进入和离开信息，而后者唯独会少打印整棵树根节点的进入和离开信息。 为什么回溯算法框架会用后者？因为回溯算法关注的不是节点，而是树枝，不信你看 [回溯算法核心套路](https://labuladong.github.io/algo/4/29/105/) 里面的图。 显然，对于这里「图」的遍历，我们应该把 `onPath` 的操作放到 for 循环外面，否则会漏掉记录起始点的遍历。 说了这么多 `onPath` 数组，再说下 `visited` 数组，其目的很明显了，由于图可能含有环，`visited` 数组就是防止递归重复遍历同一个节点进入死循环的。 当然，如果题目告诉你图中不含环，可以把 `visited` 数组都省掉，基本就是多叉树的遍历。 ### 图算法 前数据结构相关的算法无非两点：遍历 + 访问。那么图的基本遍历方法也很简单，前文 [图算法基础](https://labuladong.github.io/algo/2/19/34/) 就讲了如何从多叉树的遍历框架扩展到图的遍历。 图这种数据结构还有一些比较特殊的算法，比如二分图判断，有环图无环图的判断，拓扑排序，以及最经典的最小生成树，单源最短路径问题，更难的就是类似网络流这样的问题。 不过以我的经验呢，像网络流这种问题，你又不是打竞赛的，除非自己特别有兴趣，否则就没必要学了；像最小生成树和最短路径问题，虽然从刷题的角度用到的不多，但它们属于经典算法，学有余力可以掌握一下；像拓扑排序这一类，属于比较基本且有用的算法，应该比较熟练地掌握。 图论算法：有向图的环检测、拓扑排序算法。 1. 有向图的环检测 [环检测和拓扑排序](https://labuladong.github.io/algo/2/19/35/) 2. 拓扑排序算法 [环检测和拓扑排序](https://labuladong.github.io/algo/2/19/35/) 3. 二分图判定 4. [图遍历算法](https://labuladong.github.io/algo/2/19/34/) 5. [名流问题](https://labuladong.github.io/algo/2/19/40/) 6. [并查集算法计算连通分量](https://labuladong.github.io/algo/2/19/37/) 7. [Dijkstra ](https://labuladong.github.io/algo/2/19/41/)