企业官网建设流程全解析

深度优先搜索理论基础：

dfs 与 bfs 区别

• dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
• bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

dfs搜索过程：

关键就两点：

• 搜索方向，是认准一个方向搜，直到碰壁之后再换方向
• 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。

代码框架：

正是因为dfs搜索可一个方向，并需要回溯，所以用递归的方式来实现是最方便的。

有递归的地方就有回溯，那么回溯在哪里呢？

就递归函数的下面，例如如下代码：

voiddfs(参数){处理节点dfs(图，选择的节点);// 递归回溯，撤销处理结果}

可以看到回溯操作就在递归函数的下面，递归和回溯是相辅相成的。

在讲解二叉树章节的时候，二叉树的递归法其实就是dfs，而二叉树的迭代法，就是bfs（广度优先搜索）

所以dfs，bfs其实是基础搜索算法，也广泛应用与其他数据结构与算法中。

再回顾一下回溯法的代码框架：

voidbacktracking(参数){if(终止条件){存放结果;return;}for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){处理节点;backtracking(路径，选择列表);// 递归回溯，撤销处理结果}}

回溯算法，其实就是dfs的过程，以下给出dfs的代码框架：

voiddfs(参数){if(终止条件){存放结果;return;}for(选择：本节点所连接的其他节点){处理节点;dfs(图，选择的节点);// 递归回溯，撤销处理结果}}

可以发现dfs的代码框架和回溯算法的代码框架是差不多的。

以下再用深搜三部曲，来解读 dfs的代码框架。

dfs三部曲

1. 确认递归函数，参数

voiddfs(参数)

通常我们递归的时候，我们递归搜索需要了解哪些参数，其实也可以在写递归函数的时候，发现需要什么参数，再去补充就可以。

一般情况，深搜需要二维数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。

例如这样：

vector<vector<int>>result;// 保存符合条件的所有路径vector<int>path;// 起点到终点的路径voiddfs(图，目前搜索的节点)

但这种写法看个人习惯，不强求。

2. 确认终止条件

终止条件很重要，很多时候写dfs的时候，之所以容易死循环，栈溢出等等这些问题，都是因为终止条件没有想清楚。

if(终止条件){存放结果;return;}

终止添加不仅是结束本层递归，同时也是我们收获结果的时候。

另外，其实很多dfs写法，没有写终止条件，是因为终止条件写在了隐藏在下面dfs递归的逻辑里了，也就是如果不符合条件，直接不会向下递归。后面会有具体题目来讲解。

3. 处理目前搜索节点出发的路径

一般这里就是一个for循环的操作，去遍历 目前搜索节点 所能到的所有节点。

for(选择：本节点所连接的其他节点){处理节点;dfs(图，选择的节点);// 递归回溯，撤销处理结果}

那为什么都是 dfs代码框架中for循环里分明已经处理节点了，dfs函数下面还要撤销呢。

如下图所示，路径2已经走到了目的地节点6，那么路径2是如何撤销，然后改为路径3呢？ 其实这就是回溯的过程，撤销路径2，换下一个方向。

【98.可达路径】

图的存储方式：

邻接矩阵

邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。

本题我们会有n 个节点，因为节点标号是从1开始的，为了节点标号和下标对齐，我们申请 n + 1 * n + 1 这么大的二维数组。

vector<vector<int>>graph(n+1,vector<int>(n+1,0));

输入m个边，构造方式如下：

while(m--){cin>>s>>t;// 使用邻接矩阵 ，1 表示 节点s 指向 节点tgraph[s][t]=1;}

邻接表

邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。

邻接表的构造相对邻接矩阵难理解一些。

以下图为例：

这里表达的图是：

• 节点1 指向 节点3 和 节点5
• 节点2 指向 节点4、节点3、节点5
• 节点3 指向 节点4
• 节点4指向节点1

我们需要构造一个数组，数组里的元素是一个链表。

C++写法：

// 节点编号从1到n，所以申请 n+1 这么大的数组vector<list<int>>graph(n+1);// 邻接表，list为C++里的链表

输入m个边，构造方式如下：

while(m--){cin>>s>>t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);}

本题我们使用邻接表 或者 邻接矩阵都可以，因为后台数据并没有对图的大小以及稠密度做很大的区分。

以下我们使用邻接矩阵的方式来讲解，文末也会给出 使用邻接表的整体代码。

注意邻接表 和 邻接矩阵的写法都要掌握！

// 邻接矩阵写法#include<iostream>#include<vector>usingnamespacestd;vector<vector<int>>result;// 收集符合条件的路径vector<int>path;// 1节点到终点的路径// x：目前遍历的节点// graph：存当前的图// n：终点voiddfs(constvector<vector<int>>&graph,intx,intn){if(x==n){result.push_back(path);return;}for(inti=1;i<=n;i++){// 遍历节点x链接的所有节点if(graph[x][i]==1){// 找到x链接的节点ipath.push_back(i);// 将i放入path中dfs(graph,i,n);// 进行dfspath.pop_back();// 回溯，撤销本节点}}}intmain(){intn,m,s,t;cin>>n>>m;// 节点编号从1-n，所以申请n+1这么大的二维数组vector<vector<int>>graph(n+1,vector<int>(n+1,0));while(m--){cin>>s>>t;// 使用邻接矩阵 表示无向图，1 表示 s 与 t 是相连的graph[s][t]=1;}path.push_back(1);dfs(graph,1,n);if(result.size()==0)cout<<-1<<endl;for(constvector<int>&pa:result){for(inti=0;i<pa.size()-1;i++){cout<<pa[i]<<" ";}cout<<pa[pa.size()-1]<<endl;}}

// 邻接矩阵写法#include<iostream>#include<vector>#include<list>usingnamespacestd;vector<vector<int>>result;// 收集符合条件的路径vector<int>path;// 1节点到终点的路径// x：目前遍历的节点// graph：存当前的图// n：终点voiddfs(constvector<list<int>>&graph,intx,intn){if(x==n){result.push_back(path);return;}for(inti:graph[x]){// 遍历节点x链接的所有节点ipath.push_back(i);// 将i加入path中dfs(graph,i,n);// 进入下一层递归path.pop_back();// 回溯， 撤销本节点}}intmain(){intn,m,s,t;cin>>n>>m;// 节点编号从1-n，所以申请n+1这么大的数组vector<list<int>>graph(n+1);while(m--){cin>>s>>t;// 使用邻接表表示无向图graph[s].push_back(t);}path.push_back(1);dfs(graph,1,n);if(result.size()==0)cout<<-1<<endl;for(constvector<int>&pa:result){for(inti=0;i<pa.size()-1;i++){cout<<pa[i]<<" ";}cout<<pa[pa.size()-1]<<endl;}}

广度优先搜索理论基础：

广搜（bfs）是一圈一圈的搜索过程，和深搜（dfs）是一条路跑到黑然后再回溯。

广搜的使用场景

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

当然，也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。 （我们会在具体题目讲解中详细来说）

广搜的过程

上面我们提过，BFS是一圈一圈的搜索过程，但具体是怎么一圈一圈来搜呢。

我们用一个方格地图，假如每次搜索的方向为 上下左右（不包含斜上方），那么给出一个start起始位置，那么BFS就是从四个方向走出第一步。

如果加上一个end终止位置，那么使用BFS的搜索过程如图所示：

从图中可以看出，从start起点开始，是一圈一圈，向外搜索，方格编号1为第一步遍历的节点，方格编号2为第二步遍历的节点，第四步的时候我们找到终止点end。

正是因为BFS一圈一圈的遍历方式，所以一旦遇到终止点，那么一定是一条最短路径。

而且地图还可以有障碍，如图所示：

在第五步，第六步 只把关键的节点染色了，其他方向周边没有去染色，大家只要关注关键地方染色的逻辑就可以。

从图中可以看出，如果添加了障碍，我们是第六步才能走到end终点。

只要BFS只要搜到终点一定是一条最短路径，大家可以参考上面的图，自己再去模拟一下。

代码框架

大家应该好奇，这一圈一圈的搜索过程是怎么做到的，是放在什么容器里，才能这样去遍历。

很多网上的资料都是直接说用队列来实现。

其实，我们仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。

用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。

• 「统一顺时针 / 逆时针」只是遍历邻居的统一习惯，不是 BFS 必须遵守的规则；

• 只有你需要沿着图形边缘连续绕圈时，才强制要求方向顺序。

• 所以建议直接统一顺时针/逆时针遍历，是更通用的写法

因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。

如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。

因为栈是先进后出，加入元素和弹出元素的顺序改变了。

那么广搜需要注意 转圈搜索的顺序吗？ 不需要！

所以用队列，还是用栈都是可以的，但还是用习惯的队列来说，只不过大家要清楚，并不是非要用队列，用栈也可以。

下面给出广搜代码模板，该模板针对的就是，上面的四方格的地图：

intdir[4][2]={0,1,1,0,0,-1,-1,0};// 表示四个方向// grid 是地图，也就是一个二维数组// visited标记访问过的节点，不要重复访问// x,y 表示开始搜索节点的下标voidbfs(vector<vector<char>>&grid,vector<vector<bool>>&visited,intx,inty){queue<pair<int,int>>que;// 定义队列que.push({x,y});// 起始节点加入队列visited[x][y]=true;// 只要加入队列，立刻标记为访问过的节点while(!que.empty()){// 开始遍历队列里的元素pair<int,int>cur=que.front();que.pop();// 从队列取元素intcurx=cur.first;intcury=cur.second;// 当前节点坐标for(inti=0;i<4;i++){// 开始向当前节点的四个方向右、下、左、上去遍历intnextx=curx+dir[i][0];intnexty=cury+dir[i][1];// 获取周边四个方向的坐标if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;// 坐标越界了，直接跳过if(!visited[nextx][nexty]){// 如果节点没被访问过que.push({nextx,nexty});// 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty]=true;// 只要加入队列立刻标记，避免重复访问}}}}