数据结构基础：图(Graph)的表示方法、邻接矩阵与邻接表、优先队列(Priority Queue)原理
好，咱们今天来聊聊路径规划里最基础、也最关键的东西——数据结构。说实话，我见过不少新手，算法背得滚瓜烂熟，一上手写代码就卡壳。为什么？说白了，就是图没表示好，队列没选对。你想想看，地图都画错了，导航怎么可能准？
一、图(Graph)到底是什么？
图，说白了就是一堆节点和一堆边的集合。节点代表位置，边代表通路。我习惯把图想象成一张地铁线路图——每个站是一个节点，站与站之间的轨道就是边。
图分两种：有向图和无向图。有向图就像单行道，只能朝一个方向走。无向图就像双向车道，两边都能走。路径规划里，大部分场景是无向图，但有些特殊情况（比如单行线、电梯只能上不能下）就得用有向图。
嗯，这里要注意：图还可以带权重。权重就是边的代价，比如距离、时间、油耗。A*和Dijkstra算法，本质上都是在带权图上找最短路径。
二、邻接矩阵——简单粗暴的表示法
邻接矩阵，就是用二维数组来存图。假设有N个节点，就开一个N×N的矩阵。matrix[i][j]表示从节点i到节点j的边权。如果没有边，通常用无穷大表示。
举个例子：
# 4个节点的无向图
# 节点0-1: 权重5
# 节点1-2: 权重3
# 节点2-3: 权重2
INF = float('inf')
graph = [
[0, 5, INF, INF],
[5, 0, 3, INF],
[INF, 3, 0, 2],
[INF, INF, 2, 0]
]
邻接矩阵的优点很明显：判断两个节点是否相连，时间复杂度是O(1)，直接查表就行。我在项目中处理小规模地图（比如几十个节点）时，经常用邻接矩阵，代码写起来特别快。
但缺点也很致命：空间复杂度是O(N²)。如果图有10000个节点，矩阵就有1亿个元素。大部分元素都是无穷大，白白浪费内存。我曾经接手过一个项目，地图有5000个节点，用邻接矩阵直接内存爆了。嗯，从那以后我就学乖了。
适用场景：节点少（通常小于1000）、图比较稠密（边数接近N²）的时候，用邻接矩阵很合适。
三、邻接表——省内存的利器
邻接表，说白了就是每个节点只存它邻居的信息。用Python的字典或列表来实现，每个节点对应一个列表，列表里存着(邻居节点, 边权)这样的元组。
# 同样的图，用邻接表表示
graph = {
0: [(1, 5)],
1: [(0, 5), (2, 3)],
2: [(1, 3), (3, 2)],
3: [(2, 2)]
}
你看，只存了实际存在的边。空间复杂度是O(N+E)，E是边的数量。对于稀疏图（边数远小于N²），邻接表能省下大量内存。
我个人的习惯是：只要节点数超过1000，一律用邻接表。有一次做城市路网规划，节点数十几万，用邻接矩阵想都不敢想，邻接表轻轻松松就搞定了。
不过邻接表也有个小缺点：判断两个节点是否相连，需要遍历邻居列表，时间复杂度是O(degree)，度越大越慢。但路径规划算法本身就要遍历邻居，所以这个缺点其实不算什么。
| 特性 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(N²) | O(N+E) |
| 查边时间 | O(1) | O(degree) |
| 遍历邻居 | O(N) | O(degree) |
| 适合场景 | 稠密图、小规模 | 稀疏图、大规模 |
四、优先队列(Priority Queue)——算法的加速器
Dijkstra和A*算法，核心操作就是反复从待处理节点中取出代价最小的那个。如果每次都用普通列表找最小值，时间复杂度是O(N)，整个算法就变成O(N²)了。这太慢了。
优先队列，说白了就是一个能自动排序的队列。每次插入元素，它会自动调整顺序。取元素时，永远返回最小的那个。Python里直接用heapq模块，底层是堆(Heap)实现的，插入和取出都是O(log N)。
import heapq
# 创建一个优先队列
pq = []
# 插入元素 (优先级, 数据)
heapq.heappush(pq, (5, '节点A'))
heapq.heappush(pq, (2, '节点B'))
heapq.heappush(pq, (8, '节点C'))
# 取出优先级最小的
priority, node = heapq.heappop(pq)
print(node) # 输出: 节点B (优先级2最小)
为什么会这样？因为堆是一种完全二叉树，父节点总是小于等于子节点。每次插入或删除，只需要沿着树做log N次比较，效率非常高。
避坑指南：我曾经在项目里直接用列表+排序来实现优先队列，结果地图一大，算法跑得比蜗牛还慢。后来换成heapq，速度提升了上百倍。记住：路径规划里，优先队列一定要用堆实现。
还有一个细节：Python的heapq默认是最小堆。如果你需要最大堆，可以取负数：
heapq.heappush(pq, (-priority, data)) # 取出来时再取反
五、三者如何配合？
在A*和Dijkstra算法里，这三者是这样配合的：
- 图结构：用邻接表存储地图信息，每个节点知道自己的邻居和边权。
- 优先队列：存储待探索的节点，按当前已知的最短距离排序。
- 算法流程：从起点开始，每次从优先队列取出距离最小的节点，遍历它的邻居，更新距离，把邻居插入优先队列。
你想想看，如果没有优先队列，每次都要遍历所有节点找最小值，那算法效率就太低了。如果没有邻接表，存几万个节点就内存爆炸。这三者缺一不可。
注意：优先队列里可能会重复插入同一个节点（因为找到了更短的路径）。这时候需要判断：如果取出的节点已经处理过，就跳过。否则算法可能会陷入死循环。
好了，数据结构这块就讲到这里。下一章我们开始真正写Dijkstra算法的代码，到时候你会看到这些数据结构是怎么串起来的。我个人建议你先动手把邻接表和优先队列的代码敲一遍，光看是记不住的。