数据结构与算法：宽度优先遍历

前言

进入图论部分难度明显提升了一大截，思路想不到一点……

一、宽度优先遍历

1.内容

宽度优先遍历主要用于在图上求最短路。

（1）特点

宽度优先遍历的特点就是逐层扩展，最短路即层数

（2）使用条件

无向图且任意节点间距离相等

（3）注意

进入队列后需标记状态防止重复入队。

可剪枝！！可单源头可多源头！！

（4）难点

主要难点在于节点如何找路、路的展开以及剪枝方法。

2.题目

（1）地图分析

class Solution {
public://移动 -> 上下左右vector<int>move={-1,0,1,0,-1};int maxDistance(vector<vector<int>>& grid) {int n=grid.size();vector<vector<bool>>visited(n,vector<bool>(n));queue<pair<int,int>>node;int seas=0;//初始化for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(grid[i][j]==1)//陆地{visited[i][j]=true;node.push(make_pair(i,j));}else//海洋{seas++;}}}//特例if(seas==0||seas==n*n){return -1;}//统计int level=0;while(!node.empty()){level++;int size=node.size();for(int i=0,x,y,nx,ny;i<size;i++){x=node.front().first;y=node.front().second;node.pop();for(int j=0;j<4;j++)//j=0:上//j=1:下//j=2:左//j=3:右{nx=x+move[j];ny=y+move[j+1];if(nx>=0&&nx<n&&ny>=0&&ny<n&&grid[nx][ny]==0&&!visited[nx][ny]){visited[nx][ny]=true;node.push(make_pair(nx,ny));} }}}return level-1;//到最后还被多加了一次}
};

这个题主要是引入节点向周围找路的方法。

整体思路就是从每个陆地往外进行宽度优先遍历，遇到海就“感染”入队，最后返回层数-1即可。

首先，要遍历每个陆地入队，与此同时还可以顺便统计海洋数量。若全为海或者全为陆地就直接返回。之后进行宽度优先遍历统计level层数，每次从队列里取队列的size个，即当前层的所有节点，然后每个节点向外扩。注意这里向外扩的写法，设置move数组为-1,0,1,0,-1，之后每来到一个位置就让下一步的nx=x+move[j]，ny=y+move[j+1]，这样就能实现向上下左右四个方向扩。当下一步的位置有效时，就记录状态然后入队。

（2）贴纸拼词

class Solution {
public://邻接表建图vector<vector<string>>graph;int minStickers(vector<string>& stickers, string target) {int n=stickers.size();graph.resize(26);//能消目标某字母的字符串//路的展开 -> 用每个贴纸会导致不同的剩余情况for(int i=0;i<n;i++){//排序字符串 -> 只考虑词频和字母sort(stickers[i].begin(),stickers[i].end());//建图for(int j=0;j<stickers[i].length();j++){//统计能消的字符if(j==0||stickers[i][j]!=stickers[i][j-1])//不重复加{graph[stickers[i][j]-'a'].push_back(stickers[i]);}}}//排序sort(target.begin(),target.end());set<string>visited;//剩余字符串去重queue<string>node;visited.insert(target);node.push(target);int level=0;while(!node.empty()){level++;int size=node.size();for(int i=0;i<size;i++){string cur=node.front();node.pop();//剪枝 -> 统计前缀 -> 先消前缀for(int j=0;j<graph[cur[0]-'a'].size();j++){//求消完后的字符串string next=findNext(cur,graph[cur[0]-'a'][j]);if(next==""){return level;}else if(visited.find(next)==visited.end())//没进过{visited.insert(next);node.push(next);}}}}return -1;}string findNext(string cur,string s){string next;for(int i=0,j=0;i<cur.length();)//双指针{if(j==s.length())//用完了{next+=cur[i++];}else{if(cur[i]<s[j])//消不完{next+=cur[i++];}else if(cur[i]>s[j])//用不着{j++;}else//能消{i++;j++;}}}return next;}
};

 这个题就很有难度了，最难想的地方就是之前提到过的三点：节点如何找路、路的展开和剪枝。

