当前位置:   article > 正文

算法总结篇——BFS_bfs算法

bfs算法

BFS 算法简介

BFS广度优先搜索(Breadth-First Search)的缩写,是一种图遍历算法。它从给定的起始节点开始,逐层地向外扩展,先访问起始节点的相邻节点,然后再访问相邻节点的相邻节点,以此类推,直到遍历完所有可达节点。

具体的BFS算法流程如下:

  1. 创建一个队列,并将起始节点入队;
  2. 将起始节点标记为已访问;
  3. 当队列不为空时,循环执行以下操作: a. 出队一个节点; b. 访问该节点; c. 将该节点的所有未访问相邻节点入队,并标记为已访问;
  4. 遍历完成。

BFS算法的特点是按照层级进行遍历,先访问离起始节点最近的节点,再访问离起始节点稍远一层的节点,依次类推。由于BFS需要使用队列来辅助实现,因此可以保证每个节点被访问且仅被访问一次。

BFS算法广泛应用于图的遍历、最短路径、连通性检测等问题,也可以用于解决一些搜索问题,例如在迷宫中找到最短路径等。

经典 BFS 问题

N叉树的层序遍历

N 叉树的层序遍历
在这里插入图片描述
在这里插入图片描述
这就是一个典型的层序遍历问题,将一层的节点入队列后,记录这一层的个数 sz,每当有个节点出队列一次,就将他的所有孩子节点都入队列,如此往复…

力扣代码:

/*
// 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>> ret;
        queue<Node*> q;
        if(root == nullptr) return ret;
        q.push(root);
        while(!q.empty())
        {
            int sz = q.size();
            vector<int> tmp;
            for(int i = 0; i < sz; i++)
            {
                Node* t = q.front();
                tmp.push_back(t->val);
                q.pop();
                for(auto &e: t->children)
                {
                    if(e!=nullptr) q.push(e);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

  • 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

BFS 解决最短路问题

这里的最短路问题,指的是边权相同的最短路问题。

在这里插入图片描述
如图,从 A 开始,走到 I 的最短路径是多少?

步骤:从起点开始,每一步都可能会有多种选择,每走一步,将下一次的所有选择都 “同时” 入队列(保证他们向外扩展的速度相同),同时将每一步得的位置都存入哈希表中,当准备入队时,发现哈希表中已经存在当前位置了,就不入队(因为时同时向外扩展得,所以当此位置已经在哈希表中存在时,说明当前这条路一定不是最佳选择,则舍去),记录公同向外扩展的次数,就是最短的路径长度!

迷宫中离入口最近的出口

迷宫中离入口最近的出口

在这里插入图片描述
这道题是经典的最短路径问题,也就是我们说的模板题

class Solution {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        bool vis[m][n];
        memset(vis, 0, sizeof vis);
        queue<pair<int, int>> q;
        q.push({entrance[0], entrance[1]});
        vis[entrance[0]][entrance[1]] = true;
        int step = 0; // 记录路径长度
        while(q.size() > 0)
        {
            step ++;
            int sz = q.size();
            for(int i = 0; i < sz; i++)
            {
                auto [a, b] = q.front();
                q.pop(); // 取出队头元素并出队
                for(int j = 0; j < 4; j++)
                {
                    // 找出队头元素的多种道路选择
                    int x = a + dx[j];
                    int y = b + dy[j];
                    if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !vis[x][y])
                    {
                        if(x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;
                        q.push({x, y}); // 将这种道路选择入队
                        vis[x][y] = true;
                    }
                }    
            }
        }
        return -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

多源BFS最短路问题

多源BFS最短路问题是一个经典的图论问题,也被称为全源最短路径问题。给定一个带权有向图和图中的多个源点,要求计算出从每个源点到图中所有其他节点的最短路径。

如果将多个源点的 BFS 问题,转化为多个单源点的 BFS 问题,但是大概率会超时,时间复杂度过高。

那么怎么办呢?将多个节点看作一个超级源点,将他们同时入队即可,然后一层一层的往外扩展,在写代码上,只需要将单源最短路中的将起点入队,改为将题目中给出的所有节点入队即可!

01 矩阵

01 矩阵
给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。
在这里插入图片描述
这是一个经典的多源 BFS 问题
但如果将1当作起点,0 当作终点的话,很难判定它的距离,于是我们正难则反,将0当作起点(将所有的 0 入队),1 当作终点进行一个多源 BFS 即可!

class Solution
{
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };
public:
	vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
	{
		int m = mat.size(), n = mat[0].size();
		// dist[i][j] == -1 表⽰:没有搜索过
		// dist[i][j] != -1 表⽰:最短距离
		vector<vector<int>> dist(m, vector<int>(n, -1));
		queue<pair<int, int>> q;
		// 1. 把所有的源点加⼊到队列中
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				if (mat[i][j] == 0)
				{
					q.push({ i, j });
					dist[i][j] = 0;
				}
		// 2. ⼀层⼀层的往外扩
		while (q.size())
		{
			auto [a, b] = q.front(); q.pop();
			for (int i = 0; i < 4; i++)
			{
				int x = a + dx[i], y = b + dy[i];
				if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
				{
					dist[x][y] = dist[a][b] + 1;
					q.push({ x, y });
				}
			}
		}
		return dist;
	}
};
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/一键难忘520/article/detail/737315?site
推荐阅读
相关标签
  

闽ICP备14008679号