Skip to content

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

原文：https://www.techinterviewhandbook.org/algorithms/graph/

简介

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

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

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

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

学习资源

图形表示

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

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

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

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

时间复杂度

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

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

面试时要注意的事情

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

拐角情况

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

图形搜索算法

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

深度优先搜索

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

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

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)

广度优先搜索

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

在矩阵上进行广度优先搜索的类似模板是这样的。使用双端队列而不是数组/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 帖子

拓扑排序

有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于从顶点 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]

基本问题

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

推荐练习题

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

推荐课程

AlgoMonsterT3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得终身访问。 今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式，而不是背答案！ 现在获得终身使用权→

掌握编码面试:数据结构+算法

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

我们一直在努力

apachecn/AiLearning

【布客】中文翻译组