面试Leetcode - Graph

图Graph图是 点Vertex / Node和 边Edge组成的结构树其实是图的特例树 连通且无环的无向图。存储邻接表 *graph { 0: [1, 2], 1: [0, 3], 2: [0], 3: [1] }含义0 与 1、2 相连。leetcode 一般标准解法都用邻接表邻接矩阵0 1 2 30 0 1 1 01 1 0 0 12 1 0 0 03 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 dequequeue deque()# 起点加入队列queue.append(start)while queue:node queue.popleft()# 处理 nodefor neighbor in neighbors(node):queue.append(neighbor)做题看到什么词想到什么岛屿、区域、省份、连通块连通性课程、前置、依赖、任务顺序依赖关系最少步数、最短路径BFS 最短路带权代价最小Dijkstra连通性两个点能不能互相到达Flood Fill / Connected ComponentsLC200 Number of IslandsLC695 Max Area of IslandLC733 Flood Fill最短路BFS lc 994 坏橘子问题依赖关系有没有一种合法的执行顺序检查图中有没有环 DFS/BFS 都可以)step 1 建立邻接表