『算法』广度优先搜索

『算法』广度优先搜索

本篇博客我们来介绍一下广度优先搜索的基本思想。

什么是广度优先搜索

广度优先搜索（又称广度优先搜索）是最简便的图的搜索算法之一。英文缩写为BFS（Breadth First Search）。属于一种盲目搜索法，目的是系统地展开并检查图中的所有结点，以找寻结果。换句话说，它不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

我们来看一个迷宫问题：
假设有一个迷宫，里面有障碍物，迷宫用二维矩阵表示，标记为0的地方表示可以通过，标记为1的地方表示障碍物，不能通过。现在给一个迷宫出口，让你判断是否可以从入口进来之后，走出迷宫，每次可以向任意方向走。

• 假设是一个10*10的迷宫，入口在(1, 1)的位置，出口在(8, 10)的位置，通过(1, 1)一步可以走到的位置有两个(1, 2)，(2, 1)；
• 但是这两个点并不是出口，需要继续通过这两个位置进一步搜索，假设现在在(1, 2)，下一次一步可以到达的新的位置为(1, 3)，(2, 2)。而通过(2, 1)可以一步到达的新的位置为(2, 2)，(3, 1)，但是这里(2, 2)是重复的，所以没一个点在走的过程中需要标记是否已经走过了；
• 两步之后，还没有走到出口，这时候需要通过新加入的点再去探索下一步能走到哪些新点上，重复这个过程，直到走到出口为止。

我们直接来看实现代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;static int nextPos[4][2] = {{ 1, 0 }, { 0, 1 }, { -1, 0 }, {0, -1}
};bool BFS(vector<vector<int>>& graph, int sx, int sy, int ex, int ey) {int row = graph.size();int col = graph[0].size();queue<pair<int, int>> q;vector<vector<int>> book(row, vector<int>(col, 0));q.push(make_pair(sx, sy));book[sx][sy] = 1;bool flag = false;while (!q.empty()) {for (int i = 0; i < 4; ++i) {int newX = q.front().first + nextPos[i][0];int newY = q.front().second + nextPos[i][1];if (newX >= row || newX < 0 || newY >= col || newY < 0) {continue;}if (graph[newX][newY] == 0 && book[newX][newY] == 0) {q.push(make_pair(newX, newY));book[newX][newY] = 1;}if (newX == ex && newY == ey) {flag = true;break;}}if (flag) break;q.pop();}return flag;
}int main() {int sx, sy, ex, ey;int row, col;cout << "请输入迷宫的行和列: ";cin >> row >> col;vector<vector<int>> graph(row, vector<int>(col, 0));cout << "请输入迷宫: n";for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {cin >> graph[i][j];}}cout << "请输入迷宫的入口和出口: n";cin >> sx >> sy >> ex >> ey;cout << "是否可以走出迷宫: " << BFS(graph, sx, sy, ex, ey) << endl;return 0;
}

根据上面的例子，我们可以提炼出广度优先搜索的模型：

/** BFS() {*     1. 建立起始步骤，队列初始化；*     2. 遍历队列中的每一种可能；*     while (队列不为空) {*         通过对头元素带出下一步的所有可能，并且一次入队；*         {*             判断当前情况是否达成目标：按照目标要求处理逻辑；*         }*         继续遍历队列中的剩余情况；*     }* }*/

几个简单的例子加深理解

员工的重要性

/*
// Employee info
class Employee {
public:// It's the unique ID of each node.// unique id of this employeeint id;// the importance value of this employeeint importance;// the id of direct subordinatesvector<int> subordinates;
};
*/
class Solution {
public:int getImportance(vector<Employee*> employees, int id) {if (pty()) {return 0;}unordered_map<int, Employee*> info;for (const auto& e : employees) {info[e->id] = e;}int sum = 0;BFS(info, id, sum);return sum;}void BFS(unordered_map<int, Employee*>& info, int id, int& sum) {queue<int> q;q.push(id);while (!q.empty()) {sum += info[q.front()]->importance;for (const auto& subid : info[q.front()]->subordinates) {q.push(subid);}q.pop();}}
};

N叉树的层序遍历

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/
class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> result;if (root == nullptr) {return result;}queue<Node*> q;q.push(root);while (!q.empty()) {int qSize = q.size();vector<int> curLevel(qSize);for (int i = 0; i < qSize; ++i) {Node* curNode = q.front();curLevel[i] = curNode->val;for (const auto& node : curNode->children) {q.push(node);}q.pop();}result.push_back(curLevel);}return result;}
};

腐烂的橘子

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {if (pty()) {return 0;}int row = grid.size();int col = grid[0].size();queue<pair<int, int>> q;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (grid[i][j] == 2) {q.push(make_pair(i, j));}}}int nextPos[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};int minutes = 0;while (!q.empty()) {++minutes;int qSize = q.size();for (int i = 0; i < qSize; ++i) {pair curPair = q.front();for (int i = 0; i < 4; ++i) {int newX = curPair.first + nextPos[i][0];int newY = curPair.second + nextPos[i][1];if (newX >= row || newX < 0 || newY >= col || newY < 0) {continue;}if (grid[newX][newY] == 1) {q.push(make_pair(newX, newY));grid[newX][newY] = 2;}}q.pop();}}bool flag = false;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (grid[i][j] == 1) {flag = true;break;}}}minutes = minutes ? --minutes : minutes;return flag ? -1 : minutes;}
};

单词接龙

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordSet(wordList.begin(), d());unordered_set<string> visited;int length = beginWord.size();int steps = 0;queue<string> q;q.push(beginWord);while (!q.empty()) {++steps;int qSize = q.size();for (int i = 0; i < qSize; ++i) {string curWord = q.front();if (curWord == endWord) {return steps;}for (int i = 0; i < length; ++i) {string newWord(curWord);for (char ch = 'a'; ch <= 'z'; ++ch) {newWord[i] = ch;if (!unt(newWord) || unt(newWord)) {continue;}q.push(newWord);visited.insert(newWord);}}q.pop();}}return 0;}
};

打开转盘锁

class Solution {
public:int openLock(vector<string>& deadends, string target) {unordered_set<string> deadSet(deadends.begin(), d());if (unt("0000")) {return -1;}int steps = 0;unordered_set<string> visited;visited.insert("0000");queue<string> q;q.push("0000");while (!q.empty()) {int qSize = q.size();for (int i = 0; i < qSize; ++i) {string curPW = q.front();if (unt(curPW)) {return -1;}if (curPW == target) {return steps;}visited.insert(curPW);for (int j = 0; j < 4; ++j) {string newPW1(curPW);string newPW2(curPW);newPW1[j] = newPW1[j] == '9' ? '0' : ++newPW1[j];newPW2[j] = newPW2[j] == '0' ? '9' : --newPW2[j];if (!unt(newPW1) && !unt(newPW1)) {q.push(newPW1);visited.insert(newPW1);}if (!unt(newPW2) && !unt(newPW2)) {q.push(newPW2);visited.insert(newPW2);}}q.pop();}++steps;}return -1;}
};