← 博客

图

图题单

网格图题单

Notes

  • 能记忆化搜索->一定是有向无环图

邻接表空间复杂度

空间由两部分构成：

  1. 每个节点对应一个邻接列表：$O(V)$
  2. 邻接列表中保存边的端点：无向图的每条边存两次，因此是 $O(2E) = O(E)$

总空间复杂度为 $O(V + E)$。

DFS

找连通块、判断是否有环

对于无向图，如果不需要判断是否有环，则无需用parent，仅用vis即可

261. 以图判树

无向图，判断是否无环并且联通。

用vis[i]=True判断即可。但是由于是无向图，在遍历邻居的时候要跳过父节点，所以需要作为参数被传递

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def dfs(i, parent):
    vis[i]=True
    for nxt in g[i]:
        if nxt==parent:
            continue
        if vis[nxt]:
            return False
        if not dfs(nxt, i):
            return False
    return True

比如1-3-6，1-5-6,如果这样连，那一定是有环的，所以不需要三种颜色

207. 课程表

有向图，判断是否无环

为什么必须用三色？

因为要区分：当前路径上的，还有之前已经遍历结束的某个节点。
比如1->3->6（已经遍历完6了），此时遍历1->5->6，又遇见6，显然这里没有环 如果用True/False， 则这两种情况都算True

为什么单纯通过恢复颜色来做到，会超时？ DAG可能可以用记忆化搜索。比如对于节点x, 仅有的两个next nodes: nxt1 & nxt2都返回好结果，那么x肯定也是返回好结果。根据这样的关系，可以用记忆化搜索。所以可以用第三种状态来表示，已经探索完的节点，如果遇到这种节点，就不dfs进去了

2192. 有向无环图中一个节点的所有祖先

要找到某个节点的所有祖先，但是不需要在dfs的时候把所有本次搜索经过的节点都带上，因为，我们会遍历每个节点，作为起点。所以在搜索的时候，我们只要把这个起点加进祖先列表即可。

dfs条件：当下一个节点在本次搜索之中，没有被搜到过的时候，可以去遍历它.所以每次dfs的时候，vis[i]表示这次搜索的起点，

遍历过该节点，需要恢复它吗？

不需要.
比如0->3->6, 0->4->6。第二次到6的时候其实是不同的一条路，这个时候6被标记为没有被访问过～

当 start = 0：

走路径 0→3→6 时，第一次到达 6，满足 vis[6] != 0，于是 ans[6].append(0)，然后你回溯时如果写了 vis[6] = -1，等于擦掉“6 已被 start=0 访问过”的标记。

回到 0 再走另一条路径 0→4→6，再次检查到 vis[6] != 0（因为被你复原成了 -1），又会 ans[6].append(0) —— 同一个祖先 0 被加了两次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def dfs(i, start):
    # i, start分别是现在到的节点和最开始的祖先
    #找它能到的所有节点
    vis[i]=start
    for child in g[i]:
        if vis[child]!=start:
            dfs(child, start)
    #记录它的祖先（只记录start即可。因为每个node都会做一遍start！）
    if i!=start:
        res[i].append(start)

2101. 引爆最多的炸弹

数从一个节点最多能到多少个节点。有向图，可能有环.

for 循环遍历每个节点，以这个节点为祖先搜索一次。并且每次循环都需要一个新的 vis 数组。

不能记忆化搜索，因为不是DAG,并且会有菱形问题，比如A-B,A-C,B-D,C-D

如果在 dfs 最后恢复vis[i]=False 则会有问题，因为 1-4-6,1-5-6，第一次搜索到 6 就把它标记为 False 了，然后第二次搜索到它的时候会重新计数

721. 账户合并

把人名和邮箱名都视为节点，目的是数连通块的个数

建立一个email_to_account, 记录每个email会属于哪些account。在一次dfs中，会标记所有同属于一个人的账号，并且把他们的email都加进一个set中。

924. 尽量减少恶意软件的传播

无向图中，找最大的、被感染、且只有一个传染源的连通块.返回连通块的大小。
dfs返回三个值：连通块大小、连通块中炸弹数量、连通块中炸弹的index（如果没有则返回inf)

133. 克隆图

主函数表示：为当前node创建一个副本

Solution class拥有一个字段，是一个从原始node到复制node的字典。注意在尝试遍历某个node的邻居之前，要把这个node放进字典

  1. 检查当前节点是否已被访问过，如果是，直接返回self.visited[node]
  2. 为当前节点创建一个node_clone, 并且存入visited
  3. 遍历当前节点的所有邻居，为每个邻居递归调用一次主函数

