BFS 广度优先搜索算法

,

BFS 广度搜索算法

BFS主要使用对图的遍历，通过队列的逐层扩展，按层次搜索所有可能的节点，确保找到最短的路径（无权图），BFS的本质是对图的暴力穷举，适合解决一些寻路的问题，比如找迷宫的最短路径

核心机制

使用队列驱动，时间复杂度通常为O(N)，N为状态数。空间复杂度为O(N)，储存所有当前层节点。

  1. 初始化：标记地图和障碍物，标记已经访问过的节点
  2. 循环处理：从队列的头节点来遍历之下的相邻位置
  3. 当队列为空遍历结束/找到终点

特点：使用队列（FIFO）保证操作顺序

优化及其变种

  • 双向BFS（bidirectional BFS）：从起点和终端同时进行BFS，相遇时停下
  • A*搜索：结合BFS和启发式函数，优先搜索更接近目标的节点

示例：

  • 问题：
    • 给定一个 N x M 的二维矩阵表示迷宫
      • 0 表示可以通行的空地。
    • 1 表示障碍物，不可通行。
    • 起点为 (0, 0)，终点为 (N-1, M-1)。
    • 每次移动可以向上、下、左、右四个方向行走一格，求从起点到终点的最短路径步数。如果无法到达终点，返回 -1。

步骤

  1. 初始化地图 标记数组 方向数组：
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
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
int maze[4][4] = {

    {0, 0, 0, 0},

    {1, 1, 0, 1},

    {0, 0, 0, 0},

    {0, 1, 1, 0}

};
int visited[4][4];

struct point {

    int x;

    int y;

    int step;

    queue<point> backpoint;

};

int dx[4] = {0, 0, -1, 1}; // 上 下 左 右

int dy[4] = {-1, 1, 0, 0};

queue<point> r;

