一、啥是广度优先搜索
广度优先搜索（BFS）就像是在一个大迷宫里找东西。咱们从起点开始，先看看离起点最近的那些地方，把这些地方都检查一遍，然后再去看离这些地方近的其他地方，一层一层地往外扩展。就好比你站在一个广场中间，先看看广场周围一圈的店铺，看完了再去看这些店铺旁边街道上的其他地方。
二、队列优化是怎么回事
在广度优先搜索里，队列就像是一个排队的队伍。咱们把要去探索的地方按照顺序排好队，每次从队伍最前面拿出一个地方去探索，然后把这个地方能到达的新地方都加到队伍的末尾。这样就能保证我们是一层一层地去探索，不会乱了顺序。
比如说，我们有一个图，里面有很多节点，每个节点都和其他一些节点相连。我们从一个节点开始，把这个节点放到队列里，然后开始探索。每次从队列里拿出一个节点，看看它能到达哪些新节点，把这些新节点都加到队列末尾。这样不断重复，直到队列为空。
三、实现图的层级遍历
我们来用 Java 实现图的层级遍历。这里我们用邻接表来表示图，邻接表就是一个数组，数组里每个元素是一个链表，链表存储了和这个节点相连的其他节点。
// Java 技术栈
import java.util.*;
// 图类
class Graph {
private int V; // 节点数量
private LinkedList<Integer> adj[]; // 邻接表
// 构造函数
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// 添加边
void addEdge(int v, int w) {
adj[v].add(w);
}
// 层级遍历
void BFS(int s) {
// 标记节点是否被访问过
boolean visited[] = new boolean[V];
// 创建队列
LinkedList<Integer> queue = new LinkedList<Integer>();
// 标记当前节点为已访问并加入队列
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
// 从队列头部取出一个节点
s = queue.poll();
System.out.print(s + " ");
// 获取当前节点的所有邻接节点
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
// 标记未访问的邻接节点为已访问并加入队列
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
// 创建一个有 4 个节点的图
Graph g = new Graph(4);
// 添加边
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("从节点 2 开始的层级遍历结果:");
g.BFS(2);
}
}
在这个例子里，我们首先创建了一个图，然后添加了一些边。接着从节点 2 开始进行层级遍历，把访问过的节点依次打印出来。
四、求解最短路径
广度优先搜索还可以用来求解最短路径。因为它是一层一层地扩展，所以第一次到达某个节点时经过的路径就是最短路径。
我们还是用上面的图，稍微修改一下代码来求解最短路径。
// Java 技术栈
import java.util.*;
// 图类
class Graph {
private int V; // 节点数量
private LinkedList<Integer> adj[]; // 邻接表
// 构造函数
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// 添加边
void addEdge(int v, int w) {
adj[v].add(w);
}
// 求解最短路径
void shortestPath(int start, int end) {
// 标记节点是否被访问过
boolean visited[] = new boolean[V];
// 存储每个节点的前一个节点
int[] prev = new int[V];
// 创建队列
LinkedList<Integer> queue = new LinkedList<Integer>();
// 标记当前节点为已访问并加入队列
visited[start] = true;
queue.add(start);
prev[start] = -1;
while (queue.size() != 0) {
// 从队列头部取出一个节点
int s = queue.poll();
// 如果到达目标节点，结束搜索
if (s == end) {
break;
}
// 获取当前节点的所有邻接节点
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
// 标记未访问的邻接节点为已访问并加入队列
visited[n] = true;
queue.add(n);
prev[n] = s;
}
}
}
// 从目标节点回溯到起始节点
List<Integer> path = new ArrayList<>();
for (int at = end; at != -1; at = prev[at]) {
path.add(at);
}
Collections.reverse(path);
if (path.get(0) != start) {
System.out.println("没有找到路径");
} else {
System.out.println("最短路径: " + path);
}
}
public static void main(String args[]) {
// 创建一个有 4 个节点的图
Graph g = new Graph(4);
// 添加边
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("从节点 0 到节点 3 的最短路径:");
g.shortestPath(0, 3);
}
}
在这个例子里，我们用一个数组 prev 来存储每个节点的前一个节点，这样就能通过回溯找到最短路径。
五、应用场景
广度优先搜索的应用场景有很多。比如说在社交网络里，我们可以用它来找到两个用户之间的最短关系链。在游戏里，我们可以用它来找到角色从一个位置到另一个位置的最短路径。在地图导航里，也可以用它来规划最短路线。
六、技术优缺点
优点
- 简单易懂：广度优先搜索的逻辑比较简单，很容易理解和实现。
- 能找到最短路径：因为它是一层一层地扩展，所以能保证找到的路径是最短的。
- 适用于无权图：对于没有边权的图，广度优先搜索是一个很好的选择。
缺点
- 空间复杂度高：需要使用队列来存储待探索的节点，当图很大时，队列可能会占用很多内存。
- 不适用于带权图：如果图中的边有不同的权重，广度优先搜索就不能找到最优路径了，需要用其他算法，比如 Dijkstra 算法。
七、注意事项
- 节点标记：在遍历过程中，一定要标记节点是否被访问过，否则会出现重复访问的情况，导致无限循环。
- 队列管理：队列的操作要正确，确保先加入的节点先被访问。
- 图的表示：要根据图的特点选择合适的表示方法，比如邻接表或邻接矩阵。
八、文章总结
广度优先搜索是一种非常实用的算法，通过队列优化可以实现图的层级遍历和最短路径求解。它的逻辑简单，能解决很多实际问题，比如社交网络分析、游戏路径规划等。不过它也有一些缺点，比如空间复杂度高和不适用于带权图。在使用时，我们要注意节点标记、队列管理和图的表示等问题。
评论