算法总结 | 技术面试手册 | tech-interview-handbook 中文文档

根据您提供的Markdown文档内容，以下是翻译后的简体中文版本：

id: graph 标题：编码面试图形技巧指南描述：编码面试图形学习指南，包括实践问题、技巧、时间复杂度和推荐资源关键词： [ 图形编码面试学习指南，图形编码面试技巧，图形实践问题，图形有用技巧，图形时间复杂度，图形推荐学习资源 ] 侧边栏标签：图形目录最大标题级别：2

引言

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

图形通常用于模拟无序实体之间的关系，例如

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

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

学习资源

图形表示

你可能会得到一个边列表，你必须根据这些边构建自己的图形，以便对它们进行遍历。常见的图形表示有：

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

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

在算法面试中，图形通常作为输入给出为二维矩阵，其中单元格是节点，每个单元格可以遍历到其相邻单元格（上/下/左/右）。因此，熟悉遍历二维矩阵非常重要。在遍历矩阵时，请确保当前位置在矩阵边界内，并且之前未被访问过。

时间复杂度

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

算法	大O表示
深度优先搜索	O(
广度优先搜索	O(
拓扑排序	O(

面试时需要注意的事项

树状图可能是一个允许循环的图形，天真的递归解决方案将不起作用。在这种情况下，你必须处理循环并在遍历时保持已访问节点集。
确保正确跟踪已访问节点，避免重复访问每个节点。否则，你的代码可能会导致无限循环。

边缘情况

空图
只有一个或两个节点的图
断开的图
带有循环的图

图搜索算法

常见 - 广度优先搜索，深度优先搜索
不常见 - 拓扑排序，Dijkstra算法
几乎从不 - Bellman-Ford算法，Floyd-Warshall算法，Prim算法，Kruskal算法。你的面试官可能也不知道这些算法。

深度优先搜索

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

在矩阵上执行深度优先搜索的简单模板如下：

def dfs(matrix):
  # 检查是否为空图/图形。
  if not matrix:
    return []

  行数, 列数 = len(matrix), len(matrix[0])
  已访问 = set()
  方向 = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def 遍历(i, j):
    如果 (i, j) 已经在已访问集合中，则返回。

    已访问添加到 (i, j)
    # 遍历邻居。
    for 方向 in 方向:
      下一个i, 下一个j = i + 方向[0], j + 方向[1]
      如果 0 <= 下一个i < 行数并且 0 <= 下一个j < 列数：
        # 添加问题特定的检查，如有必要。
        遍历(下一个i, 下一个j)

  对于 i 在范围 [0, 行数) 内，对于 j 在范围 [0, 列数) 内：
    遍历(i, j)

广度优先搜索

广度优先搜索是一种图遍历算法，它从节点开始，探索当前深度的所有节点，然后再移动到下一个深度层次的节点。通常使用队列来跟踪遇到的但尚未探索的节点。

在矩阵上执行广度优先搜索的类似模板如下。使用双端队列而不是数组/Python列表很重要，因为双端队列的入队出队操作是O(1)的，而数组/Python列表是O(n)的。

from collections import deque

def bfs(matrix):
  # 检查是否为空图/图形。
如果要将Markdown技术文档翻译成简体中文，请提供您想要翻译的文档内容。请确保翻译结果不包含任何额外的翻译信息，也不要添加任何内容。翻译时请注意保持原文的格式不变，包括缩进、空格、行首缩进符号、换行和链接。翻译结果应流畅、口语化，并符合中国简体中文的表达方式。

以下是根据您提供的Markdown示例进行的翻译：

```markdown
如果矩阵不是空的，就返回一个空列表。

矩阵的行数和列数分别为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]

基本问题

如果您正在为该主题学习，这是练习的基本问题。

引言