int main() {

    int n = 3,m = 3;

    int startx = 0, starty = 0; // 起点位置

    int endx = 3, endy = 3;

}
  1. 初始化队列
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
point p;

    p.x = startx;

    p.y = starty;

    p.step = 0;

    visited[startx][starty] = 1;

 

    r.push(p);

 

    while(!r.empty()) {

        if (r.front().x == endx && r.front().y == endy) {

            printf("到达终点，坐标(%d, %d), 共%d步\n", r.front().x, r.front().y, r.front().step);

            return 0;

    }
  1. 访问头节点附近节点
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
 for (int i = 0; i < 4; i++) {

        point temp;

        int tx = r.front().x + dx[i];

        int ty = r.front().y + dy[i];

        if (tx >= 0 && tx < n && ty >= 0 && ty < m && maze[tx][ty] == 0 && visited[tx][ty] == 0) {

            temp.x = tx;

            temp.y = ty;

            temp.step = r.front().step + 1;

            temp.backpoint = r.front().backpoint;

            visited[tx][ty] = 1;

            r.push(temp);

        }

    }

    r.pop();

到达终点，坐标(3, 3), 共6步

通过队列回溯输出路径

定义一个parent来记录每一次的前驱节点坐标，注意要初始化起始点的前驱

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
33
34
35
36
37
38
39
40
pair<int, int> parent[4][4]; // 记录前驱节点

void printPath(int endX, int endY) {

    vector<pair<int, int>> path;

    int x = endX, y = endY;

    // 从终点回溯到起点

    while (x != -1 && y != -1) {

        path.push_back({x, y});

        auto p = parent[x][y];

        x = p.first;

        y = p.second;

    }

    // 逆序输出路径

    reverse(path.begin(), path.end());

    cout << "最短路径：" << endl;

    for (auto p : path) {

        cout << "(" << p.first << ", " << p.second << ") ";

    }

    cout << endl;

}



完整代码：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <bits/stdc++.h>

using namespace std;

  

int maze[4][4] = {

    {0, 0, 0, 0},

    {1, 1, 0, 1},

    {0, 0, 0, 0},

    {0, 1, 1, 0}

};

  

int visited[4][4];

  

struct point {

    int x;

    int y;

    int step;

};

  

int dx[4] = {0, 0, -1, 1}; // 上 下 左 右

int dy[4] = {-1, 1, 0, 0};

  

queue<point> r;

pair<int, int> parent[4][4]; // 记录前驱节点

  

int flag = 0;

  

void printPath(int endX, int endY) {

    vector<pair<int, int>> path;

    int x = endX, y = endY;

    // 从终点回溯到起点

    while (x != -1 && y != -1) {

        path.push_back({x, y});

        auto p = parent[x][y];

        x = p.first;

        y = p.second;

    }

    // 逆序输出路径

    reverse(path.begin(), path.end());

    cout << "最短路径：" << endl;

    for (auto p : path) {

        cout << "(" << p.first << ", " << p.second << ") ";

    }

    cout << endl;

}

  

int main() {

    int n = 4,m = 4;

    int startx = 0, starty = 0; // 起点位置

    int endx = 3, endy = 3;

  

    point p;

    p.x = startx;

    p.y = starty;

    p.step = 0;

    visited[startx][starty] = 1;

    parent[startx][starty] = {-1, -1}; // 起点无前驱

  

    r.push(p);

  

    while(!r.empty()) {

        if (r.front().x == endx && r.front().y == endy) {

            printf("到达终点，坐标(%d, %d), 共%d步\n", r.front().x, r.front().y, r.front().step);

            flag = 1;

            break;

    }

  

    for (int i = 0; i < 4; i++) {

        point temp;

        int tx = r.front().x + dx[i];

        int ty = r.front().y + dy[i];

        if (tx >= 0 && tx < n && ty >= 0 && ty < m && maze[tx][ty] == 0 && visited[tx][ty] == 0) {

            temp.x = tx;

            temp.y = ty;

            temp.step = r.front().step + 1;

            visited[tx][ty] = 1;

            parent[tx][ty] = {r.front().x, r.front().y}; // 记录前驱

            r.push(temp);

        }

    }

    r.pop();

}

  

if (flag == 1) {

    printPath(endx, endy);

}

  
  

if (flag == 0) puts("无法到达目标");

return 0;

  
  

}

应用

用一个ctf逆向题来学习这个算法：

使用c++的队列来处理，先完成一次寻路，到达终点后再回溯最短路径

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>

using namespace std;

  

int maps[58][58] = {{1,0,1}}; //省略地图
  

int visited[60][60] = {0};

struct point {

    int x;

    int y;

    int step;

    vector<pair<int, int>> path;

};

int dx[4] = {0, 0, -1, 1}; // 上 下 左 右

int dy[4] = {-1, 1, 0, 0};

queue<point> r;

string path1 = "S";

int main() {

    int n = 56, m = 56;  // 实际地图大小

    int startx = 1, starty = 1;

    int endx = 15, endy = 32;

    // 检查起始点和终点

    if (maps[startx][starty] != 0) {

        printf("起始点不可通行！起始点值：%d\n", maps[startx][starty]);

        return 0;

    }

    if (maps[endx][endy] != 0) {

        printf("终点不可通行！终点值：%d\n", maps[endx][endy]);

        return 0;

    }

    printf("起始点：(%d,%d)，终点：(%d,%d)\n", startx, starty, endx, endy);

    point p;

    p.x = startx;

    p.y = starty;

    p.step = 0;

    visited[startx][starty] = 1;

    r.push(p);

    while (!r.empty()) {

        point current = r.front();

        int x = r.front().x, y = r.front().y;

        // 判断是否到达终点

        if (x == endx && y == endy) {

            printf("到达终点，共%d步\n", r.front().step);

            for (int i = 0; i < current.path.size(); i++) {

                printf("第%d步: (%d, %d)", i+1, current.path[i].first, current.path[i].second);

                if (i > 0) {

                    int dx = current.path[i].first - current.path[i-1].first;

                    int dy = current.path[i].second - current.path[i-1].second;

                    if (dx == -1) printf(" [从(%d,%d)向上移动]", current.path[i-1].first, current.path[i-1].second), path1 += "W";

                    else if (dx == 1) printf(" [从(%d,%d)向下移动]", current.path[i-1].first, current.path[i-1].second), path1 += "S";

                    else if (dy == -1) printf(" [从(%d,%d)向左移动]", current.path[i-1].first, current.path[i-1].second), path1 += "A";

                    else if (dy == 1) printf(" [从(%d,%d)向右移动]", current.path[i-1].first, current.path[i-1].second), path1 += "D";

                }

            printf("\n");

        }

            std::cout << "结果为：" << path1 << '\n';

            return 0;

        }

        for (int j = 0; j < 4; j++) {

            int tx = x + dx[j];

            int ty = y + dy[j];

            // 修正边界检查和通行条件

            if (tx >= 0 && ty >= 0 && tx < n && ty < m &&

                maps[tx][ty] == 0 && visited[tx][ty] == 0) {

                point temp;

                temp.x = tx;

                temp.y = ty;

                temp.step = current.step + 1;

                temp.path = current.path;  // 复制当前路径

                temp.path.push_back({tx, ty});  // 添加新位置

                r.push(temp);

                visited[tx][ty] = 1;

            }

        }

        r.pop();

    }

    puts("未找到结果！");

    return 0;

}