3481. 应用替换

最坏情况：

%a% → %b%%c%
%b% → %d%%e%
%c% → %f%%g%

假设原始字符串一开始的长度为L，并且一次替换中最多可能有两个占位符，则时间复杂度为L*2^n

T(k)=2T(k−1),T(0)=L

BFS

一般是在加入队列的时候设置邻居的visited为True

127. 单词接龙

1311. 获取你好友已观看的视频

注意要在加入队列的时候，标记该节点为已访问

815. 公交路线

每条 bus route 是一个 node，如果两条 bus 共享至少一个 stop，就连一条边

站i入队，每次找邻居是找stopToBus[i]中每个bus能到的所有站。
还会用vis数组记录是否到达过某个站/搭乘过某个bus
这样每条公交线路最多被遍历一次，因为一个公交一旦到达过了，就不去遍历它的线路了。
最后的时间复杂度位O(S),即所有routes的长度之和。

注意，在遍历完某个站的所有能搭乘的公交之后，清空stopToBus[cur_stop]，防止再次遍历到这个站的时候，遍历很多公交

这题也可以变形做。比如预处理每两个站之间的距离，然后query。

全源最短路径

  • 可以用floyd
  • 对每个source做BFS。
  • 对每个bus做BFS，得到dist[i][j]，即从bus i换乘坐上bus j,需要的最少换乘次数。最后遍历起点站的所有车和终点站的所有车，找最小值

拓扑排序

DFS写法讲解

Kahn拓扑排序

在任意时刻，如果图中入度为 0 的节点有多个，则拓扑排序结果不唯一

刷表法：我已经算好了一个点的答案， 就立刻用它去“更新”所有它能影响到的点。

针对有向无环图。

269. 火星词典

需要注意：建图方式。
DFS写法是三色染色法，每次标记一个节点为【遍历完成】时，加入拓扑队列，最后的答案是拓扑队列的倒序

310. 最小高度树

一棵树的最小高度中心最多只有两个点。

我们通过一轮轮剪掉度为1的点，最后剩下的就是最中心的那个（或两个）点，也就是你要找的答案。需要记录每一层剥下了哪些叶子。

1059. 从起点到终点的所有路径

如果用 dfs 写，不加记忆化搜索，时间复杂度为 number of paths
dfs(cur)代表，是否所有从 cur 出发的路径，其最终状态一定是到 destination

如果用拓扑排序写，需要反向建图。degrees[i]表示对于节点i来说，目前有多少条路径没有被确定为“安全”的。只是因为我们只从destination出发，所以每次找到一个nxt节点，我们都可以确定当前的路径是安全的。

444. 序列重建

把所有的序列视为有向图，首先把入度为0的节点放入队列，队列中一定保证只有唯一的入度为0的节点。（因为此时需要选一个节点加入拓扑排序，必须选这个入度为0的节点）

851. 喧闹和富有

拓扑+DP，记忆化搜索。dfs(x)返回不比自己穷的人当中，最不安静的那个人

dfs 中从 x 去搜索比自己富的人，并返回这些人的对应答案

这种题一定要计算并更新每个人的状态，用于更新邻居的状态。

网格图 DFS

LC 200 岛屿数量

DFS可以用来找聚在一起的符合要求的格子，在访问过某个格子后，改变它的标记。
外层循环遍历每个格子，当见到一个新的符合要求的格子，对它调用 DFS，这一次搜索就能找到一块岛屿，并且保证组成岛屿的部分都不会被再次访问，答案+1.

130. 被围绕的区域

用DFS把与边缘相连通的O都设为#，然后遍历每个格子，把O变成X，再把所有#变成O

694. 不同岛屿的数量

这道题必须要记录完整的：遍历-撤回过程，才能唯一识别一个形状.

在先序遍历的位置加入一个方向，比如1表示是往上达到的这个格子；在后序遍历的时候再加入这个方向的撤回，比如-1。

因为你不知道相邻的两个方向，他们是属于同一次搜索的先后顺序，还是属于两个分支。

827. 最大人工岛

需要给每个岛屿编号，编号从2开始。用编号直接修改grid[i][j]的值

有一个列表islands，里面记录每个岛屿的面积大小.

212. 单词搜索 II

注意这个问题，一个单词中，不能多次用到相同的格子；而一次搜索的多个分支，可以多次用到相同的格子。比如A-B-F, A-C-F，第一次遍历完F，需要把F恢复到visited[F]=False

网格图 BFS

一般是在加入队列的时候设置邻居的visited为True，并且设置队列的初始成员visited为True。

