Python图算法BFS与DFS — 邻接表/最短路径/拓扑排序/环检测图由顶点和边组成在社交网络、路径规划、依赖分析中有广泛应用。Python中常用字典列表来表示图简洁高效。1. 图的表示邻接表/邻接字典from collections import defaultdict, dequeimport heapq# 使用字典存储邻接表{顶点: [邻居列表]}graph {A: [B, C],B: [A, D, E],C: [A, F],D: [B],E: [B, F],F: [C, E]}# 也可用defaultdict(list)自动处理不存在的键graph_dd defaultdict(list, {A: [B, C],B: [D, E],C: [F],})2. BFS广度优先搜索—— 最短路径def bfs_shortest_path(graph, start, end):BFS求无权图中的最短路径返回路径节点列表queue deque([[start]]) # 队列中存储路径visited {start}while queue:path queue.popleft()node path[-1]if node end: # 到达目标节点返回路径return pathfor neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)new_path list(path)new_path.append(neighbor)queue.append(new_path)return None # 不存在路径graph2 {A: [B, C], B: [A, D, E],C: [A, F], D: [B], E: [B, F], F: [C, E]}path bfs_shortest_path(graph2, A, F)print(A到F的最短路径:, path) # [A, C, F]3. DFS深度优先搜索—— 拓扑排序def topological_sort(graph):DFS实现拓扑排序用于有向无环图DAGvisited set() # 已访问节点stack [] # 存储拓扑顺序逆后序def dfs(node):visited.add(node)for neighbor in graph[node]:if neighbor not in visited:dfs(neighbor)stack.append(node) # 后序加入栈for node in list(graph.keys()):if node not in visited:dfs(node)return stack[::-1] # 反转得到拓扑顺序dag {5: [2, 0], 4: [0, 1],2: [3], 3: [1], 1: [], 0: []}print(拓扑排序:, topological_sort(dag)) # 多种可能如[5,4,2,3,1,0]4. 有向图中的环检测def has_cycle(graph):检测有向图是否存在环使用DFS三色标记法WHITE, GRAY, BLACK 0, 1, 2 # 未访问、正在访问、已访问完成color {node: WHITE for node in graph}def dfs(node):color[node] GRAY # 标记为正在访问for neighbor in graph[node]:if color[neighbor] GRAY: # 遇到正在访问的节点说明有环return Trueif color[neighbor] WHITE and dfs(neighbor):return Truecolor[node] BLACK # 标记为已访问完成return Falsefor node in graph:if color[node] WHITE:if dfs(node):return Truereturn Falsecyclic_graph {0: [1], 1: [2], 2: [0]} # 0-1-2-0 形成环print(有环吗:, has_cycle(cyclic_graph)) # True5. 连通分量def connected_components(graph):找出无向图中的所有连通分量visited set()components []def dfs(node, component):visited.add(node)component.append(node)for neighbor in graph[node]:if neighbor not in visited:dfs(neighbor, component)for node in graph:if node not in visited:component []dfs(node, component)components.append(component)return componentsundirected {A: [B], B: [A], C: [D], D: [C], E: []}print(连通分量:, connected_components(undirected)) # [[A,B],[C,D],[E]]6. Dijkstra 最短路径算法加权图def dijkstra(graph, start):Dijkstra算法求单源最短路径使用heapq优化# graph: {节点: [(邻居, 权重), ...]}INF float(inf)dist {node: INF for node in graph}dist[start] 0pq [(0, start)] # (距离, 节点) 元组存入堆while pq:d, node heapq.heappop(pq)if d dist[node]: # 如果堆中已有更短的路径则跳过continuefor neighbor, weight in graph[node]:new_dist d weightif new_dist dist[neighbor]:dist[neighbor] new_distheapq.heappush(pq, (new_dist, neighbor))return distweighted_graph {A: [(B, 1), (C, 4)],B: [(A, 1), (D, 2), (E, 5)],C: [(A, 4), (F, 1)],D: [(B, 2)],E: [(B, 5), (F, 3)],F: [(C, 1), (E, 3)]}distances dijkstra(weighted_graph, A)print(从A出发的最短距离:, distances) # {A:0,B:1,C:4,D:3,E:6,F:5}7. 图的遍历完整的BFS/DFS模板def bfs_full(graph, start):BFS全遍历返回访问顺序visited {start}queue deque([start])order []while queue:node queue.popleft()order.append(node)for neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)return orderdef dfs_full(graph, start):DFS全遍历迭代法返回访问顺序visited {start}stack [start]order []while stack:node stack.pop()order.append(node)for neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)stack.append(neighbor)return orderprint(BFS遍历:, bfs_full(graph2, A))print(DFS遍历:, dfs_full(graph2, A))