22_图论中的高级数据结构

菜鸟：老鸟，我最近在处理一个网络节点数据的问题，发现代码运行得特别慢。你能帮我看看有什么优化的方法吗？

老鸟：当然可以。你处理的是图结构对吗？你是如何存储和操作这些节点的？

菜鸟：是的，我用的是邻接矩阵存储的方式，但是在查询和更新时，感觉性能很糟糕。

老鸟：邻接矩阵在某些情况下确实会有性能瓶颈。今天我可以给你介绍几个图论中的高级数据结构，比如邻接表、优先队列、和Dijkstra算法等等，这些可以大大提升你的操作效率。

渐进式介绍概念

菜鸟：听起来不错，能先讲讲邻接表吗？

老鸟：好的。邻接表是一种更为内存友好的图表示方法。相比邻接矩阵，邻接表的空间复杂度是O(V + E)，其中V是顶点数，E是边数。

在邻接表中，每个顶点都会有一个列表，列表中存储与该顶点相邻的所有顶点。以下是一个简单的示例：

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

菜鸟：这个看起来更直观一些，查询一个顶点的邻居也很方便。

老鸟：是的，而且插入和删除操作也相对简单。让我们继续深入一些，看看如何使用邻接表进行图的遍历。

代码示例与分析

老鸟：以下是一个使用邻接表进行深度优先搜索（DFS）的示例：

def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start)for next in graph[start] - visited:dfs(graph, next, visited)return visited# 使用DFS遍历图
dfs(graph, 'A')

菜鸟：这里的visited是用来记录访问过的节点吗？

老鸟：没错，通过这个集合，我们可以避免重复访问节点，从而防止死循环。类似地，我们还可以实现广度优先搜索（BFS）。

from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])while queue:vertex = queue.popleft()if vertex not in visited:print(vertex)visited.add(vertex)queue.extend(graph[vertex] - visited)return visited# 使用BFS遍历图
bfs(graph, 'A')

问题与优化

菜鸟：这些遍历方法确实很有效，那在处理更复杂的图问题时，比如最短路径，该怎么优化呢？

老鸟：对于最短路径问题，Dijkstra算法是一个很好的选择。它使用优先队列来优化路径搜索过程。

import heapqdef dijkstra(graph, start):pq = [(0, start)]distances = {vertex: float('infinity') for vertex in graph}distances[start] = 0while pq:current_distance, current_vertex = heapq.heappop(pq)if current_distance > distances[current_vertex]:continuefor neighbor in graph[current_vertex]:distance = current_distance + graph[current_vertex][neighbor]if distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(pq, (distance, neighbor))return distances# 定义图，边的权重
weighted_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': 2},'F': {'C': 1, 'E': 2}
}# 计算最短路径
print(dijkstra(weighted_graph, 'A'))