Python图算法入门指南（从零开始掌握图论与网络分析）

什么是图？

图由节点（Vertices 或 Nodes）和边（Edges）组成。节点代表实体（如用户、城市），边代表它们之间的关系（如好友关系、道路连接）。

• 有向图：边有方向（如 A → B）
• 无向图：边无方向（A — B 等价于 B — A）
• 加权图：边带有权重（如距离、成本）

Python 中如何表示图？

最常用的方式是使用邻接表（Adjacency List），可以用 Python 的字典（dict）轻松实现。

# 无向图的邻接表表示graph = {    'A': ['B', 'C'],    'B': ['A', 'D', 'E'],    'C': ['A', 'F'],    'D': ['B'],    'E': ['B', 'F'],    'F': ['C', 'E']}

这种结构清晰、节省空间，非常适合大多数图论基础操作。

常用图算法实战

1. 广度优先搜索（BFS）

BFS 用于遍历或搜索图中的节点，常用于求最短路径（无权图）。

from collections import dequedef bfs(graph, start):    visited = set()    queue = deque([start])    visited.add(start)        while queue:        node = queue.popleft()        print(node, end=' ')                for neighbor in graph[node]:            if neighbor not in visited:                visited.add(neighbor)                queue.append(neighbor)# 调用示例bfs(graph, 'A')  # 输出: A B C D E F

2. 深度优先搜索（DFS）

DFS 使用递归或栈，适合路径探索、拓扑排序等场景。

def dfs(graph, node, visited=None):    if visited is None:        visited = set()        visited.add(node)    print(node, end=' ')        for neighbor in graph[node]:        if neighbor not in visited:            dfs(graph, neighbor, visited)# 调用示例dfs(graph, 'A')  # 输出: A B D E F C

使用 NetworkX 库简化开发

对于更复杂的网络分析任务，推荐使用 Python 的 networkx 库，它内置了大量图算法。

import networkx as nximport matplotlib.pyplot as plt# 创建图G = nx.Graph()G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F'), ('E', 'F')])# 计算最短路径print(nx.shortest_path(G, 'A', 'F'))  # ['A', 'C', 'F']# 可视化图（可选）nx.draw(G, with_labels=True, node_color='lightblue', node_size=1500, font_size=16)plt.show()

总结

通过本教程，你已经掌握了图的基本概念、Python 表示方法以及 BFS/DFS 等核心算法。无论是学习数据结构教程，还是进行实际项目开发，这些知识都是坚实的基础。

下一步建议：尝试解决 LeetCode 上的图相关题目，或使用 NetworkX 分析真实社交网络数据，进一步提升你的Python图算法实战能力！