什么是优先队列？
你可以把优先队列想象成“插队”的队伍。普通队列是“先来先服务”，谁先排队谁先走。但优先队列不一样，谁的“优先级”高，谁就能先走。
比如：
- 医院急诊，病情重的先看。
- 游戏里，分数高的玩家先上榜。
优先队列常用的实现方法是“堆”，比如二叉堆。
优先队列常见的操作：
- 加入一个元素（push）
- 取出优先级最高的元素（pop/top）
在C++里有std::priority_queue，Go语言里可以用container/heap包。
举个例子（Go语言）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| package main
import (
"container/heap"
"fmt"
)
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
h := &IntHeap{}
heap.Init(h)
heap.Push(h, 3)
heap.Push(h, 1)
heap.Push(h, 5)
fmt.Println((*h)[0])
heap.Pop(h)
fmt.Println((*h)[0])
}
|
什么是广度优先搜索（BFS）？
广度优先搜索（BFS）其实就是“按圈扩散”。
想象你在操场上，站在起点，每次都走一步，先走离你最近的，再走远一点的。
BFS用的是普通队列，保证大家一圈一圈地被访问。
BFS的基本步骤：
- 把起点放进队列，并记下来已经来过。
- 不断从队列里拿出一个点，看看它能到哪些新地方，把没去过的都加进队列。
- 队列空了，说明所有能到的地方都走过了。
举个例子（Go语言）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| package main
import (
"container/list"
"fmt"
)
func bfs(graph [][]int, start int) {
visited := make([]bool, len(graph))
q := list.New()
q.PushBack(start)
visited[start] = true
for q.Len() > 0 {
e := q.Front()
u := e.Value.(int)
fmt.Print(u, " ")
q.Remove(e)
for _, v := range graph[u] {
if !visited[v] {
visited[v] = true
q.PushBack(v)
}
}
}
}
func main() {
graph := [][]int{{1, 2}, {0, 3}, {0, 3}, {1, 2}}
bfs(graph, 0)
}
|
两者的区别和联系
BFS用的是普通队列，适合“每一步花费都一样”的场景，比如迷宫最短路。
优先队列适合“每一步花费不一样”的场景，比如有的路长有的路短，这时候我们希望每次都先走“最省力”的那条路。
比如著名的Dijkstra算法，就是用优先队列来找最短路。
总结：
- BFS用普通队列，适合每一步代价一样的情况。
- 优先队列适合每一步代价不一样、需要优先处理“最优解”的情况。
为什么有时候要用优先队列来做广度搜索？
如果每一步的花费都一样（比如每走一步都花1元），用普通队列就行。
但如果有的路花1元，有的路花100元，我们当然想先走便宜的路。这时候就要用优先队列，每次都优先走“目前最省钱”的那条。
简单说：
- 每一步代价一样，用普通队列。
- 每一步代价不一样，用优先队列。
优先队列让搜索既能“按顺序扩展”，又能“按优先级扩展”，能解决更多实际问题。
