graph

文档摘要

id: graph title: 编码面试中的图 cheat sheet description: 编码面试中的图学习指南，包括练习题、技巧、时间复杂度和推荐资源 keywords: [ 图编码面试学习指南, 编码面试中的图技巧, 图练习题, 图实用技巧, 图时间复杂度, 图推荐学习资源, ] sidebarlabel: 图 tocmaxheadinglevel: 2 引言图是一种结构，包含一组对象（节点或顶点），这些节点/顶点之间可以存在边。边可以是有向的或无向的，也可以选择性地带有权值（加权图）。树是一种无向图，其中任意两个顶点之间恰好有一条边相连，并且图中不能存在环。图常用于建模无序实体之间的关系，例如：人与人之间的友谊——每个节点代表一个人，节点间的边表示两人是朋友。


id: graph  
title: 编码面试中的图 cheat sheet  
description: 编码面试中的图学习指南，包括练习题、技巧、时间复杂度和推荐资源  
keywords:  
  [
    图编码面试学习指南,
    编码面试中的图技巧,
    图练习题,
    图实用技巧,
    图时间复杂度,
    图推荐学习资源,
  ]  
sidebar_label: 图  
toc_max_heading_level: 2

引言

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

图常用于建模无序实体之间的关系，例如：

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

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

学习资源

阅读材料
- 从理论到实践：图的表示, basecs
- 深入探索图：DFS遍历, basecs
- 广度探索图：BFS遍历, basecs
补充内容（仅限有空时）
- 寻找最短路径，借助迪杰斯特拉算法, basecs
- 用有向无环图绕圈, basecs

图的表示方法

你可能会得到一个边的列表，需要根据这些边构建自己的图，以便对其进行遍历。常见的图表示方法有：

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

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

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

时间复杂度

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

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

面试中需要注意的事项

树状图很可能是一个允许存在环的图，朴素的递归解法将无法奏效。在这种情况下，你需要处理环，并在遍历时记录已访问过的节点集合。
确保正确记录已访问的节点，避免重复访问同一个节点。否则你的代码可能会陷入无限循环。

边界情况

空图
只有一个或两个节点的图
不连通的图
有环的图

图的搜索算法

常见——广度优先搜索、深度优先搜索
不常见——拓扑排序、迪杰斯特拉算法
几乎不会用到——贝尔曼-福特算法、弗洛伊德-沃什尔算法、普里姆算法、克鲁斯卡尔算法。你的面试官可能也不熟悉这些算法。

深度优先搜索

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

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


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]

必备题目

如果你正在备考这一主题，这些题目是必练的。