1. Hot100图论专题解析算法面试的核心战场最近在刷Hot100的图论题目发现这确实是算法面试中的重灾区。作为计算机科学的基础领域之一图论问题在各大公司的技术面试中出现的频率极高。我花了整整两周时间集中攻克这个专题期间踩过不少坑也总结出一些实用的解题套路。图论问题之所以让很多人头疼主要在于它的变化多端。从简单的图的遍历到复杂的网络流问题考察点可以非常灵活。但万变不离其宗掌握几个核心算法思想和解题模板就能应对大部分面试场景。下面我就结合Hot100中的典型题目分享我的解题心得。2. 图论基础与核心算法2.1 图的表示方法在开始解题前首先要明确图的两种主要表示方式邻接矩阵用一个二维数组表示图中顶点之间的连接关系邻接表为每个顶点维护一个链表存储与之相连的顶点对于稀疏图边数远小于顶点数的平方邻接表更为高效。这也是大多数算法题的首选表示方法。在Python中我们常用字典来表示邻接表graph { A: [B, C], B: [A, D, E], C: [A, F], D: [B], E: [B, F], F: [C, E] }2.2 深度优先搜索(DFS)与广度优先搜索(BFS)这两种遍历方法是解决图论问题的基础。它们的核心区别在于访问节点的顺序DFS沿着一条路径深入探索到底再回溯BFS按层次逐步扩展先访问离起点近的节点DFS的实现通常使用递归或显式栈def dfs(graph, node, visited): if node not in visited: print(node) visited.add(node) for neighbor in graph[node]: dfs(graph, neighbor, visited)BFS则使用队列实现from collections import deque def bfs(graph, start): visited set() queue deque([start]) visited.add(start) while queue: node queue.popleft() print(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)2.3 拓扑排序拓扑排序针对的是有向无环图(DAG)它将图中的顶点排成一个线性序列使得对于图中的每条有向边(u,v)u在序列中总是位于v的前面。Kahn算法是一种常用的拓扑排序算法def topological_sort(graph): in_degree {u:0 for u in graph} for u in graph: for v in graph[u]: in_degree[v] 1 queue deque([u for u in graph if in_degree[u] 0]) topo_order [] while queue: u queue.popleft() topo_order.append(u) for v in graph[u]: in_degree[v] - 1 if in_degree[v] 0: queue.append(v) if len(topo_order) len(graph): return topo_order else: return [] # 存在环3. Hot100经典图论题目解析3.1 课程表问题LeetCode 207这是拓扑排序的典型应用。题目要求判断给定的课程安排是否合理即是否存在循环依赖。解题思路将课程看作图中的节点先修关系看作有向边尝试对图进行拓扑排序如果排序后的节点数等于总课程数说明无环否则存在循环依赖def canFinish(numCourses, prerequisites): graph {i:[] for i in range(numCourses)} in_degree [0]*numCourses for dest, src in prerequisites: graph[src].append(dest) in_degree[dest] 1 queue deque([i for i in range(numCourses) if in_degree[i] 0]) count 0 while queue: node queue.popleft() count 1 for neighbor in graph[node]: in_degree[neighbor] - 1 if in_degree[neighbor] 0: queue.append(neighbor) return count numCourses3.2 岛屿数量LeetCode 200这是典型的连通分量问题可以用DFS或BFS解决。题目要求在给定的二维网格中统计岛屿的数量1表示陆地0表示水。DFS解法def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) def dfs(r, c): if r 0 or c 0 or r rows or c cols or grid[r][c] ! 1: return grid[r][c] 0 # 标记为已访问 dfs(r1, c) dfs(r-1, c) dfs(r, c1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 dfs(r, c) return count3.3 克隆图LeetCode 133这道题要求深度复制一个无向连通图。关键在于如何处理节点的引用关系避免重复创建节点。BFS解法class Node: def __init__(self, val 0, neighbors None): self.val val self.neighbors neighbors if neighbors is not None else [] def cloneGraph(node): if not node: return None visited {} queue deque([node]) visited[node] Node(node.val, []) while queue: n queue.popleft() for neighbor in n.neighbors: if neighbor not in visited: visited[neighbor] Node(neighbor.val, []) queue.append(neighbor) visited[n].neighbors.append(visited[neighbor]) return visited[node]4. 图论中的高级算法与应用4.1 最短路径算法Dijkstra算法是解决单源最短路径问题的经典算法适用于边权非负的图。import heapq def dijkstra(graph, start): distances {vertex: float(infinity) for vertex in graph} distances[start] 0 heap [(0, start)] while heap: current_dist, current_vertex heapq.heappop(heap) if current_dist distances[current_vertex]: continue for neighbor, weight in graph[current_vertex].items(): distance current_dist weight if distance distances[neighbor]: distances[neighbor] distance heapq.heappush(heap, (distance, neighbor)) return distances4.2 最小生成树Kruskal算法用于寻找连通加权无向图的最小生成树。class UnionFind: def __init__(self, size): self.parent list(range(size)) self.rank [0]*size def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root self.find(x) y_root self.find(y) if x_root y_root: return False if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1 return True def kruskal(vertices, edges): edges.sort(keylambda x: x[2]) uf UnionFind(len(vertices)) mst [] for u, v, weight in edges: if uf.union(u, v): mst.append((u, v, weight)) if len(mst) len(vertices) - 1: break return mst4.3 网络流问题Ford-Fulkerson算法是解决最大流问题的经典方法。这里给出基于BFS的Edmonds-Karp实现from collections import deque def bfs(graph, s, t, parent): visited [False] * len(graph) queue deque() queue.append(s) visited[s] True while queue: u queue.popleft() for v, capacity in enumerate(graph[u]): if not visited[v] and capacity 0: queue.append(v) visited[v] True parent[v] u if v t: return True return False def ford_fulkerson(graph, source, sink): parent [-1] * len(graph) max_flow 0 while bfs(graph, source, sink, parent): path_flow float(Inf) v sink while v ! source: u parent[v] path_flow min(path_flow, graph[u][v]) v u v sink while v ! source: u parent[v] graph[u][v] - path_flow graph[v][u] path_flow v u max_flow path_flow return max_flow5. 图论解题技巧与常见错误5.1 解题思路框架面对图论问题时可以按照以下步骤思考明确问题类型是路径问题、连通性问题、匹配问题还是流问题选择合适的图表示方法邻接表还是邻接矩阵确定适用的算法DFS/BFS、Dijkstra、拓扑排序等考虑边界条件空图、单节点图、完全图等特殊情况优化空间和时间复杂度5.2 常见错误与调试技巧无限循环在图遍历时忘记标记已访问节点解决方法确保在访问节点后立即标记错误的最短路径在有权图中错误使用BFS解决方法对于有权图使用Dijkstra等专门算法内存溢出处理大规模图时使用不合适的表示方法解决方法对于稀疏图使用邻接表而非邻接矩阵忽略方向性混淆有向图和无向图解决方法仔细审题明确图的类型5.3 性能优化策略及早终止在找到解后立即返回避免不必要的计算剪枝在搜索过程中排除不可能的分支双向BFS当起点和终点都已知时可以显著提高搜索效率预处理对图进行预处理如计算度中心性以加速后续查询6. 图论在面试中的实际应用6.1 系统设计中的应用社交网络好友关系图、推荐系统网络路由互联网路由算法任务调度依赖关系处理地图服务路径规划、导航6.2 常见面试问题模式矩阵中的图问题将矩阵视为图的邻接矩阵树形问题树是特殊的图很多图算法适用于树状态转换问题将状态视为节点转换视为边分层图问题如带约束的最短路径6.3 面试准备建议掌握基础算法DFS、BFS、拓扑排序、最短路径等理解算法适用场景知道什么情况下用什么算法练习白板编码熟练在不借助IDE的情况下写出正确代码准备复杂度分析能够分析算法的时间和空间复杂度多做模拟面试适应面试环境和压力图论问题在面试中虽然挑战性较大但通过系统性的学习和足够的练习完全可以掌握。我个人的经验是先理解各类算法的核心思想然后通过大量题目练习来培养直觉。当看到一个图论问题时能够快速识别其类型并选择合适的解决方法。 
长河君 · 2026/8/26 3:09:06 · 阅读 1.2k Hot100图论专题解析：算法面试核心技巧
1. Hot100图论专题解析算法面试的核心战场最近在刷Hot100的图论题目发现这确实是算法面试中的重灾区。作为计算机科学的基础领域之一图论问题在各大公司的技术面试中出现的频率极高。我花了整整两周时间集中攻克这个专题期间踩过不少坑也总结出一些实用的解题套路。图论问题之所以让很多人头疼主要在于它的变化多端。从简单的图的遍历到复杂的网络流问题考察点可以非常灵活。但万变不离其宗掌握几个核心算法思想和解题模板就能应对大部分面试场景。下面我就结合Hot100中的典型题目分享我的解题心得。2. 图论基础与核心算法2.1 图的表示方法在开始解题前首先要明确图的两种主要表示方式邻接矩阵用一个二维数组表示图中顶点之间的连接关系邻接表为每个顶点维护一个链表存储与之相连的顶点对于稀疏图边数远小于顶点数的平方邻接表更为高效。这也是大多数算法题的首选表示方法。在Python中我们常用字典来表示邻接表graph { A: [B, C], B: [A, D, E], C: [A, F], D: [B], E: [B, F], F: [C, E] }2.2 深度优先搜索(DFS)与广度优先搜索(BFS)这两种遍历方法是解决图论问题的基础。它们的核心区别在于访问节点的顺序DFS沿着一条路径深入探索到底再回溯BFS按层次逐步扩展先访问离起点近的节点DFS的实现通常使用递归或显式栈def dfs(graph, node, visited): if node not in visited: print(node) visited.add(node) for neighbor in graph[node]: dfs(graph, neighbor, visited)BFS则使用队列实现from collections import deque def bfs(graph, start): visited set() queue deque([start]) visited.add(start) while queue: node queue.popleft() print(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)2.3 拓扑排序拓扑排序针对的是有向无环图(DAG)它将图中的顶点排成一个线性序列使得对于图中的每条有向边(u,v)u在序列中总是位于v的前面。Kahn算法是一种常用的拓扑排序算法def topological_sort(graph): in_degree {u:0 for u in graph} for u in graph: for v in graph[u]: in_degree[v] 1 queue deque([u for u in graph if in_degree[u] 0]) topo_order [] while queue: u queue.popleft() topo_order.append(u) for v in graph[u]: in_degree[v] - 1 if in_degree[v] 0: queue.append(v) if len(topo_order) len(graph): return topo_order else: return [] # 存在环3. Hot100经典图论题目解析3.1 课程表问题LeetCode 207这是拓扑排序的典型应用。题目要求判断给定的课程安排是否合理即是否存在循环依赖。解题思路将课程看作图中的节点先修关系看作有向边尝试对图进行拓扑排序如果排序后的节点数等于总课程数说明无环否则存在循环依赖def canFinish(numCourses, prerequisites): graph {i:[] for i in range(numCourses)} in_degree [0]*numCourses for dest, src in prerequisites: graph[src].append(dest) in_degree[dest] 1 queue deque([i for i in range(numCourses) if in_degree[i] 0]) count 0 while queue: node queue.popleft() count 1 for neighbor in graph[node]: in_degree[neighbor] - 1 if in_degree[neighbor] 0: queue.append(neighbor) return count numCourses3.2 岛屿数量LeetCode 200这是典型的连通分量问题可以用DFS或BFS解决。题目要求在给定的二维网格中统计岛屿的数量1表示陆地0表示水。DFS解法def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) def dfs(r, c): if r 0 or c 0 or r rows or c cols or grid[r][c] ! 1: return grid[r][c] 0 # 标记为已访问 dfs(r1, c) dfs(r-1, c) dfs(r, c1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 dfs(r, c) return count3.3 克隆图LeetCode 133这道题要求深度复制一个无向连通图。关键在于如何处理节点的引用关系避免重复创建节点。BFS解法class Node: def __init__(self, val 0, neighbors None): self.val val self.neighbors neighbors if neighbors is not None else [] def cloneGraph(node): if not node: return None visited {} queue deque([node]) visited[node] Node(node.val, []) while queue: n queue.popleft() for neighbor in n.neighbors: if neighbor not in visited: visited[neighbor] Node(neighbor.val, []) queue.append(neighbor) visited[n].neighbors.append(visited[neighbor]) return visited[node]4. 图论中的高级算法与应用4.1 最短路径算法Dijkstra算法是解决单源最短路径问题的经典算法适用于边权非负的图。import heapq def dijkstra(graph, start): distances {vertex: float(infinity) for vertex in graph} distances[start] 0 heap [(0, start)] while heap: current_dist, current_vertex heapq.heappop(heap) if current_dist distances[current_vertex]: continue for neighbor, weight in graph[current_vertex].items(): distance current_dist weight if distance distances[neighbor]: distances[neighbor] distance heapq.heappush(heap, (distance, neighbor)) return distances4.2 最小生成树Kruskal算法用于寻找连通加权无向图的最小生成树。class UnionFind: def __init__(self, size): self.parent list(range(size)) self.rank [0]*size def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root self.find(x) y_root self.find(y) if x_root y_root: return False if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1 return True def kruskal(vertices, edges): edges.sort(keylambda x: x[2]) uf UnionFind(len(vertices)) mst [] for u, v, weight in edges: if uf.union(u, v): mst.append((u, v, weight)) if len(mst) len(vertices) - 1: break return mst4.3 网络流问题Ford-Fulkerson算法是解决最大流问题的经典方法。这里给出基于BFS的Edmonds-Karp实现from collections import deque def bfs(graph, s, t, parent): visited [False] * len(graph) queue deque() queue.append(s) visited[s] True while queue: u queue.popleft() for v, capacity in enumerate(graph[u]): if not visited[v] and capacity 0: queue.append(v) visited[v] True parent[v] u if v t: return True return False def ford_fulkerson(graph, source, sink): parent [-1] * len(graph) max_flow 0 while bfs(graph, source, sink, parent): path_flow float(Inf) v sink while v ! source: u parent[v] path_flow min(path_flow, graph[u][v]) v u v sink while v ! source: u parent[v] graph[u][v] - path_flow graph[v][u] path_flow v u max_flow path_flow return max_flow5. 图论解题技巧与常见错误5.1 解题思路框架面对图论问题时可以按照以下步骤思考明确问题类型是路径问题、连通性问题、匹配问题还是流问题选择合适的图表示方法邻接表还是邻接矩阵确定适用的算法DFS/BFS、Dijkstra、拓扑排序等考虑边界条件空图、单节点图、完全图等特殊情况优化空间和时间复杂度5.2 常见错误与调试技巧无限循环在图遍历时忘记标记已访问节点解决方法确保在访问节点后立即标记错误的最短路径在有权图中错误使用BFS解决方法对于有权图使用Dijkstra等专门算法内存溢出处理大规模图时使用不合适的表示方法解决方法对于稀疏图使用邻接表而非邻接矩阵忽略方向性混淆有向图和无向图解决方法仔细审题明确图的类型5.3 性能优化策略及早终止在找到解后立即返回避免不必要的计算剪枝在搜索过程中排除不可能的分支双向BFS当起点和终点都已知时可以显著提高搜索效率预处理对图进行预处理如计算度中心性以加速后续查询6. 图论在面试中的实际应用6.1 系统设计中的应用社交网络好友关系图、推荐系统网络路由互联网路由算法任务调度依赖关系处理地图服务路径规划、导航6.2 常见面试问题模式矩阵中的图问题将矩阵视为图的邻接矩阵树形问题树是特殊的图很多图算法适用于树状态转换问题将状态视为节点转换视为边分层图问题如带约束的最短路径6.3 面试准备建议掌握基础算法DFS、BFS、拓扑排序、最短路径等理解算法适用场景知道什么情况下用什么算法练习白板编码熟练在不借助IDE的情况下写出正确代码准备复杂度分析能够分析算法的时间和空间复杂度多做模拟面试适应面试环境和压力图论问题在面试中虽然挑战性较大但通过系统性的学习和足够的练习完全可以掌握。我个人的经验是先理解各类算法的核心思想然后通过大量题目练习来培养直觉。当看到一个图论问题时能够快速识别其类型并选择合适的解决方法。