在编程的浩瀚宇宙中，图（Graph）作为一种能够表达复杂数据关系的结构，其重要性不言而喻。Python，作为一门灵活且功能强大的编程语言，为我们提供了多种实现和遍历图的方法。今天，我们将一同探索Python中图的精妙表示方式以及高效遍历策略，旨在提升你的编程艺术感。
图的表示
在Python中，图通常可以通过邻接表（Adjacency List）或邻接矩阵（Adjacency Matrix）来表示。邻接表更节省空间，特别是对于稀疏图；而邻接矩阵则便于检查任意两点是否直接相连，但空间复杂度较高。
邻接表表示
python
使用字典实现邻接表
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F', 'G'],
'F': ['C', 'E'],
'G': ['E']
}
访问节点'A'的邻接节点
print("A的邻接节点:", graph['A'])
邻接矩阵表示
python
使用二维列表（或NumPy数组）实现邻接矩阵
假设图中只有上述7个节点
n = len(graph)
adjmatrix = [[0] * n for in range(n)]
根据邻接表填充邻接矩阵
for node in graph:
for neighbor in graph[node]:
adj_matrix[ord(node) - ord('A')][ord(neighbor) - ord('A')] = 1
打印邻接矩阵（部分）
print("邻接矩阵的部分内容:")
for row in adj_matrix[:3]:
print(row[:3]) # 仅打印前3x3的部分以节省空间
图的遍历
图的遍历主要有深度优先搜索（DFS）和广度优先搜索（BFS）两种策略。
深度优先搜索（DFS）
python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ') # 输出访问顺序
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
从节点'A'开始DFS遍历
dfs(graph, 'A')
广度优先搜索（BFS）
python
from collections import deque
def 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)
从节点'A'开始BFS遍历
bfs(graph, 'A')
结语
通过上面的示例，我们不仅学会了如何在Python中使用邻接表和邻接矩阵来表示图，还掌握了DFS和BFS两种高效遍历图的方法。这些基础但强大的技能，将帮助你解决更复杂的图论问题，并在实际编程中展现出更高的艺术感。无论是处理社交网络中的关系链，还是解决迷宫问题，图的精妙表示与高效遍历策略都是你不可或缺的工具。继续深入探索，让编程之路更加宽广而精彩！
