算法:BFS宽度优先遍历

这篇具有很好参考价值的文章主要介绍了算法:BFS宽度优先遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本篇总结的是BFS算法,BFS算法相比起DFS算法来说还是比较简单的

BFS与Queue相结合

N叉树的层序遍历

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

/*
// 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;
        if(root == nullptr)
            return ret;
        queue<Node*> qe;
        qe.push(root);
        while(!qe.empty())
        {
            int size = qe.size();
            vector<int> tmp;
            for(int i = 0; i < size; i++)
            {
                // 取队列头节点
                Node* front = qe.front();
                qe.pop();
                // 把值入到数组中
                tmp.push_back(front->val);
                // 如果有孩子,就把孩子入到队列中
                for(int j = 0; j < (front->children).size(); j++)
                    qe.push((front->children)[j]);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

二叉树的锯齿形层序遍历

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先
这里提供一种双端队列的做法,也可以在合适的层数逆序

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int>> res;
        if(root == nullptr)
            return res;
        bool status = true;
        queue<TreeNode*> qe;
        qe.push(root);
        while(!qe.empty())
        {
            int size = qe.size();
            deque<int> v;
            for(int i = 0; i < size; i++)
            {
                TreeNode* front = qe.front();
                qe.pop();
                if(status)
                    v.push_back(front->val);
                else
                    v.push_front(front->val);
                if(front->left) 
                    qe.push(front->left);
                if(front->right) 
                    qe.push(front->right);
            }
            res.push_back(vector<int>(v.begin(), v.end()));
            status = !status;
        }
        return res;
    }
};

二叉树的最大宽度

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
public:
    int widthOfBinaryTree(TreeNode* root) 
    {
        // 用数组来模拟队列,有助于最后计算,这里没用
        queue<pair<TreeNode*, unsigned int>> v;
        v.push(make_pair(root, 1));
        unsigned int lenth = 0;
        while(!v.empty())
        {
            // 计算一下这中间长度的差
            lenth = max(lenth, v.back().second - v.front().second + 1);
            int size = v.size();
            for(int i = 0; i < size; i++)
            {
                // 取头
                auto front = v.front();
                v.pop();
                // 如果有左或者有右节点,就进去
                if(front.first->left) 
                    v.push(make_pair(front.first->left, (front.second) * 2));
                if(front.first->right) 
                    v.push(make_pair(front.first->right, (front.second) * 2 + 1));
            }
        }
        return lenth;
    }
};

BFS和FLoodFill相结合

图像渲染

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

class Solution 
{
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        int oldcolor = image[sr][sc];
        int newcolor = color;
        if(oldcolor == newcolor)
            return image;
        queue<pair<int, int>> q;
        q.push({sr, sc});
        while(!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            image[a][b] = newcolor;
            for(int k = 0; k < 4; k++)
            {
                int x = dx[k] + a, y = dy[k] + b;
                if(x >= 0 && x < image.size() && y >=0 && y < image[0].size() && image[x][y] == oldcolor)
                    q.push({x, y});
            }
        }
        return image;
    }
};

岛屿数量

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

class Solution
{
    int res = 0;
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
public:
    int numIslands(vector<vector<char>>& grid)
    {
        vector<vector<bool>> check;
        check.resize(grid.size(), vector<bool>(grid[0].size(), false));
        queue<pair<int, int>> q;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == '1' && check[i][j] == false)
                {
                    check[i][j] = true;
                    q.push({ i, j });
                    while (!q.empty())
                    {
                        auto [a, b] = q.front();
                        q.pop();
                        for (int k = 0; k < 4; k++)
                        {
                            int x = dx[k] + a, y = dy[k] + b;
                            if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1' && check[x][y] == false)
                            {
                                check[x][y] = true;
                                q.push({ x, y });
                            }
                        }
                    }
                    res++;
                }
            }
        }
        return res;
    }
};

岛屿的最大面积

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

class Solution 
{
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        int res = 0, maxsize = 0, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        vector<vector<bool>> check(grid.size(), vector<bool>(grid[0].size(), false));
        queue<pair<int, int>> q;
        for(int i = 0; i < grid.size(); i++)
        {
            for(int j = 0; j < grid[0].size(); j++)
            {
                if(check[i][j] == false && grid[i][j] == 1)
                {
                    check[i][j] = true;
                    q.push({i, j});
                    res++;
                    while(!q.empty())
                    {
                        auto [a, b] = q.front();
                        q.pop();
                        for(int k = 0; k < 4; k++)
                        {
                            int x = dx[k] + a, y = dy[k] + b;
                            if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 1 && check[x][y] == false)
                            {
                                check[x][y] = true;
                                q.push({x, y});
                                res++;
                            }
                        }
                    }
                    maxsize = max(res, maxsize);
                    res = 0;
                }
            }
        }
        return maxsize;
    }
};

BFS解决最短路问题

最小基因变化

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

class Solution
{
public:
	int minMutation(string startGene, string endGene, vector<string>& bank)
	{
		// 首先把符合要求的字符串丢到哈希表中
		unordered_map<string, int> hash;
		for (auto& str : bank)
			hash[str]++;
		// vis数组用来存储已经加过的状态
		unordered_map<string, int> visited;

		char arr[4] = { 'A', 'C', 'G', 'T' };
		int step = 0;
		queue<string> q;
		q.push(startGene);
		visited[startGene]++;
		while (!q.empty())
		{
			step++;
			int qsize = q.size();
			for (int k = 0; k < qsize; k++)
			{
				string front = q.front();
				q.pop();
				// 对于字符串中的每一个元素都要进行枚举
				for (int i = 0; i < front.size(); i++)
				{
					string tmp = front;
					// front中的每一个元素都要被枚举四次
					for (int j = 0; j < 4; j++)
					{
						tmp[i] = arr[j];
						// 如果front在visited中存在,说明这个元素已经被找过了
						if (visited.count(tmp) == 0)
						{
							// 如果这个元素还在bank中,那么就是有效状态,那么就可以进入队列中
							if (hash.count(tmp))
							{
								q.push(tmp);
								visited[tmp]++;
								if (tmp == endGene)
									return step;
							}
						}
					}
				}
			}
		}
		return -1;
	}
};

单词接龙

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

class Solution 
{
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        // 用哈希表存储符合要求的顶点和已经访问过的顶点
        unordered_map<string, int> hash;
        unordered_map<string, int> visited;
        // 把wordlist中元素存储到哈希中
        for(auto& str : wordList)
            hash[str]++;
        // 把wordlist中的元素含有的字母进行标记
        set<int> st;
        for(auto str : wordList)
        {
            for(auto e : str)
            {
                st.insert(e);
            }
        }
        int stsize = st.size();
        // 定义一些变量
        int ret = 1;
        queue<string> q;
        q.push(beginWord);
        visited[beginWord]++;
        while(!q.empty())
        {
            int qsize = q.size();
            ret++;
            for(int i = 0; i < qsize; i++)
            {
                // 进入循环中一次,就意味着走了一步
                string front = q.front();
                q.pop();
                // 单词的每一个字母都可以进行变换
                for(int j = 0; j < front.size(); j++)
                {
                    string tmp = front;
                    // 每一个字母都有26种变换方式
                    for(int k = 0; k < 26; k++)
                    {
                        // 如果这个元素在set中出现过就可以使用
                        if(st.count('a' + k))
                            tmp[j] = 'a' + k;
                        else
                            continue;
                        // 对于变换后的结果tmp,如果这个结果在list中才能继续
                        if(hash.count(tmp) && visited.count(tmp) == 0)
                        {
                            // 如果tmp没有被访问过才能继续
                            visited[tmp]++;
                            q.push(tmp);
                            if(tmp == endWord)
                                return ret;
                        }
                    }
                }
            }
        }
        return 0;
    }
};

为高尔夫比赛砍树

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

struct Cmp
{
	bool operator()(const pair<int, pair<int, int>>& p1, const pair<int, pair<int, int>>& p2)
	{
		return p1.first > p2.first;
	}
};

class Solution
{
	int dx[4] = { 1, -1, 0, 0 };
	int dy[4] = { 0, 0, 1, -1 };
public:
	int cutOffTree(vector<vector<int>>& forest)
	{
		int m = forest.size(), n = forest[0].size();
		// 首先要把矩阵的信息存储起来
		priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, Cmp> heap;
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				if (forest[i][j] != 1 && forest[i][j] != 0)
					heap.push(make_pair(forest[i][j], make_pair(i, j)));
		// 此时堆中就是按高度排列,并且每一个高度会对应其下标
		int step = 0;
		int x = 0, y = 0;
		while (!heap.empty())
		{
			auto top = heap.top();
			heap.pop();
			int ans = bfs(x, y, top.second.first, top.second.second, forest);
			if (ans == -1)
				return -1;
			step += ans;
			x = top.second.first;
			y = top.second.second;
		}
		return step;
	}

	// bfs函数,用来寻找从[curx, cury]到[nextx, nexty]的最短路径
	int bfs(int curx, int cury, int nextx, int nexty, vector<vector<int>>& forest)
	{
		if (curx == nextx && cury == nexty)
			return 0;
		int m = forest.size(), n = forest[0].size();
		vector<vector<bool>> visited(m, vector<bool>(n, false));
		int step = 0;
		queue<pair<int, int>> q;
		q.push({ curx, cury });
		visited[curx][cury] = true;
		while (!q.empty())
		{
			int qsize = q.size();
			step++;
			for (int i = 0; i < qsize; i++)
			{
				auto [a, b] = q.front();
				q.pop();
				for (int k = 0; k < 4; k++)
				{
					int x = a + dx[k], y = b + dy[k];
					if (x == nextx && y == nexty)
						return step;
					// 如果这个下标合法,并且没有被选过,并且不是障碍,就进队列
					if (x >= 0 && x < m && y >= 0 && y < n && visited[x][y] == false && forest[x][y] != 0)
					{
						visited[x][y] = true;
						q.push({ x, y });
					}
				}
			}
		}
		return -1;
	}
};

拓扑排序

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

课程表

class Solution 
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        // 1. 建图
        // 一个用来存储图的边信息,一个用来存储图的入度信息
        unordered_map<int, vector<int>> graph;
        vector<int> in(numCourses);

        // 2. 把图的信息存储到图中
        for(auto& e : prerequisites)
        {
            int pre = e[1], next = e[0];
            graph[pre].push_back(next);
            in[next]++;
        }

        // 3. 多源bfs遍历
        queue<int> q;
        for(int e = 0; e < numCourses; e++)
            if(in[e] == 0)
                q.push(e);
        while(!q.empty())
        {
            int front = q.front();
            q.pop();
            for(auto e : graph[front])
            {
                in[e]--;
                if(in[e] == 0)
                    q.push(e);
            }
        }

        // 4. 判断有没有环
        for(auto e : in)
            if(e)
                return false;
        return true;
    }
};

课程表II

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先

class Solution 
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        vector<int> res;

        // 1. 建表
        unordered_map<int, vector<int>> graph;
        vector<int> in(numCourses);

        // 2. 把信息入表
        for(auto e : prerequisites)
        {
            int prev = e[1], next = e[0];
            graph[prev].push_back(next);
            in[next]++;
        }

        // 3. 多源bfs
        queue<int> q;
        // 把入度为0的点入到队列中
        for(int i = 0; i < numCourses; i++)
            if(in[i] == 0)
                q.push(i);
        while(!q.empty())
        {
            int front = q.front();
            q.pop();
            res.push_back(front);
            for(auto& e : graph[front])
            {
                in[e]--;
                if(in[e] == 0)
                {
                    q.push(e);
                }
            }
        }

        // 4. 判环
        for(int i = 0; i < numCourses; i++)
            if(in[i])
                return {};
        return res;
    }
};

火星词典

算法:BFS宽度优先遍历,C++,# 算法,知识总结,算法,宽度优先,深度优先文章来源地址https://www.toymoban.com/news/detail-834483.html

class Solution 
{
    // 1. 建图
    unordered_map<char, unordered_set<char>> edge;
    unordered_map<char, int> in;
    bool check;
public:
    string alienOrder(vector<string>& words) 
    {
        for(auto& str : words)
            for(auto& ch : str)
                in[ch] = 0;

        string res;
        // 2. 存储信息
        int n = words.size();
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++)
                add(words[i], words[j]);
        if(check)
            return "";
        
        // 3. 拓扑排序
        queue<char> q;
        for(auto& [a, b] : in)
            if(b == 0)
                q.push(a);

        while(!q.empty())
        {
            char front = q.front();
            q.pop();
            res += front;
            for(auto& ch : edge[front])
            {
                in[ch]--;
                if(in[ch] == 0)
                    q.push(ch);
            }
        }

        // 4. 检查
        for(auto& [a, b] : in)
            if(b)
                return "";
        return res;
    }

    void add(string& s1, string& s2)
    {
        int n = min(s1.size(), s2.size());
        
        int i = 0;
        for(; i < n; i++)
        {
            if(s1[i] != s2[i])
            {
                char a = s1[i], b = s2[i];
                if(edge.count(a) == 0 || edge[a].count(b) == 0)
                {
                    edge[a].insert(b);
                    in[b]++;  
                }
                break;
            }
        }

        if(i == s2.size() && i < s1.size())
            check = true;
    }
};

到了这里,关于算法:BFS宽度优先遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 宽度优先搜索算法(BFS)

    宽度优先搜索算法(BFS) (也称为 广度优先搜索 )主要运用于树、图和矩阵(这三种可以都归类在图中),用于在图中从起始顶点开始 逐层 地向外探索,直到找到目标顶点为止。 在本篇文章中,我们主要讨论其在 树 中的运用 树的宽度优先搜索 即 树的层序遍历 :逐层访

    2024年03月12日
    浏览(46)
  • 图的遍历(广度优先遍历BFS,深度优先遍历DFS)

    目录 图的遍历概念: 图的广度优先遍历(BFS): 代码实现如下: 测试如下: 注意: 图的深度优先遍历(DFS): 代码实现如下: 测试如下: 总代码: 结语: 给定一个图G和其中任意一个顶点v0,从v0出发,沿着图中各边访问图中的所有顶点,且每个顶点仅被遍历一次。\\\"遍

    2024年02月21日
    浏览(54)
  • 对无向图进行邻接矩阵的转化,并且利用DFS(深度优先)和BFS(广度优先)算法进行遍历输出, 在邻接矩阵存储结构上,完成最小生成树的操作。

    目录 一 实验目的 二 实验内容及要求 实验内容: 实验要求: 三 实验过程及运行结果 一 算法设计思路 二 源程序代码 三、截图 四 调试情况、设计技巧及体会 1.掌握图的相关概念。 2.掌握用邻接矩阵和邻接表的方法描述图的存储结构。 3.掌握图的深度优先搜索和广度优

    2024年02月04日
    浏览(54)
  • 【数据结构】图的遍历:广度优先(BFS),深度优先(DFS)

    目录 1、广度优先(BFS) 算法思想  广度优先生成树  知识树  代码实现  2、深度优先(DFS) 算法思想  深度优先生成树 知识树  代码实现           图的广度优先遍历(BFS)是一种遍历图的算法,其思想是从起始顶点开始遍历图,先访问起始顶点的所有直接邻居,然

    2024年02月04日
    浏览(63)
  • BFS算法(宽度优先搜索)超强解析 BFS迷宫问题图文详解 DFS与BFS的区别

      前情回顾:DFS练习-迷宫(最短路径)问题详解 一波三折 图片+文字 以及你需要会的基础:手搓数据结构之队列queue C/C++语言版(BFS算法预备知识) 广度优先搜索(Breadth First Search)简称广搜或者 BFS, 是遍历图存储结构的一种算法 。 BFS的原理是 “逐层扩散” ,从起点出发

    2024年02月22日
    浏览(46)
  • 【算法】广度优先遍历 (BFS)

    (1) 广度优先遍历 (Breadth First Search) ,又称 宽度优先遍历 ,是最简便的图的搜索算法之一。 (2)已知图 G = (V, E) 和一个源顶点 start,宽度优先搜索以一种系统的方式探寻 G 的边,从而“发现” start 所能到达的所有顶点,并计算 start 到所有这些顶点的距离(最少边数),

    2024年02月08日
    浏览(38)
  • 图的遍历——深度优先搜索(DFS)与广度优先搜索(BFS)(附带C语言源码)

    个人主页:【😊个人主页】 系列专栏:【❤️数据结构与算法】 学习名言:天子重英豪,文章教儿曹。万般皆下品,惟有读书高——《神童诗劝学》 第一章 ❤️ 学前知识 第二章 ❤️ 单向链表 第三章 ❤️ 递归 … 在此之前我们学习过了图的一些基本概念,如同在二叉树

    2024年02月06日
    浏览(65)
  • 【数据结构】图的创建和深度(DFS)广度(BFS)优先遍历

    图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为G(V,E),其中,G标示一个图, V是图G中 顶点的集合 , E是图G中 边的集合 。 图分为 无向图 和 有向图 无向图: 若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用序偶对(Vi,Vj)表示。 有向图: 若从

    2024年02月05日
    浏览(59)
  • 数据结构实验6 :图的存储与遍历(邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS)

    利用邻接矩阵存储无向图,并从0号顶点开始进行深度优先遍历。 输入第一行是两个整数n1 n2,其中n1表示顶点数(则顶点编号为0至n1-1),n2表示图中的边数。 之后有n2行输入,每行输入表示一条边,格式是“顶点1 顶点2”,把边插入图中。 例如: 4 4 0 1 1 3 0 3 0 2 先输出存储

    2024年02月09日
    浏览(63)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包