994 腐烂的橘子

BFS用来一层一层地往外蔓延，可以记录蔓延的时间。

286. 墙与门

不是从房间去寻找门，而是让门去寻找房间！

多源BFS：把所有门作为起点，一起向四周扩散。每个空房间第一次被更新时就是它距离最近门的最短距离，这样只访问每个格子一次，效率更高。

具体操作时，把格子的值修改为从门到它的最短距离。

417. 太平洋大西洋水流问题

也可以用多源BFS做，BFS函数每次返回一个visited数组。最后的结果即为两个BFS数组的交集

初始入队可以这样写：

1

pac_starts = [(i, 0) for i in range(m)] + [(0, j) for j in range(n)]

1293. 网格中的最短路径

最多可以消除K个障碍物：最多可以经过K个障碍物
搜索状态(x,y,rest)表示在此处还可以经过rest个障碍物.
vis集合里面也需要记录此时剩余可以跨越的障碍物数量

网格图 0-1 BFS

专门解决「边权只可能是 0 或 1」的最短路问题，它把 Dijkstra 的“按距离最小弹出 + 优先队列”思路，换成了“双端队列 deque + 常数时间插入”——一旦边权只有 0/1，就能把 O(E log V) 降到 O(E + V)。

为什么可以这样做？因为BFS队列只包含“这一层”和“下一层”的节点。而0-1网格图中，边权只有0或1，也就对应“这一层”和“下一层”，所以用双端队列就可以实现用堆的Dijkstra。

时间复杂度为O(V+E)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from collections import deque

INF = 10**18

def zero_one_bfs(n, adj, s):
    """
    n: 顶点个数 [0..n-1]
    adj[u]: 列表 [(v, w)]，其中 w ∈ {0, 1}
    s: 源点
    return: dist 数组
    """
    dist = [INF] * n
    dist[s] = 0
    dq = deque([s])

    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                if w == 0:
                    dq.appendleft(v)  # 同层：放队首
                else:
                    dq.append(v)      # 下一层：放队尾
    return dist

1368. 使网格图至少有一条有效路径的最小代价

欧拉回路

欧拉通路（Eulerian Path）：是一条通过图中所有边恰好一次的路径，不要求遍历所有顶点（因为某些顶点可能没有边，或者不是路径的一部分）。

欧拉回路（Eulerian Circuit）：是一条通过图中所有边恰好一次且起点终点相同的回路，也不要求必须经过所有顶点。

欧拉图：包含欧拉回路的图；

半欧拉图：包含欧拉通路但不包含欧拉回路的图。

  1. 对于无向图 G，G 是欧拉图当且仅当 G 是连通的且没有奇度顶点。
    对于无向图 G，G 是半欧拉图当且仅当 G 是连通的且 G 中恰有 0 个或 2 个奇度顶点。
  2. 对于有向图 G，G 是欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。
  3. 对于有向图 G，G 是半欧拉图当且仅当
  • 如果将 G 中的所有有向边退化为无向边时，那么 G 的所有顶点属于同一个强连通分量；
  • 最多只有一个顶点的出度与入度差为 1；
  • 最多只有一个顶点的入度与出度差为 1；
  • 所有其他顶点的入度和出度相同

332. 重新安排行程

此图是一个半欧拉图，且固定起点为JFK。因此，图中唯一出度比入度小1的节点是终点

从某个机场出发，一直做DFS，但是需要用heap,弹出到字母序最小的机场的那条边。只要当前机场 node 还有没用过的出发机票，就继续往下 DFS。 直到某个机场，没有任何机票了，就把它加入答案。

Hierholzer 算法的核心思路是：

  1. 从起点出发，深度优先遍历图中还没被访问的边。
  2. 一旦当前点没有未访问的边了，就将它加入最终路径中（回溯）。
  3. 回溯过程会将路径倒着加入，最后再把路径逆序得到答案。

dijkstra

✅ 图搜索问题
✅ 最优路径问题（要找最优等待时间)
✅ 非负权重（高度值非负）

当一个节点出堆的时候，就代表它的最短路一定已经找到了（虽然此时弹出的距离不一定是最短距离）

一个节点第一次出堆的时候，这个时候弹出的dx一定是最小值，且dx==dist[x]

在正权图的 Dijkstra + 懒删除实现里， 每当一个节点从堆顶弹出时，它的最短路长度 dist[x] 已经确定； 如果 dx == dist[x]，确定发生在当前弹出； 如果 dx > dist[x]，确定发生在之前那次满足相等条件的弹出。

