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 阅读数:35 评论数:0 点赞数:0 收藏数:0

BFS基础

```// 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;
}
};```

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;
}
};```

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

https://www.cnblogs.com/bangerlee/p/11223194.html