面试Leetcode - Graph
图（Graph）
图是 点（Vertex / Node）和 边（Edge）组成的结构
树其实是图的特例
树 = 连通且无环的无向图。
存储
邻接表 *
graph = { 0: [1, 2], 1: [0, 3], 2: [0], 3: [1] }
含义：0 与 1、2 相连。
leetcode 一般标准解法都用邻接表
邻接矩阵
0 1 2 3
0 0 1 1 0
1 1 0 0 1
2 1 0 0 0
3 0 1 0 0
适合稠密图
空间 O(n²)
搜索
DFS（深度优先）
一路走到底，再回溯。递归帮你维护“下一步”。
visited = set()
def dfs(u):
visited.add(u)
for v in graph[u]:
if v not in visited:
dfs(v)
BFS（广度优先）
一层一层扩展。队列帮你维护“下一步”。
from collections import deque
queue = deque()
# 起点加入队列
queue.append(start)
while queue:node = queue.popleft()
# 处理 node
for neighbor in neighbors(node):
queue.append(neighbor)
做题
看到什么词 | 想到什么 |
|---|---|
岛屿、区域、省份、连通块 | 连通性 |
课程、前置、依赖、任务顺序 | 依赖关系 |
最少步数、最短路径 | BFS 最短路 |
带权代价最小 | Dijkstra |
连通性
两个点能不能互相到达？
Flood Fill / Connected Components
LC200 Number of Islands
LC695 Max Area of Island
LC733 Flood Fill
最短路
BFS lc 994 坏橘子问题
依赖关系
有没有一种合法的执行顺序？
检查图中有没有环 （DFS/BFS 都可以)
step 1 建立邻接表