Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

算法与数据结构基础 - 广度优先搜索(BFS)

bangerlee 2019-07-28 16:43:00 阅读数:18 评论数:0 点赞数:0 收藏数:0

BFS基础

广度优先搜索(Breadth First Search)用于按离始节点距离、由近到远渐次访问图的节点,可视化BFS

通常使用队列(queue)结构模拟BFS过程,关于queue见:算法与数据结构基础 - 队列(Queue)

 

最直观的BFS应用是图和树的遍历,其中图常用邻接表或矩阵表示,例如 LeetCode题目 690. Employee Importance:

// LeetCode 690. Employee Importance
/*
class Employee { public: int id; int importance; vector<int> subordinates; }; */
// Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 Output: 11 class Solution { public: int getImportance(vector<Employee*> employees, int id) { int res=; unordered_map<int,Employee*> m; for(Employee* e:employees) m[e->id]=e; queue<Employee*> q; q.push(m[id]); while(!q.empty()){ Employee* cur=q.front();q.pop(); res+=cur->importance; for(auto s:cur->subordinates) q.push(m[s]); } return res; } };

 

相关LeetCode题:

690. Employee Importance  题解

513. Find Bottom Left Tree Value  题解

101. Symmetric Tree  题解

529. Minesweeper  题解

133. Clone Graph  题解

 

拓扑排序(Topological Sort)也应用了BFS遍历思想、以达成按依赖关系排序的目的,关于拓扑排序见:算法与数据结构基础 - 拓扑排序(Topological Sort)

 

层信息

BFS思路是从某节点层层往外扩展,一些场景下我们需要处理层(level)相关的信息,例如 LeetCode题目 102. Binary Tree Level Order Traversal:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            vector<int> tmp;
            for(int i=;i<size;i++){   //处理当前level
                TreeNode* cur=q.front();q.pop();
                tmp.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

以上代码不单遍历了树节点,还加了按层(level)处理,注意以上代码与遍历代码的细微差别。

 

相关LeetCode题:

102. Binary Tree Level Order Traversal  题解

429. N-ary Tree Level Order Traversal  题解

111. Minimum Depth of Binary Tree  题解

993. Cousins in Binary Tree  题解

515. Find Largest Value in Each Tree Row  题解

 

最短距离

BFS另一个重要的应用就是求最短路径,可以是单点到单点、单点到多点、多点到多点之间的路径。

当问题出现最小(minimum)、最短(shortest)等字样时可考虑用BFS求解,一般求解思路是 1/找出满足条件的起始点,2/由起始点开始进行BFS,3/遇到终点结束。

 

相关LeetCode题:

994. Rotting Oranges  题解

127. Word Ladder  题解

286. Walls and Gates  题解

505. The Maze II  题解

815. Bus Routes  题解

854. K-Similar Strings  题解

 

以上例题路径之间没有差别,更复杂的一种情况是路径具备权重。对有权图求解最短路径,一般情况下会想到Bellman-Ford、Dijkstra算法,而BFS思想是这些算法思想的核心。

 

相关LeetCode题:

 

避免BFS死循环

因问题不同、访问临近节点的方式各异,在使用BFS时我们可能会遇到重复访问某一节点的情况。

为了避免重复访问节点造成死循环,常用hashtable来记录节点是否已经被访问。

 

相关LeetCode题:

490. The Maze  题解

864. Shortest Path to Get All Keys   题解

版权声明
本文为[bangerlee]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/bangerlee/p/11223194.html