778. 水位上升的泳池中游泳

目标：最小化路径中的最大值。
把两个点之间的边权看做这两个点之间最大的高度

时间复杂度：n^2*logN, 空间复杂度：n^2

743. 网络延迟时间

time complexity: O((V+E*logV))

用堆的写法。堆里面存放目前已经探索到的节点，以从start到他们的距离排序。
一开始把起点放进堆. 注意懒删除机制：之前放进去的某个节点和它的距离，可能已经被更小值更新过了！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

g=[[inf]*n for _ in range(n)]
for a,b,d in times:
    g[a-1][b-1]=d
pq=[[0,k-1]]
dis=[inf]*n
dis[k-1]=0
while pq:
    cur_dis, cur=heapq.heappop(pq)
    #但是dis[cur]可能已经被更新了！
    if cur_dis>dis[cur]:
        continue
    #获得邻接的节点
    for nxt in range(n):
        if g[cur][nxt]<inf:
            if cur_dis+g[cur][nxt]<dis[nxt]:
                dis[nxt]=cur_dis+g[cur][nxt]
                heapq.heappush(pq, [dis[nxt], nxt])
return max(dis) if max(dis)<inf else -1

1976. 到达目的地的方案数

一边Dijkstra，一边DP，用一个f数组来记录每个距离的方案数

union find

哈希表写法: 3873

1
2
3
4
5
6
7
8

parent={}
def find(x):
    if x not in parent:
        return x
    if parent[x]==x:
        return x
    parent[x]=find(parent[x])
    return parent[x]

Kruskal

先按权重从小到大给edge排序，接着连接每个edge两端的顶点。每次连接，图中的连通块数量-=1。

等到连通块数量==1时，说明最小生成树已经生成。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

n = len(edges)
parent = list(range(n + 1))

def find(index: int) -> int:
    if parent[index] != index:
        parent[index] = find(parent[index])
    return parent[index]

def union(index1: int, index2: int):
    parent[find(index1)] = find(index2)

Bellman-Ford

在最多经过 V-1 条边的情况下，从源点 src 到所有点的最短路径。（允许负权值）

模拟每一轮怎么走。也就是循环经过的边数，每一次循环内部遍历所有的边。

时间复杂度O(VE),比dijkstra的O(ElogV)要差

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def bellman_ford(n: int, edges: List[List[int]], src: int) -> List[float]:
    dist = [inf] * n
    dist[src] = 0

    # 最多 n-1 条边 => 做 n-1 轮松弛
    for _ in range(n - 1):
        updated = False
        prev = dist[:]          # 同样用上一轮的结果
        for u, v, w in edges:
            if prev[u] == inf:
                continue
            if dist[v] > prev[u] + w:
                dist[v] = prev[u] + w
                updated = True
        if not updated:         # 可选的小优化：无更新就提前结束
            break

    return dist

787. K 站中转内最便宜的航班

dp[t][v] = 从 src 出发，经过最多 t 条边，到达 v 的最小费用

Floyd-Warshall

求全源最短路，更适合稠密图，时间复杂度恒为O(V^3)
通过每个中间节点 k，尝试更新所有点对 (i, j) 之间的最短距离

1334. 阈值距离内邻居最少的城市

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

from typing import List

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # 步骤1：初始化距离矩阵
        dis = [[float('inf')] * n for _ in range(n)]
        
        # 自己到自己距离为0
        for i in range(n):
            dis[i][i] = 0
        
        # 填入直连边的距离
        for a, b, w in edges:
            dis[a][b] = w
            dis[b][a] = w  # 无向图
        
        # 步骤2：Floyd 三层循环
        # 最外层：枚举中间节点 k
        for k in range(n):
            # 中间层：枚举起点 i
            for i in range(n):
                # 最内层：枚举终点 j
                for j in range(n):
                    # 尝试通过 k 中转，看是否更近
                    if dis[i][k] + dis[k][j] < dis[i][j]:
                        dis[i][j] = dis[i][k] + dis[k][j]
        
        # 步骤3：找答案
        min_count = n  # 最少可达城市数
        ans = -1       # 答案城市编号
        
        for i in range(n):
            # 统计从城市 i 出发，能在阈值内到达的城市数
            count = 0
            for j in range(n):
                if i != j and dis[i][j] <= distanceThreshold:
                    count += 1
            
            # 题目要求：数量相同时选编号大的
            if count <= min_count:
                min_count = count
                ans = i
        
        return ans

BFS 时间复杂度

时间复杂度 = 节点数 × 每个节点的处理成本