。

而前、中、后序遍历则是DFS#xff08;深度优先搜索#xff09;。

从字面意思也很好理解#xff0c;DFS就是一条路走到黑#xff0c;BFS则是一层一层地展开。

…

BFS也就是广度宽度优先搜索二叉树的层序遍历就是一个BFS的过程。

而前、中、后序遍历则是DFS深度优先搜索。

从字面意思也很好理解DFS就是一条路走到黑BFS则是一层一层地展开。

一、层序遍历

N叉树与二叉树的区别无非就是二叉树最多只有两个子节点用left和right两个指针就够储存。

而N叉树有N多个节点需要一个指针数组来储存。

在用BFS解决问题时几乎都要借助队列结构用队列的先进先出特性来储存上一层的数据。

首先把根节点放到队列里面然后从队列里面取节点出来把节点取出来后通过它找到它的子节点并带入到队列里面。

那么这个节点的使命就算完成了需要把它踢出队列。

循环往复直到最后队列为空则完成层序遍历。

但对于这个题并不是简单的层序遍历就行它还要把每一层划分出来。

这个其实也很简单只要记录每一层有几个节点记为n个然后一次性的遍历n个并把这n个元素用数组储存起来。

可以直接使用size()计算该层元素个数。

代码示例

qu;qu.push(root);while(!qu.empty()){vectorint

arr;int

nqu.size();//获取该层有一个元素while(n--)//取出该层的所以元素并把子节点带入{Node*

rtqu.front();qu.pop();arr.push_back(rt-val);for(int

i0;irt-children.size();i)qu.push(rt-children[i]);}if(!arr.empty())

ret.push_back(arr);}

dx[4]{0,0,-1,1}dy[4]{-1,1,0,0};

我们使用

它的扩展逻辑就和上文层序遍历中那一题差不多但需要一个变量记录层数。

在扩展过程中需要判断是否是目标值还需要把扩展到的元素做标记。

代码示例

dx[4]{0,0,-1,1},dy[4]{-1,1,0,0};int

maze,

maze[0].size();vectorvectorbool

hash(n,vectorbool(m));//记录是否已经搜索过queuepairint,int

qu;qu.push({entrance[0],entrance[1]});hash[entrance[0]][entrance[1]]

true;int

0;//记录层数while(!qu.empty()){ret;int

[a,b]

bdy[k];if(x0xny0ym!hash[x][y]maze[x][y].){if(x0||xn-1||y0||ym-1)

return

这个题我们可以做一个多趟的BFS首先确定第一个起点和终点进行BFS搜索并记录路径长度。

注意由题可知没有两棵树的高度是相同的也就是说树的高度和它的坐标是一一对应的。

具体操作如下

把所有树的高度1的元素都记录到一个数组中然后对该数组进行排序。

这样我们就知道搜索的先后顺序。

bfs(int

forest)传入起点坐标与终点的值它的作用是记录起点到终点的最短距离然后返回终点的坐标。

如果不能被搜索到返回{-1

进行一次bfs后得到的返回值作为下一次搜索的起点下标而终点值从刚才排序好的数组中取到。

class

arr.push_back(forest[i][j]);sort(arr.begin(),arr.end());int

0,y

i0;iarr.size();i){if(i0arr[i]forest[0][0])

continue;auto

hash(m,vectorbool(n));queuepairint,int

true;while(!qu.empty()){ret;int

[a,b]

bdy[k];if(x10x1my10y1n!hash[x1][y1]forest[x1][y1]!0){if(forest[x1][y1]target)

return

{x1,y1};hash[x1][y1]true;qu.push({x1,y1});}}}}return

{-1,-1};}

多源最短路它的特点就是可以选择多个起点找出到达终点的最短路径。

其实它和单源最短路差别并不是很大我们只需要把所有起点看作一个整体也就是把它当作“超级源点”那么它就是一个单源最短路问题。

这个题很明显我们可以使用BFS解决但是如果每个1的位置都用一次BFS搜索未免也太麻烦那么我们可以用多源最短路的思想把所有0当作起点然后去搜索1并填充最短路径。

那么为什么不用所有的1为起点去搜索0呢因为我们需要填写的信息是1的位置如果用1去搜索0的话最后就不能找到原来那个1的位置。

代码示例

dx[4]{0,0,1,-1},dy[4]{1,-1,0,0};vectorvectorint

mat){int

mmat.size(),nmat[0].size();vectorvectorint

ret(m,vectorint(n,-1));//充当了哈希表的功能queuepairint,int

q;for(int

j0;jn;j){if(mat[i][j]0){q.push({i,j});ret[i][j]0;}}}int

tmp

xdx[k]i,ydy[k]j;if(x0xmy0ynret[x][y]-1){ret[x][y]tmp;q.push({x,y});}}}}return

ret;}

通常用顶点来表示一个活动用边的指向来表示活动之间的先后顺序。

如

排序方法

1.记录每个顶点的入度边个数和出度边的指向。

2.把所有入度边为0的节顶点push到队列中。

3.拿出队头元素加入到结果中。

4.把该元素指向的所有顶点入度边减1并判断如果有顶点的入度边为0则push到队列。

循环执行3,4部直到队列为空则完成排序。

210.

i0;iprerequisites.size();i){int

bprerequisites[i][1];in[a];out[b].push_back(a);}

queueint

q.push(i);while(!q.empty()){int

q.front();ret.push_back(v);q.pop();for(int

i0;iout[v].size();i)if(--in[out[v][i]]0)

q.push(out[v][i]);}if(ret.size()!numCourses)

return