在Python的广阔世界里，数据结构是构建高效算法的基石。当谈及复杂的数据关系与交互时，图（Graph）这一高级数据结构无疑占据了举足轻重的地位。不同于线性结构如列表和树，图通过节点（Vertex）和边（Edge）的任意连接，展现了数据间错综复杂的关系。解锁图的表示与遍历技巧，不仅能让你的算法思维跃升至新高度，还能在解决实际问题时游刃有余。
图的表示
在Python中，图可以通过多种方式表示，其中最常见的是邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。
邻接矩阵：使用一个二维数组（或列表的列表）来存储图中每对顶点之间是否存在边。如果顶点i与顶点j之间有边，则对应位置为1（或边的权重），否则为0。这种方法简单直观，但空间复杂度较高，特别是对于稀疏图。
python
邻接矩阵表示法
graph = [
[0, 1, 0, 0, 1],
[1, 0, 1, 1, 1],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 1],
[1, 1, 0, 1, 0]
]
邻接表：使用字典（或列表的列表）来存储每个顶点的所有邻接点。这种方法空间效率高，特别适用于稀疏图。
python
邻接表表示法
graph = {
'A': ['B', 'E'],
'B': ['A', 'C', 'D', 'E'],
'C': ['B', 'D'],
'D': ['B', 'C', 'E'],
'E': ['A', 'B', 'D']
}
图的遍历
图的遍历是理解图结构和解决图问题的关键步骤，主要有深度优先搜索（DFS）和广度优先搜索（BFS）两种策略。
深度优先搜索（DFS）：从某一顶点出发，尽可能深地搜索图的分支，直到该顶点所在的路径到达末尾，再回溯到前一个顶点继续搜索其他路径。
python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for next_node in graph[start]:
if next_node not in visited:
dfs(graph, next_node, visited)
调用DFS
dfs(graph, 'A')
广度优先搜索（BFS）：从某一顶点开始，先访问其所有邻接点，再逐层向外访问，直到访问完所有可达的顶点。
python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(set(graph[vertex]) - visited)
调用BFS
bfs(graph, 'A')
总结
通过对比邻接矩阵与邻接表的不同表示方式，我们可以根据图的稀疏程度选择最适合的存储方式。而深度优先搜索与广度优先搜索则各有千秋，DFS更适合于寻找解的路径或判断图中是否存在环，BFS则常用于求解最短路径问题。掌握这些高级数据结构的表示与遍历方法，无疑能让你的算法思维更加灵活多变，为解决复杂问题提供有力支持。