首先考虑是如何想到用宽度优先遍历的。过程就是在分析题目时可以发现，选择不同的贴纸会消出不同的后续字符串，而这样的结构就可以看作一张图。

对于节点如何找路的问题，因为每用一张贴纸就会消出一条路，所以就是去找能消除当前字符串里字符的所有贴纸。

再就是在路的展开时，需要统计每张贴纸可以消除哪些字符。所以可以建立邻接表，根据每张贴纸能消的所有字符，将这个贴纸加到每个字符对应的表里，之后在消除时只需要去能消这些字符的表里选即可。

然后就是剪枝，观察可以发现，在消的过程中每个字符的相对次序并不重要，重要的是每个字符的个数。所以可以考虑将字符串排序，只保留词频信息。还有，排序后可以发现，当前节点其实可以不用展开全部的路，因为每个字符都需要消除，且现在已经有序，所以只需要按照顺序依次消除，即每次展开时只找能消当前字符前缀字符的贴纸即可。

之后就是细节部分，首先是统计所有贴纸能消的字符，需要遍历字符串，为了避免重复加入，所以相同的字符只加一次。之后进行宽度优先遍历，设置一个set去重，然后每次只根据当前字符串的前缀字符去邻接表里找所有能消前缀字符的贴纸，之后去展开。在展开时，需要找到消完之后的字符串，那么就要用到findNext函数。方法就是用双指针遍历当前字符串和贴纸，若贴纸用完了，就把后面剩下的字符串全加上；否则，即没用完时，若当前的字符比贴纸的小，说明字符串里的这种字符消不完，就加到next里；若大于，说明贴纸里的这种字符用不着了，就让贴纸的指针往下跳；否则就说明能消除。

真的难啊……

（3）为高尔夫比赛砍树

class Solution {
public:vector<int>move={-1,0,1,0,-1};int cutOffTree(vector<vector<int>>& forest) {int n=forest.size();int m=forest[0].size();vector<pair<int,int>>trees;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(forest[i][j]>1){trees.push_back({i,j});}}}sort(trees.begin(),trees.end(),[&](pair<int,int>&a,pair<int,int>&b){return forest[a.first][a.second]<forest[b.first][b.second];});int ans=0;for(int i=0,x=0,y=0,result;i<trees.size();i++){result=bfs(x,y,trees[i].first,trees[i].second,n,m,forest);if(result==-1){return -1;}ans+=result;x=trees[i].first;y=trees[i].second;}        return ans;}int bfs(int ix,int iy,int fx,int fy,int n,int m,vector<vector<int>>&forest){if(ix==fx&&iy==fy){return 0;}queue<pair<int,int>>node;vector<vector<bool>>visited(n,vector<bool>(m));node.push({ix,iy});visited[ix][iy]=true;int level=0;while(!node.empty()){level++;int size=node.size();for(int i=0;i<size;i++){int x=node.front().first;int y=node.front().second;node.pop();for(int j=0,nx,ny;j<4;j++){nx=x+move[j];ny=y+move[j+1];if(nx==fx&&ny==fy){return level;}if(nx>=0&&nx<n&&ny>=0&&ny<m&&forest[nx][ny]>0&&!visited[nx][ny]){node.push({nx,ny});visited[nx][ny]=true;}}}}return -1;}
};

这个题思路倒不是很难，就是tnnd卡常，节点用vector表示会超时，必须得改成pair才行。

具体思路其实挺简单的，就是根据第一反应去暴力。先遍历找出每棵树，然后把所有树根据高度从小到大排序，然后根据排序后的顺序，每次跑一遍宽度优先遍历bfs求最短路即可。（一开始还担心这个方法时间会超…）

之后没啥好说的了，就是bfs的模板。中间再注意一下特例的处理就行，比如初始点就是树的情况bfs要返回0。

二、01bfs

1.内容

当节点与节点间存在权重，求最短路就不能用宽度优先遍历。此时，若权重要么是0要么是1，那么就可以使用01bfs，否则就得用dijkstra等其他求最短路的算法了。

2.题目

