算法【宽度优先遍历及其扩展】

宽度优先遍历根本内容

1.bfs的特点是逐层扩散，从源头点到目的点扩散了几层，最短路就是多少。

2.bfs可以使用的特性是恣意两个节点之间的相互间隔类似（无向图）。

3.bfs开始时，可以是单个源头、也可以是多个源头。

4.bfs频仍使用队列，情势可以是单点弹出大概整层弹出。

5.bfs举行时，进入队列的节点须要标志状态，防止同一个节点重复收支队列。

6.bfs举行时，大概会包罗剪枝计谋的计划。

7.bfs是一个明白难度很低的算法，难点在于节点怎样找到路、路的睁开和剪枝计划。

01bfs，实用于图中全部边的权重只有0和1两种值，求源点到目的点的最短间隔

时间复杂度为O(节点数目+边的数目)

1.distance体现从源点到i点的最短间隔，初始时全部点的distance设置为无穷大。

2.源点进入双端队列，distance[源点]=0。

3.双端队列头部弹出x，

   A.假如x是目的点，返回distance[x]体现源点到目的点的最短间隔。

   B.观察从x出发的每一条边，假设某边去y点，边权为w

      1）假如 distance[y] > distance[x] + w，处理处罚该边；否则忽略该边。

      2）处理处罚时，更新distance[y] = distance[x] + w

         假如w==0，y重新部进入双端队列；假如w==1，y从尾部进入双端队列。

      3）观察完x出发的全部边之后，重复步调3。

4.双端队列为空制止。

宽度优先遍历与优先级队列团结，更进一步的内容会在讲Dijkstra算法时分析。

宽度优先遍历与深度优先遍历团结，去天生路径

1.bfs建图。

2.dfs使用图天生路径。

下面通过几个标题加深明白。

标题一

测试链接：https://leetcode.cn/problems/as-far-from-land-as-possible/

分析：这是一个多源宽度优先，将全部的陆地入队列。然后开始按层出队列，假如附近是海洋，则将海洋编号为层数，直到没有编号为0的海洋，分情况返回。代码如下。

1. class Solution {
2. public:
3.     int queue[10000][2];
4.     int arr[5] = {0, 1, 0, -1, 0};
5.     int maxDistance(vector<vector<int>>& grid) {
6.         int row = grid.size();
7.         int column = grid[0].size();
8.         int l = 0, r = 0, level = 0;
9.         int temp, cur_row, cur_column;
10.         for(int i = 0;i < row;++i){
11.             for(int j = 0;j < column;++j){
12.                 if(grid[i][j] == 1){
13.                     queue[r][0] = i;
14.                     queue[r++][1] = j;
15.                 }
16.             }
17.         }
18.         while (l < r)
19.         {
20.             ++level;
21.             temp = r;
22.             for(;l < temp;++l){
23.                 cur_row = queue[l][0];
24.                 cur_column = queue[l][1];
25.                 for(int index = 0;index < 4;++index){
26.                     if(cur_row+arr[index] >= 0 && cur_row+arr[index] < row && cur_column+arr[index+1] >= 0 && cur_column+arr[index+1] < column
27.                     && grid[cur_row+arr[index]][cur_column+arr[index+1]] == 0){
28.                         queue[r][0] = cur_row+arr[index];
29.                         queue[r++][1] = cur_column+arr[index+1];
30.                         grid[cur_row+arr[index]][cur_column+arr[index+1]] = level;
31.                     }
32.                 }
33.             }
34.         }
35.         if((l == 0 && r == 0) || (level == 1)){
36.             return -1;
37.         }else{
38.             return --level;
39.         }
40.     }
41. };

复制代码

此中，(l == 0 &&r == 0)代表全为海洋，level == 1代表全为陆地。

标题二

测试链接：https://leetcode.cn/problems/stickers-to-spell-word/

分析：这个使用宽度优先遍历的思绪比力奇妙。让target进队列，按层出队列，然后每一层都去遍历贴纸，将target减去遍历到的字符串的字符串进队列，假如此字符串已经在队列则跳过，直到减去之后为空字符串代表拼出了target，且如今使用的贴纸数目最少。代码如下。

