宽度优先遍历（Breadth First Search，BFS）概念和实践介绍。概念部分包括定义，使用的场景和时空复杂度；实践就是代码部分，包括树的深度优先遍历、无向图的深度优先遍历（迪杰斯特拉算法，Dijkstra’s algorithm）和有向图的深度优先遍历（拓扑排序）。
理论部分
(1). BFS 的定义
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a search key), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
宽度优先是图或者树的一种遍历算法。宽度优先算法从树或者图的某一点出发，首先遍历当前节点周围邻居节点，然后进入下一层的遍历。
(2). 和DFS的对比
- DFS使用栈的数据结构，适合写成递归的形式；BFS 使用队列的数据结构，适合写成迭代的形式;
- DFS 适合寻找离源点较远的解，BFS适合寻找离源点近的解；
- DFS是按照某个条件针对一个点一直深入，如果不满足条件之后才回溯；BFS是优先考虑周围的点，分层扩展。
- BFS相比于DFS，其中一个特性就是BFS可以求出“最小值”，比如最短距离，最小步数等等。
例题
树的层序遍历
(1). Binary Tree Level Order Traversal
二叉树的层序遍历。
c++ 实现，关键是用一个空指针来表示一行的结束。
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
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
vector<int> tmp;
queue<TreeNode *> q; //没有 unorderd queue,队列是不需要排序的
q.push(root);
q.push(nullptr); // 通过空指针进行判断一行是否结束
while(q.front())
{
auto t =q.front();
q.pop();
vector<int> level;
// 这个是处理的一层的结点
while(t)
{
level.push_back(t->val);
// 这个是处理的下一层的结点
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
t =q.front(), q.pop();
}
q.push(nullptr);
res.push_back(level);
}
return res;
}
};
|
python实现，使用 from collections import deque 实现。 访问的话使用deque.popleft() 得到是队列的首元素，deque.append() 进行添加（和list是一样的操作的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
# python 中queue的概念使用 deque（双向队列）实现
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
queue, res =deque([root]), []
while queue:
level, size =[], len(queue)
# 因为python 中没有 front() 访问的属性，所以使用 size() 来代替这种属性
for i in range(size):
node =queue.popleft() # python deque 中popleft() 是访问得到队列的首元素
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
|
(2). Binary Tree Zigzag Level Order Traversal
这道题是上一道题目的延伸，需要多设置一个参数 zigzag 表明这个是不是要reverse
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
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
//# 在层序遍历上进行扩展， zigzag traversal ， 需要处理奇偶问题
queue<TreeNode *> q;
vector<vector<int>> res;
if (!root) return res;
bool zigzag =true;
q.push(root);
q.push(nullptr);
while(q.front())
{
auto t =q.front();
q.pop();
vector<int> level;
while(t)
{
level.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
t =q.front(), q.pop();
}
q.push(nullptr);
if(!zigzag) reverse(level.begin(), level.end());
zigzag =!zigzag;
res.push_back(level);
}
return res;
}
};
|
(3). N-ary Tree Level Order Traversal
python 实现，使用 deque 队列数据结构；对于多叉树，只有 children属性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
# n-ary 和二叉树是一样的解法，层次遍历的结果
def levelOrder(self, root: 'Node') -> List[List[int]]:
from collections import deque
if not root: return []
q =deque([root])
res =[]
while q:
level =[]
for i in range(len(q)): #使用确切的遍历的次数，不用使用 空指针进行判断了
cur =q.popleft()
for c in cur.children: # 是维护queue的代码
q.append(c)
level.append(cur.val)# 维护res 的结果, 对于多叉树，只是需要判断 child 属性即可
res.append(level)
return res
|
c++ 实现，通过 size 来遍历当下的层，而不是通过 nullptr 指针来进行判断。
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
|
/*
// 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>> res;
if(!root) return res;
res=vector<vector<int>> res;
queue<Node*> q;
q.push(root);
while(q.size())
{
vector<int> level =[];
int n =q.size();
while (n--)
{
Node * t =q.front();
q.pop();
for(int i =0; i<t->children.size(); i++ )
{
q.push(t->children[i]);
}
level.push_back(t->val);
}
res.push_back(level);
}
return res;
}
};
|
无向图
BFS的队列可以分段来看，层层扩展：第一次先把所有距离是0的点都加进队列，第二步把所有距离是1的点加入队列，依次类推，所以可以保证求出的距离就是最小值。
(1). 01 Matrix
寻找矩阵中距离数字0最近的距离。思路：如果矩阵位置本身是0，那么距离就是0，如果是1，那么以0为当前点进行扩展。
C++ 实现
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
|
class Solution {
public:
// bfs 是比较擅长解决最小值 ，最短距离这样的问题
// 使用队列存储，求解到0 的最短距离
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int dx[4] ={-1, 0, 1, 0}, dy[4] ={0, 1, 0 , -1};
int n =matrix.size(), m =matrix[0].size();
vector<vector<int>> res(n, vector<int>(m , -1));
queue<pair<int, int>> q;
for(int i =0; i<n; i++)
for(int j =0; j<m ;j++)
if(matrix[i][j] ==0)
{
res[i][j] =0;
q.push(make_pair(i,j));
}
while(q.size())
{
pair<int, int> t =q.front();
q.pop();
for(int i =0; i< 4; i++)
{
int a =t.first+dx[i];
int b =t.second +dy[i];
if(a <0 || a>= n|| b<0 || b>=m || res[a][b]!=-1 )
continue;
res[a][b] =res[t.first][t.second] +1; // 因为是bfs ，所以自然是一层层的遍历，所以每一层都是会加一
q.push(make_pair(a, b)); // 作为扩展层
}
}
return res;
}
};
|
对于周围”点“的扩展，数组（图）是按照”上右下左“的规则进行扩展；树是按照”根节点到叶结点“的顺序进行扩展。两者没有什么本质的差别。扩展的同时顺便解决了问题，所以这类问题本质上是遍历。
PS: c++的 stl 中只有unordered_map, 和 unordered_set 两种表示无序的数据结构，和有序的map 和set想对应。类似 queue和 stack 这类想想都是无序的。
有向图
(1). Course Schedule
考察的是拓扑排序，中间有用到 bfs 的思想。
- 拓扑排序
虽然说是排序，但是更像是一种图的遍历。 拓扑排序通常用来处理”排序“具有依赖关系问题。 排序方法关键需要维护一个入度为0的点集合，最后的时间复杂度是 $O(n +m) $，其中$n$ 和$m$ 分别表示点数和边数。
- 图的存储
图有邻接表和邻接矩阵两种存储方式。对于稀疏图和稠密图的定义没有明显的划分边界。稀疏图（sparse graph）的边数 $E$和点数$V$保持一致；稠密图（dense graph）一般接近于最多的边数。有向图中最多有 $E(E-1) $边，无向图中最多有$\frac{E(E-1)}{2}$条边。所以，如果是稠密图，使用邻接矩阵存储；如果是稀疏图，使用邻接表存储。
该问题中的图是稀疏图，使用邻接表进行存储。
拓扑排序是可以用来解决类似选课问题等有先后依赖关系的问题。该问题中需要维护一个邻接表和一个入度数组和一个队列。
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
|
class Solution {
public:
bool canFinish(int num, vector<vector<int>>& pre) {
vector<vector<int>> adj(num);
vector<int> in_degree(num, 0);
for(int i =0; i< pre.size() ; i++)
{
in_degree[pre[i][0]] ++;
adj[pre[i][1]].push_back(pre[i][0]);
}
for(auto u: in_degree) cout << u<<" ";
queue<int> q;
int couts =0;
for(int i =0; i< num; i++)
{
if(in_degree[i] ==0) q.push(i);
}
while(!q.empty())
{
int t =q.front();
q.pop();
couts +=1;
for(int i =0; i< adj[t].size(); i++)
{
in_degree[adj[t][i]] --;
if(in_degree[adj[t][i]] ==0) q.push(adj[t][i]);
}
}
return couts ==num;
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def canFinish(self, n: int, pre: List[List[int]]) -> bool:
#adj =collections.defaultdict(set)
#indegrees =collections.defaultdict(set)
# 手动进行初始化，因为下文是根据 set() 判断的
indegrees ={i : set() for i in range(n)}
adj ={i : set() for i in range(n)}
for i,j in pre:
adj[j].add(i)
indegrees[i].add(j)
q =collections.deque([i for i in indegrees if not indegrees[i]])
counts =0
while q:
t =q.popleft()
counts +=1
for i in adj[t]:
indegrees[i].remove(t)
if not indegrees[i]:
q.append(i)
return n ==counts
|
(2) Course Schedule II
相对于上一个题目 Course Schedule，本题要求记录课程安排记录。所以还是 拓扑排序+ BFS的思想，只不过是把拓扑排序的结果存储起来了。
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
|
class Solution {
public:
vector<int> findOrder(int n, vector<vector<int>>& pre) {
// 类似图的结果，首先使用邻接矩阵存储 adj，然后保存一个入度为0的输出，使用queue 表示拓扑排序的过程
vector<vector<int>> adj(n);
vector<int> in_degrees(n, 0);
queue<int> q;
for(int i =0; i<pre.size(); i++)
{
adj[pre[i][1]].emplace_back(pre[i][0]);
in_degrees[pre[i][0]] ++;
}
// 遍历入度为0 的点，放到 queue 中
for(int i =0; i<n; i++)
if(in_degrees[i] ==0) q.push(i);
int counts =0;
vector<int> res;
while(q.size())
{
auto t =q.front();
q.pop();
counts +=1;
res.emplace_back(t);
for(int i =0; i< adj[t].size(); i++)
{
in_degrees[adj[t][i]] -=1;
if(in_degrees[adj[t][i]] ==0) q.push(adj[t][i]);
}
}
if(counts == n) return res;
else return vector<int>{};
}
};
|
python解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
# 需要使用到的数据结构如队列，dictionary 存储adj 邻接表和 in_degree 记录信息
def findOrder(self, n: int, pre: List[List[int]]) -> List[int]:
adj =collections.defaultdict(set)
in_degrees ={i : set() for i in range(n)}
for i, j in pre:
adj[j].add(i)
in_degrees[i].add(j)
count, res =0, []
q =collections.deque([i for i in in_degrees if not in_degrees[i]]) # 处理的是入度为0 的情况
while q:
node =q.popleft()
res.append(node)
count +=1
for i in adj[node]:
in_degrees[i].remove(node)
if not in_degrees[i]:
q.append(i)
return res if count ==n else []
|
(3). Number of Islands
同上面的题目类似，但是这里适合使用dfs 进行求解。
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
|
class Solution {
public:
int dx[4] ={-1, 0, 1, 0}, dy[4] ={0, 1, 0, -1};
int n, m;
int numIslands(vector<vector<char>>& grid) {
if(grid.empty()) return 0;
n =grid.size(), m =grid[0].size();
int nums =0;
for(int i =0; i< n; i++)
for(int j =0; j< m ; j++)
if(grid[i][j] =='1')
{
nums ++;
dfs(grid, i, j); // 使用dfs 进行标记的作用
}
return nums;
}
void dfs(vector<vector<char>> & grid, int x, int y)
{
grid[x][y] ='0';
for(int i =0; i< 4; i++)
{
int a =x +dx[i], b =y +dy[i];
if(a >= 0 && a<n && b>=0 && b<m && grid[a][b] =='1')
dfs(grid, a, b);
}
}
};
|
python 版本， 注意如果是在一个类中，那么只能是在 __init__ 全局变量的申明。如果写到函数外面，是不认的。如果真个函数是 __main__ 的形式，那么在函数外面声明的变量是全局变量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def __init__(self):
self.dx =[-1,0, 1, 0]
self.dy =[0, 1, 0, -1]
def numIslands(self, grid: List[List[str]]) -> int:
nums =0
for i in range(len(grid)):
for j in range(len(grid[0])):
if(grid[i][j] =='1'):
nums +=1
self.dfs(grid, i, j)
return nums
def dfs(self, grid, x, y):
grid[x][y] ='0'
for i in range(4):
a, b =x +self.dx[i], y +self.dy[i]
if a >=0 and a< len(grid) and b >= 0 and b< len(grid[0]) and grid[a][b] =='1':
self.dfs(grid, a, b)
|
(4). Dijkstra’s 算法
Dijkstra’s algorithm (or Dijkstra’s Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
迪杰斯特拉算法是在图中寻找节点之间的最短路径的算法。
For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road (for simplicity, ignore red lights, stop signs, toll roads and other obstructions), Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities.
迪杰斯特拉算法可以寻找一点到其他所有点的最短路径。如果想要点到点的最短路径，那么找到目标点的时候，就可以停止。比如说：城市之间的最短路径问题；OSPF中使用该算法计算路由之间的最短的距离。
The Dijkstra algorithm uses labels that are positive integers or real numbers, which are totally ordered.
一般迪杰斯特拉算法要求边的权重是非负数。
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
1). Dijkstra求最短路 I
数据范围：
$$
\begin{split}
1 \leq & n \leq 500 \\
1 \leq & m \leq 10^5
\end{split}
$$
其中 $n$ 表示点的个数， $m$ 表示边的个数。则表明该图为稠密图，使用邻接矩阵存储。朴素迪杰斯特拉算法时间复杂度是$O(n^2)$。寻找路径最短的点是$O(n^2)$，加入集合是$O(n)$， 更新距离是$O(m)$ ，所以总的时间复杂度是$O(n^2)$
输入格式：
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出-1。
输入判断时候的优化。
1
2
3
|
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] =min(g[a][b], c); //从优化的角度，如果有重边，那么保留最短的一条。
|
2). Dijkstra求最短路 II
数据范围：
$$
\begin{split}
1 \leq n, m \leq 10^5
\end{split}
$$
其中 $n$ 表示点的个数， $m$ 表示边的个数。则表明该图是稀疏图，所以使用邻接表进行存储。对朴素迪杰斯特拉算法中寻找距离最短的点小根堆优化，从原来的 $O(n^2)$ 优化成$O(mlogn)$。其中堆取最小值是 $O(1)$，调整堆是$O(logn)$, 最多有 $m$条边，所以堆优化之后的时间复杂度是 $mlogn$。
c++ 代码实现
c++ 中默认是大根堆，可以在构造方法中修改成小根堆。
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include <climits>
using namespace std;
const int N =1e5+11;
int m,n;
struct Node{
int vec;
int w;
};
vector<Node> g[N];
bool vis[N];
int dis[N];
typedef pair<int, int> P;
// dijkstra 算法需要维护点的集合，寻找当前点到其余点的最短的路径，然后把其加入到该集合中
void dijkstra()
{
memset(vis, 0, sizeof vis);
for(int i =1; i<=m; i++) dis[i] =INT_MAX;
dis[1] =0; // 当前的结点从1 开始计数
priority_queue<P, vector<P>, greater<P>> min_heap; // c++ 中默认是大根堆，本题需要小根堆
min_heap.push({0, 1}); //{distance, vec}
while(min_heap.size())
{
auto t =min_heap.top();
min_heap.pop();
int vec =t.second;
int distance =t.first;
if(vis[vec] ==1) continue;
vis[vec] =1;
for(int i =0; i< g[vec].size(); i++)
{
int next_node =g[vec][i].vec;
if(distance +g[vec][i].w < dis[next_node])
{
dis[next_node] =distance +g[vec][i].w;
min_heap.push({dis[next_node], next_node});
}
}
}
}
int main()
{
cin >> m >>n; // m 个点，n 个边
Node node;
int a, b, c;
for(int i =0; i<n; i++)
{
cin >> a>>b>>c;
node.vec =b;
node.w =c;
g[a].emplace_back(node);
}
dijkstra();
if(dis[m] ==INT_MAX) cout << -1<< endl;
else cout << dis[m] << endl;
return 0;
}
|
空间上：能使用 emplace_back() 就不要使用 push_back()，后者在往 vector 中放元素的过程中，涉及到拷贝操作，是对于内存的浪费。同时拷贝操作的同时，浪费了时间。
python 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import heapq
class Solution:
# 使用小根堆优化，当寻找点的时候，小根堆log(V) 的时间，总共是 O(ElogV) 时间
# 如果没有优化，那么时间复杂度是 O(V^2)
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
graph = collections.defaultdict(dict) # 默认初始化的 dic of ，可以直接 += 操作
for source, des, cost in times:
graph[source][des] =cost
distances ={i : float('inf') for i in range(1, N+1)} # 使用字典存储距离
distances[K] =0 # 从该点出发
min_heap =[(0, K)]
visited =set() # python 中set 本来就是无序的，和c++ 中的set 和unordered_set 是不一样的, 这个是内置的函数，不需要import
while min_heap:
dis, vec = heapq.heappop(min_heap) # python 中默认是小根堆， 需要import heapq
if vec in visited: continue
visited.add(vec)
for neighbor in graph[vec]:
if neighbor in visited: continue
new_dis = dis+ graph[vec][neighbor]
if new_dis < distances[neighbor]:
distances[neighbor] =new_dis
heapq.heappush(min_heap, (new_dis, neighbor))
if len(visited) != len(distances) : return -1
return max(distances.values())
|
时间复杂度分析
- 如果是树模型，那么时间复杂度是 $O(T)$, T 表示树结点的个数
- 图模型：使用堆优化之后是 $O(Elog V)$，其中 $E$表示边的个数， $V$ 表示点的个数
- 数组类型： 时间复杂度是 $O(mn)$，其中 $m$, $n$ 表示数组的长度和宽度
参考资料
- Dijkstra’s algorithm
- Dijkstra求最短路
- leetcode题目