Algorithms study cheatsheets

Coding interview 的 Graph cheatsheet

Graph 学习指南，包含练习题、技巧、时间复杂度与推荐资源

Introduction

Graph 是由一组对象（nodes/vertices）和它们之间的边（edges）组成的结构。边可以是 directed 或 undirected，也可以带权重（weighted graph）。Tree 是一种 undirected graph，其中任意两点之间只有唯一一条边，且不存在 cycle。

Graph 常用于描述无序实体之间的关系，比如：

人与人的朋友关系 - 节点是人，边表示两个人是朋友。
地点之间的距离 - 节点是地点，边表示地点相连，边的值表示距离。

需要熟悉图的表示方式、图搜索算法以及它们的 time/space complexity。

Learning resources

Readings
- From Theory To Practice: Representing Graphs, basecs
- Deep Dive Through A Graph: DFS Traversal, basecs
- Going Broad In A Graph: BFS Traversal, basecs
Additional (only if you have time)
- Finding The Shortest Path, With A Little Help From Dijkstra, basecs
- Spinning Around In Cycles With Directed Acyclic Graphs, basecs

Graph representations

面试时可能给你一组 edges，然后让你自己构图来做遍历。常见表示方式：

Adjacency matrix
Adjacency list
Hash table of hash tables

在算法面试中，用 hash table of hash tables 通常最直接。面试很少要求你必须用 adjacency matrix 或 adjacency list。

面试中 graph 也常以二维矩阵形式出现：cell 是 node，且可向上下左右相邻 cell 走。因此需要熟悉 2D matrix 遍历。遍历时要确保当前位置在边界内，且尚未访问过。

Time complexity

|V| 是 vertices 数量，|E| 是 edges 数量。

Algorithm	Big-O
Depth-first search	O(\|V\| + \|E\|)
Breadth-first search	O(\|V\| + \|E\|)
Topological sort	O(\|V\| + \|E\|)

Things to look out for during interviews

看起来像 tree 的图，可能其实允许 cycle，简单递归会炸。此时必须处理 cycle，并维护 visited 集合。
确保正确维护 visited，避免重复访问节点，否则可能进入无限循环。

Corner cases

Empty graph
Graph with one or two nodes
Disconnected graphs
Graph with cycles

Graph search algorithms

Common - Breadth-first Search, Depth-first Search
Uncommon - Topological Sort, Dijkstra's algorithm
Almost never - Bellman-Ford algorithm, Floyd-Warshall algorithm, Prim's algorithm, Kruskal's algorithm。面试官可能也不熟。

Depth-first search

DFS 会沿着某条路径尽可能深地探索，走到底再回溯。通常会用 stack 记录当前路径上的节点，可以是隐式 recursion stack，也可以是显式 stack 数据结构。

一个在 matrix 上做 DFS 的模板：

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

BFS 从起点开始，先探索当前深度的所有节点，再进入下一层。通常用 queue 记录已发现但未探索的节点。

下面是 BFS 的 matrix 模板。注意要用 deque 而不是数组/Python list，因为 deque 的出队是 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 用 recursion 实现，但也可以像 BFS 一样用迭代方式。二者核心差异在于底层数据结构（BFS 用 queue，DFS 用 stack）。Python 的 deque 既可当 stack，也可当 queue。

更多 BFS/DFS 提示可以参考这个 LeetCode post

Topological sorting

Topological sort 是对 directed graph 做线性排序，使得对每条边 u -> v，u 都排在 v 前面。更严格地说，topological sort 是一种遍历：只有当节点 v 的所有依赖都被访问后，v 才会被访问。

Topological sort 常用于带依赖关系的任务调度：任务是顶点，若 x 必须先完成才能开始 y，则有边 x -> y。

另一个例子是大学选课：课程之间有 prerequisites。

下面例子里 edges 是二维数组，且第一项依赖第二项。

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

这些是该 topic 必练题。