BFS（Breadth First Search）算法的模型可以看做是一个"广度优先的搜索"过程，它以树或图的形式展开搜索。在BFS过程中，每个节点都被访问一次，并且所有节点都可以按照它们的距离（深度）从根节点分类。该算法是解决许多图论问题的基础，例如寻找节点之间的最短路径，查找图中的连通性等等。
在实现上，BFS使用队列来存储当前搜索的节点。从队列中取出首个未被访问的节点，并将其访问，并将其所有的邻居节点加入队列中。一旦访问某个节点，就将其标记为已经访问过的节点。如果没有找到目标节点，则重复执行此过程，直到队列为空或者找到目标节点。 可以采用迭代的方式实现BFS算法，也可以采用递归的方式实现。递归方式实现BFS需要考虑调用堆栈的深度问题，在搜索深度较大的情况下会出现堆栈溢出的情况，因此较为推荐的是迭代方式。
可以使用BFS算法场景：
1. 无权图的最短路径问题。
2. 树的层次遍历。
3. 图的连通性和环的问题。
4. 拓扑排序。
5. 最小生成树问题。
需要注意的事项：
1. 队列的数据结构使用循环队列可以较好地管理入队和出队操作。
2. 为了避免一个节点被重复访问，可以添加一个visited的数组，记录每个节点的状态。
3. 对于图，要注意处理孤立的节点。
BFS算法步骤：
1. 将起始节点入队，标记为visited。
2. 取出队首元素，查找其未被遍历的临近节点，入队且标记为visited。
3. 重复执行步骤2，直到队列为空或者找到目标节点。
4. 如果存在目标节点，返回结果；否则返回空或错误信息。
// BFS（广度优先搜索）算法模型是一种基于队列实现的搜索算法。
// 它从起点开始逐层向外搜索，搜索过程中每层节点按照先入先出的原则进行遍历，直到达到目标节点或者搜索完整个状态空间。
// BFS算法通常用于求解从起点到目标状态的最短路径或者最少步数等问题。
// bfs 1. 迷宫路径问题
// 在迷宫问题中，BFS算法可以用来查找从起点到终点的最短路径。
// 具体实现方式是，将起点加入到队列中，然后依次遍历当前节点的邻居节点，将其加入到队列中，直到找到终点或者队列为空。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ROWS 5
#define COLS 5
int board[ROWS][COLS] = {
{0, 0, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 1, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};
int visited[ROWS][COLS] = {0};
int steps[ROWS][COLS] = {0};
struct node {
int x;
int y;
int step;
};
struct node queue[ROWS * COLS];
void bfs(int start_x, int start_y, int end_x, int end_y)
{
int head = 0, tail = 0;
queue[tail].x = start_x;
queue[tail].y = start_y;
queue[tail].step = 0;
tail++;
visited[start_x][start_y] = 1;
while (head < tail) {
struct node cur = queue[head++];
if (cur.x == end_x && cur.y == end_y) {
printf("The shortest path is %d\n", cur.step);
return;
}
if (cur.x+1 < ROWS && board[cur.x+1][cur.y] == 0 && visited[cur.x+1][cur.y] == 0) {
queue[tail].x = cur.x+1;
queue[tail].y = cur.y;
queue[tail].step = cur.step+1;
tail++;
visited[cur.x+1][cur.y] = 1;
}
if (cur.x-1 >= 0 && board[cur.x-1][cur.y] == 0 && visited[cur.x-1][cur.y] == 0) {
queue[tail].x = cur.x-1;
queue[tail].y = cur.y;
queue[tail].step = cur.step+1;
tail++;
visited[cur.x-1][cur.y] = 1;
}
if (cur.y+1 < COLS && board[cur.x][cur.y+1] == 0 && visited[cur.x][cur.y+1] == 0) {
queue[tail].x = cur.x;
queue[tail].y = cur.y+1;
queue[tail].step = cur.step+1;
tail++;
visited[cur.x][cur.y+1] = 1;
}
if (cur.y-1 >= 0 && board[cur.x][cur.y-1] == 0 && visited[cur.x][cur.y-1] == 0) {
queue[tail].x = cur.x;
queue[tail].y = cur.y-1;
queue[tail].step = cur.step+1;
tail++;
visited[cur.x][cur.y-1] = 1;
}
}
printf("No path found!\n");
}
int main()
{
bfs(0, 0, ROWS-1, COLS-1);
return 0;
}
// bfs 2. 图的遍历
// 在图的遍历中，BFS算法可以用来查找从起点到目标节点的最短路径。具体实现方式是，将起点加入到队列中，然后依...
// 对于图的遍历，除了查找最短路径外，BFS算法还常用于判断图是否联通、检测图是否有环等问题。
// 判断图是否联通的方法是从任意一个没有被访问过的节点开始，使用BFS算法遍历整个图，若每个节点都被访问到了，则图是联通的。
// 检测图是否有环的方法是，在遍历到每个节点时，都检查是否已经被访问过，如果一个节点已经被访问过了，说明已经从其他路径到达该节点，表明存在一条环路。
// 以下是一个使用BFS算法实现检测图是否有环的代码示例：
// 以上代码中，使用了邻接表储存图的结构，add_edge函数用于向邻接表中添加一条边。
// has_cycle_bfs函数用于遍历每个节点，以此检测是否存在环路。
// 每次搜索时重新初始化visited数组，使用队列进行BFS搜索。
// 当搜索到一个已经访问过的节点时，就说明存在环路。最后在主函数中调用has_cycle_bfs函数来检测图是否有环。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODES 1000
int visited[MAX_NODES] = {0};
struct edge {
int to;
int next;
};
struct edge graph[MAX_NODES] = {0};
int head[MAX_NODES] = {0};
int num_edges = 0;
void add_edge(int u, int v)
{
graph[++num_edges].to = v;
graph[num_edges].next = head[u];
head[u] = num_edges;
}
int has_cycle_bfs(int n)
{
for (int i = 1; i <= n; i++) {
memset(visited, 0, sizeof(visited));
visited[i] = 1;
int queue[MAX_NODES] = {i};
int front = 0, rear = 0;
while (front <= rear) {
int cur = queue[front++];
for (int j = head[cur]; j; j = graph[j].next) {
int nxt = graph[j].to;
if (visited[nxt] == 0) {
visited[nxt] = 1;
queue[++rear] = nxt;
} else {
// 已经访问过该节点，说明存在环
return 1;
}
}
}
}
return 0;
}
int main()
{
// 构造一个有向图，图中有环路
add_edge(1, 2);
add_edge(2, 3);
add_edge(3, 4);
add_edge(4, 5);
add_edge(5, 1);
if (has_cycle_bfs(5)) {
printf("Graph has cycle(s)\n");
} else {
printf("Graph does not have cycle\n");
}
return 0;
}
// bfs 2. 图的遍历
// 在图的遍历中，BFS算法可以用来查找从起点到目标节点的最短路径。
// 具体实现方式是，将起点加入到队列中，然后依依次弹出队首元素，并将队首元素的邻居节点依次加入队列。
// 如此往复，直到找到目标节点或队列为空。
// 除了查找最短路径之外，BFS算法还可以用于其他几个问题，请列举出来并说明具体实现方式。
// 提示：可能用到的相关概念包括“图的遍历”、“图的连通性”、“环的概念”。
// 除了查找最短路径，BFS算法还可以用于以下几个问题：
// 1. 判断图是否连通
// 具体实现方法是，将任意一个没有被访问过的节点加入到队列中。然后在遍历的过程中，记录已经访问过的节点，在遍历结束后，如果已经访问过的节点数等于图的总节点数，则图是连通的；否则，图不连通。
// 2. 检测图是否存在环路
// 具体实现方法是，在遍历到每个节点时，都检查是否已经被访问过，如果一个节点已经被访问过了，说明已经从其他路径到达该节点，表明存在一条环路。
// 下面是使用C语言结合BFS算法实现判断图是否连通和检测图是否存在环路的代码示例：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_NODE_NUM 1000
#define QUEUE_SIZE MAX_NODE_NUM
// *************** 图的定义和构造 ***************//
struct node {
int id;
struct node *next;
};
struct graph {
int n; // 图中节点总数
struct node *adj[MAX_NODE_NUM];
bool visited[MAX_NODE_NUM]; // 节点是否被访问过
};
void graph_init(struct graph *g)
{
g->n = 0;
memset(g->adj, 0, MAX_NODE_NUM * sizeof(struct node *));
memset(g->visited, false, MAX_NODE_NUM);
}
void add_edge(struct graph *g, int from, int to)
{
struct node *n = (struct node *)malloc(sizeof(struct node));
n->id = to;
n->next = g->adj[from];
g->adj[from] = n;
}
// *************** BFS算法的核心实现 ***************//
struct queue {
int data[QUEUE_SIZE];
int front, rear;
};
void init_queue(struct queue *q)
{
memset(q->data, 0, QUEUE_SIZE * sizeof(int));
q->front = q->rear = 0;
}
void enqueue(struct queue *q, int x)
{
q->data[q->rear++] = x;
}
int dequeue(struct queue *q)
{
return q->data[q->front++];
}
int is_queue_empty(struct queue *q)
{
return (q->front == q->rear);
}
// 判断图是否连通
int is_graph_connected(struct graph *g)
{
int connected = 0;
struct queue q;
init_queue(&q);
enqueue(&q, 0);
g->visited[0] = true;
while (!is_queue_empty(&q)) {
int v = dequeue(&q);
connected++;
struct node *p = g->adj[v];
while (p) {
int w = p->id;
if (!g->visited[w]) {
g->visited[w] = true;
enqueue(&q, w);
}
p = p->next;
}
}
return (connected == g->n);
}
// 检测图是否有环，返回1为有环，返回0为无环
int is_graph_cyclic(struct graph *g)
{
int cyclic = 0;
struct queue q;
init_queue(&q);
for (int i = 0; i < g->n; i++) {
memset(g->visited, false, MAX_NODE_NUM);
enqueue(&q, i);
g->visited[i] = true;
while (!is_queue_empty(&q)) {
int v = dequeue(&q);
struct node *p = g->adj[v];
while (p) {
int w = p->id;
if (!g->visited[w]) {
g->visited[w] = true;
enqueue(&q, w);
} else {
cyclic = 1; // 存在环
}
p = p->next;
}
}
}
return cyclic;
}
// *************** 测试代码 ***************//
// 其中第一行通过调用`graph_init`函数初始化了图`g`；
// 接着通过`scanf`语句读入节点数和边数，然后通过`add_edge`函数添加边；
// 最后通过调用`is_graph_connected`和`is_graph_cyclic`函数检查图是否连通和是否存在环路，并将结果打印输出。
int main()
{
struct graph g;
graph_init(&g);
int nodes, edges;
scanf("%d%d", &nodes, &edges);
g.n = nodes;
for (int i = 0; i < edges; i++) {
int from, to;
scanf("%d%d", &from, &to);
add_edge(&g, from, to);
}
printf("Graph is%s connected\n", is_graph_connected(&g) ? "" : " not");
printf("Graph has%s cycle\n", is_graph_cyclic(&g) ? "" : " no");
return 0;
}
// BFS（广度优先搜索）算法模型是一种基于队列实现的搜索算法。
// 它从起点开始逐层向外搜索，搜索过程中每层节点按照先入先出的原则进行遍历，直到达到目标节点或者搜索完整个状态空间。
// BFS算法通常用于求解从起点到目标状态的最短路径或者最少步数等问题。
// 以下是一个生动形象的使用场景：社交网络中寻找两个人之间是否存在间接关系。
// 例如，在微博中，假设A关注了B，B又关注了C，那么A和C之间就存在间接关注关系，通过BFS算法可以找到这两个人之间的路径。
// 具体实现方式是，建立一个用户关注关系图，将A作为起点，C作为目标节点，
// 然后使用BFS算法进行搜索，每次遍历时将当前用户的粉丝加入队列中，
// 依次搜索其粉丝的粉丝，直到找到目标用户或者搜索完整个网络。
// 代码实现如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_USERS 1000
struct user {
int id;
int visited;
int num_followers;
int *followers;
};
struct user users[MAX_USERS] = {0};
void bfs(int start_id, int end_id)
{
int queue[MAX_USERS] = {0};
int head = 0, tail = 0;
queue[tail] = start_id;
head++;
users[start_id].visited = 1;
while (head < tail) {
int cur_id = queue[head++];
struct user cur_user = users[cur_id];
for (int i = 0; i < cur_user.num_followers; i++) {
int follower_id = cur_user.followers[i];
if (users[follower_id].visited == 0) {
queue[++tail] = follower_id;
users[follower_id].visited = 1;
if (follower_id == end_id) {
printf("Found a path from %d to %d\n", start_id, end_id);
return;
}
}
}
}
printf("No path found from %d to %d\n", start_id, end_id);
}
int main()
{
// 构建用户关注关系图
users[0].id = 0;
users[0].num_followers = 2;
users[0].followers = (int*)malloc(sizeof(int) * 2);
users[0].followers[0] = 1;
users[0].followers[1] = 2;
users[1].id = 1;
users[1].num_followers = 1;
users[1].followers = (int*)malloc(sizeof(int) * 1);
users[1].followers[0] = 2;
users[2].id = 2;
users[2].num_followers = 1;
users[2].followers = (int*)malloc(sizeof(int) * 1);
users[2].followers[0] = 3;
users[3].id = 3;
users[3].num_followers = 1;
users[3].followers = (int*)malloc(sizeof(int) * 1);
users[3].followers[0] = 4;
users[4].id = 4;
users[4].num_followers = 0;
// 使用BFS查找两个用户之间的关系
bfs(0, 4);
return 0;
}
