41.md

# 用于编码面试的图表备忘单

> 原文:[https://www.techinterviewhandbook.org/algorithms/graph/](https://www.techinterviewhandbook.org/algorithms/graph/)

<header>

## 简介[](#introduction "Direct link to heading")

图是包含一组对象(节点或顶点)的结构，其中在这些节点/顶点之间可以有边。边可以是有向的或无向的，并且可以选择性地具有值(加权图)。树是无向图，其中任意两个顶点仅由一条边连接，并且图中不能有圈。

图形通常用于对无序实体之间的关系进行建模，例如

*   人与人之间的友谊——每个节点都是一个人，节点之间的边表示这两个人是朋友。
*   位置之间的距离-每个节点都是一个位置，节点之间的边表示这些位置是相连的。边的值代表距离。

熟悉各种图形表示、图形搜索算法及其时间和空间复杂性。

## 学习资源[](#learning-resources "Direct link to heading")

*   读物
    *   [从理论到实践:表示图](https://medium.com/basecs/from-theory-to-practice-representing-graphs-cfd782c5be38)，basecs
    *   [深入研究一个图形:DFS 遍历](https://medium.com/basecs/deep-dive-through-a-graph-dfs-traversal-8177df5d0f13)，basecs
    *   [在图中变宽:BFS 遍历](https://medium.com/basecs/going-broad-in-a-graph-bfs-traversal-959bd1a09255)，basecs
*   附加(仅当您有时间时)
    *   在 Dijkstra 、basecs 的帮助下，寻找最短路径
    *   [用有向无环图](https://medium.com/basecs/spinning-around-in-cycles-with-directed-acyclic-graphs-a233496d4688)、basecs 循环打转

## 图形表示[](#graph-representations "Direct link to heading")

可以给你一个边的列表，你必须从这些边构建你自己的图，这样你就可以遍历它们。常见的图形表示有:

*   邻接矩阵
*   邻接表
*   哈希表中的哈希表

在算法面试中，使用哈希表中的哈希表是最简单的方法。在面试中，你很少不得不使用邻接矩阵或列表来解决图形问题。

在算法访谈中，通常在输入中以 2D 矩阵的形式给出图形，其中像元是节点，每个像元可以遍历其相邻像元(上/下/左/右)。因此，熟悉 2D 矩阵的遍历是很重要的。当遍历矩阵时，始终确保您的当前位置在矩阵的边界内，并且以前没有被访问过。

## 时间复杂度[](#time-complexity "Direct link to heading")

`|V|`是顶点的数量，而`|E|`是边的数量。

| 算法 | 大 O |
| --- | --- |
| 深度优先搜索 | o(&#124;V&#124;+&#124;E&#124;) |
| 广度优先搜索 | o(&#124;V&#124;+&#124;E&#124;) |
| 拓扑排序 | o(&#124;V&#124;+&#124;E&#124;) |

## 面试时要注意的事情[](#things-to-look-out-for-during-interviews "Direct link to heading")

*   树形图很可能是一个允许循环的图，简单的递归解决方案是行不通的。在这种情况下，您必须处理循环，并在遍历时保留一组已访问的节点。
*   确保正确跟踪已访问的节点，并且每个节点不会被访问超过一次。否则，您的代码可能会陷入无限循环。

## 拐角情况[](#corner-cases "Direct link to heading")

*   空图
*   有一个或两个节点的图
*   不相交的图
*   带循环的图形

## 图形搜索算法[](#graph-search-algorithms "Direct link to heading")

*   **常见的** -广度优先搜索、深度优先搜索
*   **不常见** -拓扑排序，Dijkstra 算法
*   **几乎没有**——贝尔曼-福特算法，弗洛伊德-沃肖尔算法，普里姆算法，克鲁斯卡尔算法。你的面试官可能也不认识他们。

### 深度优先搜索[](#depth-first-search "Direct link to heading")

深度优先搜索是一种图遍历算法，它在回溯之前尽可能地沿着每个分支进行探索。堆栈通常用于跟踪当前搜索路径上的节点。这可以通过隐式的[递归](/algorithms/recursion/)堆栈或者实际的[堆栈](/algorithms/stack/)数据结构来完成。

对矩阵进行深度优先搜索的简单模板如下:

```
def  dfs(matrix):  # Check for an empty matrix/graph.  if  not matrix:  return  []  rows, cols =  len(matrix),  len(matrix[0])  visited =  set()  directions =  ((0,  1),  (0,  -1),  (1,  0),  (-1,  0))  def  traverse(i, j):  if  (i, j)  in visited:  return  visited.add((i, j))  # Traverse neighbors.  for direction in directions:  next_i, next_j = i + direction[0], j + direction[1]  if  0  <= next_i < rows and  0  <= next_j < cols:  # Add in question-specific checks, where relevant.  traverse(next_i, next_j)  for i in  range(rows):  for j in  range(cols):  traverse(i, j) 
```

### 广度优先搜索[](#breadth-first-search "Direct link to heading")

广度优先搜索是一种图遍历算法，它从一个节点开始，在移动到下一个深度级别的节点之前，探索当前深度的所有节点。一个[队列](/algorithms/queue/)通常用于跟踪已经遇到但还没有探索的节点。

在矩阵上进行广度优先搜索的类似模板是这样的。使用双端队列而不是数组/Python 列表很重要，因为双端队列的入队速度是 O(1 ),而数组的入队速度是 O(n)。

```
from collections import deque  def  bfs(matrix):  # Check for an empty matrix/graph.  if  not matrix:  return  []  rows, cols =  len(matrix),  len(matrix[0])  visited =  set()  directions =  ((0,  1),  (0,  -1),  (1,  0),  (-1,  0))  def  traverse(i, j):  queue = deque([(i, j)])  while queue:  curr_i, curr_j = queue.popleft()  if  (curr_i, curr_j)  not  in visited:  visited.add((curr_i, curr_j))  # Traverse neighbors.  for direction in directions:  next_i, next_j = curr_i + direction[0], curr_j + direction[1]  if  0  <= next_i < rows and  0  <= next_j < cols:  # Add in question-specific checks, where relevant.  queue.append((next_i, next_j))  for i in  range(rows):  for j in  range(cols):  traverse(i, j) 
```

info

虽然在这个示例中使用递归实现了 DFS，但它也可以像 BFS 一样迭代实现。这两种算法的主要区别在于底层的数据结构(BFS 使用队列，而 DFS 使用堆栈)。Python 中的`deque`类既可以作为堆栈，也可以作为队列。

关于 BFS 和 DFS 的更多提示，你可以参考这个 [LeetCode 帖子](https://leetcode.com/problems/pacific-atlantic-water-flow/discuss/90774/Python-solution-with-detailed-explanation)

### 拓扑排序[](#topological-sorting "Direct link to heading")

有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv，在排序中 u 在 v 之前。准确地说，拓扑排序是一种图遍历，其中每个节点 v 只有在它的所有依赖关系都被访问之后才被访问。

拓扑排序最常用于作业调度，即一系列依赖于其他作业/任务的作业或任务。作业由顶点表示，如果作业 x 必须在作业 y 开始之前完成，则从 x 到 y 有一条边。

另一个例子是在大学里选修有先修课程的课程。

在下面的示例中，边是一个由两个值组成的数组，第一个值依赖于第二个值。

```
def  graph_topo_sort(num_nodes, edges):  from collections import deque nodes, order, queue =  {},  [], deque()  for node_id in  range(num_nodes):  nodes[node_id]  =  {  'in':  0,  'out':  set()  }  for node_id, pre_id in edges:  nodes[node_id]['in']  +=  1  nodes[pre_id]['out'].add(node_id)  for node_id in nodes.keys():  if nodes[node_id]['in']  ==  0:  queue.append(node_id)  while  len(queue):  node_id = queue.pop()  for outgoing_id in nodes[node_id]['out']:  nodes[outgoing_id]['in']  -=  1  if nodes[outgoing_id]['in']  ==  0:  queue.append(outgoing_id)  order.append(node_id)  return order if  len(order)  == num_nodes else  None   print(graph_topo_sort(4,  [[0,  1],  [0,  2],  [2,  1],  [3,  0]]))  # [1, 2, 0, 3] 
```

## 基本问题[](#essential-questions "Direct link to heading")

如果你在学习这个话题，这些是需要练习的基本问题。

*   [岛屿数量](https://leetcode.com/problems/number-of-islands/)
*   [洪水填充](https://leetcode.com/problems/flood-fill)
*   [01 矩阵](https://leetcode.com/problems/01-matrix/)

## 推荐练习题[](#recommended-practice-questions "Direct link to heading")

*这些是在你为题目学习并练习了基本问题后推荐练习的问题。*

*   广度优先搜索
    *   [腐烂的橙子](https://leetcode.com/problems/rotting-oranges/)
    *   [最少骑士招式(LeetCode Premium)](https://leetcode.com/problems/minimum-knight-moves)
*   要么搜索
    *   [克隆图形](https://leetcode.com/problems/clone-graph/)
    *   [太平洋大西洋水流](https://leetcode.com/problems/pacific-atlantic-water-flow/)
    *   [无向图中连通分量的数量(LeetCode Premium)](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/)
    *   [图形有效树(LeetCode Premium)](https://leetcode.com/problems/graph-valid-tree/)
*   拓扑排序
    *   [课程表](https://leetcode.com/problems/course-schedule/)
    *   [外星人字典(LeetCode Premium)](https://leetcode.com/problems/alien-dictionary/)

## 推荐课程[](#recommended-courses "Direct link to heading")

### [AlgoMonster](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)[T3】](#algomonster "Direct link to heading")

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得**终身访问**。 [**今天加入七折优惠→**](https://shareasale.com/r.cfm?b=1873647&u=3114753&m=114505&urllink=&afftrack=)

### [寻找编码面试:编码问题的模式](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)[](#grokking-the-coding-interview-patterns-for-coding-questions "Direct link to heading")

设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。**学习和理解模式，而不是背答案！** [**现在获得终身使用权→**](https://designgurus.org/link/kJSIoU?url=https%3A%2F%2Fdesigngurus.org%2Fcourse%3Fcourseid%3Dgrokking-the-coding-interview)

### [掌握编码面试:数据结构+算法](https://fxo.co/DQpY)[](#master-the-coding-interview-data-structures--algorithms "Direct link to heading")

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 **19 个小时**的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 [**结账→**](https://fxo.co/DQpY)

</header>