图题单

网格图题单

图

DFS

找连通块、判断是否有环

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，又遇见5，显然这里没有环 如果用True/False， 则这两种情况都算True

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 数组。

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

721. 账户合并

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

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

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

BFS

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

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

拓扑排序

DFS写法讲解

针对有向无环图。

网格图

DFS

LC 200 岛屿数量

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

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)]