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

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

2019-07-28 16:43 by bangerlee, … 阅读, … 评论, 收藏, 编辑

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=0;
        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 题解

200. Number of Islands 题解

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=0;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;
    }
};