1. class Solution {
2. public:
3.     vector<vector<int>> graph;
4.     set<string> visited;
5.     string queue[401];
6.     void build(vector<string>& stickers){
7.         vector<int> temp;
8.         graph.assign(26, temp);
9.         int length1 = stickers.size();
10.         int length2;
11.         for(int i = 0;i < length1;++i){
12.             sort(stickers[i].begin(), stickers[i].end());
13.             length2 = stickers[i].size();
14.             for(int j = 0;j < length2;++j){
15.                 if((j == 0) || (stickers[i][j] != stickers[i][j-1])){
16.                     graph[stickers[i][j] - 'a'].push_back(i);
17.                 }
18.             }
19.         }
20.     }
21.     string next(string cur, string sticker){
22.         int length1 = cur.size();
23.         int length2 = sticker.size();
24.         string s = "";
25.         int i, j;
26.         for(i = 0, j = 0;i < length1 && j < length2;){
27.             if(cur[i] == sticker[j]){
28.                 ++i;
29.                 ++j;
30.             }else if(cur[i] < sticker[j]){
31.                 s += cur[i];
32.                 ++i;
33.             }else{
34.                 ++j;
35.             }
36.         }
37.         if(j == length2){
38.             while (i < length1)
39.             {
40.                 s += cur[i];
41.                 ++i;
42.             }
43.         }
44.         return s;
45.     }
46.     int minStickers(vector<string>& stickers, string target) {
47.         sort(target.begin(), target.end());
48.         build(stickers);
49.         int level = 0;
50.         int l = 0, r = 0, temp;
51.         queue[r++] = target;
52.         visited.insert(target);
53.         while (l < r)
54.         {
55.             ++level;
56.             temp = r;
57.             for(;l < temp;++l){
58.                 string cur = queue[l];
59.                 int len = graph[cur[0] - 'a'].size();
60.                 for(int i = 0;i < len;++i){
61.                     string Next = next(cur, stickers[graph[cur[0] - 'a'][i]]);
62.                     if(Next == ""){
63.                         return level;
64.                     }else if(visited.count(Next) == 0){
65.                         queue[r++] = Next;
66.                         visited.insert(Next);
67.                     }
68.                 }
69.             }
70.         }
71.         return -1;
72.     }
73. };

复制代码

此中，使用set来实现队列中不会出现重复字符串。

标题三

测试链接：https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/

分析：这个就是开头先容的01bfs。下一步假如是停滞物则此节点到一下个节点的间隔为1，否则为0，流程按01bfs教学的写就行。代码如下。

1. class Solution {
2. public:
3.     int arr[5] = {0, 1, 0, -1, 0};
4.     int deque[100001][2] = {0};
5.     vector<vector<int>> distance;
6.     void build(vector<vector<int>>& grid, int row, int column){
7.         vector<int> temp;
8.         temp.assign(column, -1);
9.         distance.assign(row, temp);
10.         distance[0][0] = 0;
11.     }
12.     int minimumObstacles(vector<vector<int>>& grid) {
13.         int row = grid.size();
14.         int column = grid[0].size();
15.         build(grid, row, column);
16.         int l = 0, r = 0;
17.         deque[r][0] = 0;
18.         deque[r++][1] = 0;
19.         while (true)
20.         {
21.             int cur_row = deque[l][0];
22.             int cur_column = deque[l][1];
23.             l = (l + 1) % 100001;
24.             if(cur_row == row-1 && cur_column == column-1){
25.                 return distance[row-1][column-1];
26.             }
27.             for(int index = 0;index < 4;++index){
28.                 if(cur_row+arr[index] >= 0 && cur_row+arr[index] < row
29.                 && cur_column+arr[index+1] >= 0 && cur_column+arr[index+1] < column){
30.                     if(distance[cur_row+arr[index]][cur_column+arr[index+1]] == -1
31.                     || distance[cur_row][cur_column] + grid[cur_row+arr[index]][cur_column+arr[index+1]] < distance[cur_row+arr[index]][cur_column+arr[index+1]]){
32.                         distance[cur_row+arr[index]][cur_column+arr[index+1]] = distance[cur_row][cur_column] + grid[cur_row+arr[index]][cur_column+arr[index+1]];
33.                         if(grid[cur_row+arr[index]][cur_column+arr[index+1]] == 1){
34.                             deque[r][0] = cur_row+arr[index];
35.                             deque[r++][1] = cur_column+arr[index+1];
36.                         }else{
37.                             l = (l - 1 + 100001) % 100001;
38.                             deque[l][0] = cur_row+arr[index];
39.                             deque[l][1] = cur_column+arr[index+1];
40.                         }
41.                     }
42.                 }
43.             }
44.         }
45.     }
46. };

复制代码

此中，双端队列接纳界说一个数组实现。

标题四

测试链接：https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

分析：这个题和标题三差不多。下一个节点的方向和箭头指向方向同等，则此节点和下一个节点间隔为0，否则为1。代码如下。

