能否通过不同优先级策略，用优先队列实现DFS、BFS、Dijkstra、Prim？

结论：仅关注顶点探索顺序时，这四种算法完全可以用优先队列实现，核心差异仅在于顶点优先级的分配策略，以下是具体实现方案：

1. BFS（广度优先搜索） #

优先级策略：顶点到起点的层数（步数）

• 起始顶点优先级设为0
• 处理顶点u时，其未访问的邻接顶点v的优先级设为u的优先级 + 1
• 使用最小堆作为优先队列，保证层数小的顶点先被探索，契合BFS逐层遍历的顺序

2. DFS（深度优先搜索） #

优先级策略：单调递减的全局计数器值（模拟栈的"后进先出"逻辑）

• 初始化全局计数器（例如设为-1，或负的图顶点总数，确保数值覆盖所有节点）
• 起始顶点优先级设为计数器--（如初始为-1，起点优先级为-1，计数器变为-2）
• 处理顶点u时，按期望的分支顺序遍历其未访问的邻接顶点v，每个v的优先级设为计数器--后加入队列
• 使用最小堆作为优先队列：新发现的节点优先级更小，会被优先取出处理，完美实现DFS深度优先探索分支的逻辑——第一个分支的所有节点处理完毕后，才会处理起点的第二个子节点

3. Dijkstra（最短路径算法） #

优先级策略：起点到该顶点的当前最短路径估计值

• 起始顶点优先级设为0
• 处理顶点u时，其未访问的邻接顶点v的优先级设为u的优先级 + 边u-v的权重（若该值小于v当前优先级则更新）
• 使用最小堆作为优先队列，每次选择当前路径最短的顶点扩展，符合Dijkstra的贪心策略

4. Prim（最小生成树算法） #

优先级策略：顶点到当前生成树的最小边权

• 初始化时，起始顶点优先级设为0，其余所有顶点优先级设为无穷大
• 处理顶点u时，遍历其未访问的邻接顶点v，若边u-v的权值小于v当前优先级，则更新v的优先级为该边权值并加入队列
• 使用最小堆作为优先队列，每次选择离当前生成树最近的顶点加入，保证生成树总权重最小

内容的提问来源于stack exchange，提问作者Monarch