（1）到达角落需要移除障碍物的最小数目

class Solution {
public:vector<int>move={-1,0,1,0,-1};int minimumObstacles(vector<vector<int>>& grid) {int n=grid.size();int m=grid[0].size();vector<vector<int>>distance(n,vector<int>(m,INT_MAX));//初始无穷大deque<vector<int>>node;node.push_front({0,0});distance[0][0]=0;while(!node.empty()){vector<int>cur=node.front();//每次从头部弹出node.pop_front();int x=cur[0];int y=cur[1];if(x==n-1&&y==m-1)//到终点{return distance[x][y];}for(int i=0,nx,ny;i<4;i++){nx=x+move[i];ny=y+move[i+1];if(nx>=0&&nx<n&&ny>=0&&ny<m&&distance[x][y]+grid[nx][ny]<distance[nx][ny])//可以让去这个点的代价更小{distance[nx][ny]=distance[x][y]+grid[nx][ny];//更新if(grid[nx][ny]==0){node.push_front({nx,ny});//头入}else{node.push_back({nx,ny});//尾入}}}}   return -1;}
};

观察发现，这个题完全符合上面对01bfs的描述，所以直接跑一遍01bfs就行。

01bfs的具体方法是，设置一个distance数组存从起点到每个点的最短距离，初始每个都为无穷大。然后设置一个双端队列存节点，初始加入起点并将起点的distance设置为0。之后只要队列不为空，每次取头部节点弹出，若到了终点就直接返回，否则去周围四个点，若当前点的distance加上去往下一个点的代价小于下一个点的distance，即能把下一个点的距离变得更小，就更新下一个点的distance为当前点加代价，之后若代价为0就从头部入队，代价为1就从尾部入队。

（2）使网格图至少有一条有效路径的最小代价

class Solution {
public:vector<vector<int>>move={{},{0,1},{0,-1},{1,0},{-1,0}};int minCost(vector<vector<int>>& grid) {int n=grid.size();int m=grid[0].size();vector<vector<int>>distance(n,vector<int>(m,INT_MAX));deque<vector<int>>node;node.push_front({0,0});distance[0][0]=0;while(!node.empty()){vector<int>cur=node.front();node.pop_front();int x=cur[0];int y=cur[1];if(x==n-1&&y==m-1){return distance[x][y];}for(int i=1,nx,ny,cost;i<=4;i++){nx=x+move[i][0];ny=y+move[i][1];cost=nx!=x+move[grid[x][y]][0]||ny!=y+move[grid[x][y]][1];if(nx>=0&&nx<n&&ny>=0&&ny<m&&distance[nx][ny]>distance[x][y]+cost){distance[nx][ny]=distance[x][y]+cost;if(cost==0){node.push_front({nx,ny});}else{node.push_back({nx,ny});}}}}return -1;}
};

这个题主要是需要转化一下，当来到每个格子，若下一步往箭头方向走，代价就是0；若往非箭头方向走，代价就是1。

转化完就是01bfs的模板了，没啥好说的。

三、宽度优先遍历与堆——接雨水 II

class Solution {
public:vector<int>move={-1,0,1,0,-1};static bool cmp(vector<int>&a,vector<int>&b){return a[2]>b[2];}int trapRainWater(vector<vector<int>>& heightMap) {int n=heightMap.size();int m=heightMap[0].size();//小根堆priority_queue<vector<int>,vector<vector<int>>,decltype(&cmp)>heap(cmp);vector<vector<bool>>visited(n,vector<bool>(m,false));//先入外围一圈for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(i==0||i==n-1||j==0||j==m-1){heap.push({i,j,heightMap[i][j]});//存水线高度visited[i][j]=true;}}}//宽度优先遍历int ans=0;while(!heap.empty()){vector<int>cur=heap.top();heap.pop();int x=cur[0];int y=cur[1];int h=cur[2];//水线高度！！ans+=h-heightMap[x][y];for(int i=0,nx,ny;i<4;i++){nx=x+move[i];ny=y+move[i+1];if(nx>=0&&nx<n&&ny>=0&&ny<m&&!visited[nx][ny]){//水线高度=max(格子高度，当前点水线高度)heap.push({nx,ny,max(heightMap[nx][ny],h)});visited[nx][ny]=true;}}}return ans;}
};

这个题确实有点小恶心，但想到思路之后的coding还是不难的。

首先，因为能盛的水量主要取决于周围一圈水线最低的格子，所以考虑从外向内扩，每次统计下一个格子的水线。因为每次考虑的都是水线最低的格子，所以这里使用一个小根堆存位置和水线。之后，先让外面一圈入堆，由于在最外层，所以它们的水线就是自己的高度，即盛不了水。然后每次从水线最小的格子考虑，取出即统计答案，即水线减去自己的高度。这里，水线就是自己高度和上一格水线高度的最大值，因为若自己的高度比上一格的水线小，那么之后格子依然依赖上一格的水线，若自己高度比上一格的水线大，那么之后的格子就可以盛更多的水。

这个从外到内和更新水线的思路真不好想……

四、bfs和dfs结合——单词接龙 II

class Solution {
public:vector<vector<string>>ans;vector<string>path;//建反图 -> a能由谁生成map<string,vector<string>>graph;//将单词表转化成setset<string>words;//每一层去重set<string>curLevel;set<string>nextLevel;vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {words={wordList.begin(),wordList.end()};if(words.find(endWord)==words.end())//没有endWord{return ans;}if(bfs(beginWord,endWord)){//反向搜生成路径dfs(endWord,beginWord);}return ans;}//建图，返回是否存在bool bfs(string beginWord,string endWord){bool find=false;curLevel.insert(beginWord);while(!curLevel.empty()){//单词表删当前层，去重for(auto iter=curLevel.begin();iter!=curLevel.end();iter++){words.erase(*iter);}//当前层生成路for(string word:curLevel){//每个位置字符从a到z换一遍，检查是否存在for(int i=0;i<word.length();i++){string old=word;for(char ch='a';ch<='z';ch++){word[i]=ch;if(words.find(word)!=words.end())//词表中有{if(word==endWord)//找到了{find=true;}graph[word].push_back(old);nextLevel.insert(word);}}word=old;}}if(find){return true;}else{curLevel=nextLevel;nextLevel.clear();}}return false;}void dfs(string endWord,string beginWord){//反搜 -> 头插path.insert(path.begin(),endWord);if(endWord==beginWord)//找到了{ans.push_back(path);}else{for(string next:graph[endWord]){dfs(next,beginWord);}}path.erase(path.begin());}
};

这个题的思路有点过于逆天了，初见肯定得超时几次才能改得出来……

首先，分析题目可以发现，当前字符串根据改法的不同会展开不同的路，所以整体思路是用宽度优先遍历建图，然后找最短路。那么再进一步想，因为展开的路会有很多，但其中肯定大部分都走不到终点，是无效的路，所以为了加快找路的速度，可以使用深度优先搜索dfs，从终点开始往起点搜，这样就能避免走“死胡同”。再进一步考虑，为了实现反向dfs，所以在建图时要建反图，即让产生的新字符串指向旧字符串。

首先是bfs，为了实现去重，所以设置curLevel和nextLevel两个set，curLevel充当队列。之后首先往里加入初始字符串，然后每到一层，为了让路径最短，不走回头路，所以要让总词表减去curLevel的词，之后遍历当前层的所有情况去生成路，这里，若去遍历词表里的每个字符串，然后一个字符一个字符比对的话时间复杂度就太高了，所以考虑遍历当前字符的每个位置，让每个位置从a到z换一遍，然后去词表里找有没有，那么可以直接将词表转成一个set。若找到了就更新find，之后建图并往nextLevel里加入。遍历完所有位置，若找到了就直接返回，否则让curLevel来到nextLevel准备下一层。这里不能找到了就直接返回，会漏掉其他可能性。

再就是dfs建路了，因为是反搜，所以每次往path的开头插入。若找到了就往ans里加，没找到就遍历下一层的所有情况去递归，最后在回来时还要还原现场。

总结

太难了……

END