1. class Solution {
2. public:
3.     int move[5][2] = {{0 ,0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
4.     int distance[101][101];
5.     deque<vector<int>> dq;
6.     void build(vector<vector<int>>& grid, int row, int column){
7.         int max_value = -(1 + (1 << 31));
8.         for(int i = 0;i < row;++i){
9.             for(int j = 0;j < column;++j){
10.                 distance[i][j] = max_value;
11.             }
12.         }
13.         distance[0][0] = 0;
14.     }
15.     int minCost(vector<vector<int>>& grid) {
16.         int row = grid.size();
17.         int column = grid[0].size();
18.         int cur_row, cur_column, cost, next_row, next_column;
19.         build(grid, row, column);
20.         vector<int> ini;
21.         ini.push_back(0);
22.         ini.push_back(0);
23.         dq.push_back(ini);
24.         while (true)
25.         {
26.             cur_row = dq.front()[0];
27.             cur_column = dq.front()[1];
28.             dq.pop_front();
29.             if(cur_row == row-1 && cur_column == column-1){
30.                 return distance[row-1][column-1];
31.             }
32.             for(int index = 1;index <= 4;++index){
33.                 next_row = cur_row + move[index][0];
34.                 next_column = cur_column + move[index][1];
35.                 cost = grid[cur_row][cur_column] == index ? 0 : 1;
36.                 if(next_row >= 0 && next_row < row
37.                 && next_column >= 0 && next_column < column
38.                 && distance[cur_row][cur_column] + cost < distance[next_row][next_column]){
39.                     distance[next_row][next_column] = distance[cur_row][cur_column] + cost;
40.                     vector<int> temp;
41.                     temp.push_back(next_row);
42.                     temp.push_back(next_column);
43.                     if(cost == 0){
44.                         dq.push_front(temp);
45.                     }else{
46.                         dq.push_back(temp);
47.                     }
48.                 }
49.             }
50.         }
51.     }
52. };

复制代码

此中，双端队列接纳stl实现。

标题五

测试链接：https://leetcode.cn/problems/trapping-rain-water-ii/

分析：这个题的队列接纳优先队列，显然，矩阵的附近是接不到水的。先将矩阵的附近入队列，队列中的元素为行列坐标以及这个位置的水线，水性就是这个位置水能到达的最高高度，附近的水线高度自然就是位置的高度。然后从优先队列中弹出元素，弹出元素时更新接雨水的体积，用水线高度减去当前位置的高度，就是增长的接雨水的体积。将弹出位置附近参加进队列，进队列时的水线高度为弹出元素的水线高度和附近当前位置的高度取最大值。队列空时，得到答案。代码如下。

1. class Solution {
2. public:
3.     int arr[5] = {0, 1, 0, -1, 0};
4.     bool visited[200][200] = {false};
5.     int trapRainWater(vector<vector<int>>& heightMap) {
6.         int row = heightMap.size();
7.         int column = heightMap[0].size();
8.         int ans = 0;
9.         vector<int> cur;
10.         auto cmp = [](vector<int> v1, vector<int> v2)->bool{
11.             return v1[2] > v2[2];
12.         };
13.         priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> q(cmp);
14.         for(int i = 0;i < column;++i){
15.             if(!visited[0][i]){
16.                 visited[0][i] = true;
17.                 vector<int> temp;
18.                 temp.push_back(0);
19.                 temp.push_back(i);
20.                 temp.push_back(heightMap[0][i]);
21.                 q.push(temp);
22.             }
23.         }
24.         for(int i = 0;i < column;++i){
25.             if(!visited[row-1][i]){
26.                 visited[row-1][i] = true;
27.                 vector<int> temp;
28.                 temp.push_back(row-1);
29.                 temp.push_back(i);
30.                 temp.push_back(heightMap[row-1][i]);
31.                 q.push(temp);
32.             }
33.         }
34.         for(int i = 0;i < row;++i){
35.             if(!visited[i][0]){
36.                 visited[i][0] = true;
37.                 vector<int> temp;
38.                 temp.push_back(i);
39.                 temp.push_back(0);
40.                 temp.push_back(heightMap[i][0]);
41.                 q.push(temp);
42.             }
43.         }
44.         for(int i = 0;i < row;++i){
45.             if(!visited[i][column-1]){
46.                 visited[i][column-1] = true;
47.                 vector<int> temp;
48.                 temp.push_back(i);
49.                 temp.push_back(column-1);
50.                 temp.push_back(heightMap[i][column-1]);
51.                 q.push(temp);
52.             }
53.         }
54.         while (!q.empty())
55.         {
56.             cur = q.top();
57.             q.pop();
58.             ans += (cur[2] - heightMap[cur[0]][cur[1]]);
59.             for(int index = 0;index < 4;++index){
60.                 if(cur[0]+arr[index] >= 0 && cur[0]+arr[index] < row
61.                 && cur[1]+arr[index+1] >= 0 && cur[1]+arr[index+1] < column
62.                 && visited[cur[0]+arr[index]][cur[1]+arr[index+1]] == false){
63.                     visited[cur[0]+arr[index]][cur[1]+arr[index+1]] = true;
64.                     vector<int> temp;                  
65.                     temp.push_back(cur[0]+arr[index]);
66.                     temp.push_back(cur[1]+arr[index+1]);
67.                     temp.push_back((heightMap[cur[0]+arr[index]][cur[1]+arr[index+1]] > cur[2] ?
68.                     heightMap[cur[0]+arr[index]][cur[1]+arr[index+1]] : cur[2]));
69.                     q.push(temp);
70.                 }
71.             }
72.         }
73.         return ans;
74.     }
75. };

复制代码

此中，visited数组体现当前位置是否进过队列，false代表没有，true代表进过。

标题六

测试链接：https://leetcode.cn/problems/word-ladder-ii/

分析：这道题接纳宽度优先和深度优先团结的方式。先用bfs找到endWord是否可以大概转化，同时，在bfs的时间把图建好，图代表入度节点可以转换为出度节点。然后使用dfs得到每一个最短转换序列，dfs的开头是endWord，末了是beginWord，以是须要将序列翻转才是答案。代码如下。

1. class Solution {
2. public:
3.     set<string> dict;
4.     set<string> curLevel;
5.     set<string> nextLevel;
6.     map<string, vector<string>> graph;
7.     vector<string> path;
8.     vector<vector<string>> ans;
9.     void build(vector<string>& wordList){
10.         int length = wordList.size();
11.         for(int i = 0;i < length;++i){
12.             dict.insert(wordList[i]);
13.         }
14.     }
15.     bool bfs(string beginWord, string endWord){
16.         bool find = false;
17.         curLevel.insert(beginWord);
18.         string cur_str;
19.         int cur_str_length;
20.         char old;
21.         while (!curLevel.empty())
22.         {
23.             for(set<string>::iterator it = curLevel.begin();it != curLevel.end();++it){
24.                 dict.erase((*it));
25.             }
26.             for(set<string>::iterator it = curLevel.begin();it != curLevel.end();++it){
27.                 cur_str = *it;
28.                 cur_str_length = cur_str.size();
29.                 for(int i = 0;i < cur_str_length;++i){
30.                     old = cur_str[i];
31.                     for(char ch = 'a'; ch <= 'z';++ch){
32.                         cur_str[i] = ch;
33.                         if(dict.count(cur_str) != 0 && ch != old){
34.                             if(endWord.compare(cur_str) == 0){
35.                                 find = true;
36.                             }
37.                             if(graph.count(cur_str) == 0){
38.                                 vector<string> temp;
39.                                 graph.insert(make_pair(cur_str, temp));
40.                             }
41.                             (*graph.find(cur_str)).second.push_back((*it));
42.                             nextLevel.insert(cur_str);
43.                         }
44.                     }
45.                     cur_str[i] = old;
46.                 }
47.             }
48.             if(find){
49.                 return true;
50.             }else{
51.                 set<string> temp;
52.                 temp = curLevel;
53.                 curLevel = nextLevel;
54.                 nextLevel = temp;
55.                 nextLevel.clear();
56.             }
57.         }
58.         return false;
59.     }
60.     void dfs(string word, string aim){
61.         path.push_back(word);
62.         int length;
63.         if(word.compare(aim) == 0){
64.             vector<string> temp(path.begin(), path.end());
65.             reverse(temp.begin(), temp.end());
66.             ans.push_back(temp);
67.         }else if(graph.count(word) != 0){
68.             length = (*graph.find(word)).second.size();
69.             for(int i = 0; i < length;++i){
70.                 dfs((*graph.find(word)).second[i], aim);
71.             }
72.         }
73.         path.pop_back();
74.     }
75.     vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
76.         build(wordList);
77.         if(dict.count(endWord) == 0){
78.             return ans;
79.         }
80.         if(bfs(beginWord, endWord)){
81.             dfs(endWord, beginWord);
82.         }
83.         return ans;
84.     }
85. };

复制代码

此中，bfs中的建图接纳毗连表建图；而且判定当前层字符串可否转换为已有的字符串接纳将当前层字符串的每个位置更换一次26个字母，判定新字符串是否存在的方法；bfs没有使用队列，而是使用两个层，当前层的字符串从已存在的字符串中删去制止重复遍历，天生好下一层后，当前层和下一层互换，然后清空下一层；思量到图的意义，以是dfs天生的序列是从endWord到beginWord的，以是须要翻转。