新公司做网站有效果吗,微信小程序成本,深圳设计网站建设公司,西安网站建设推广代码随想录Day66 | 图的DFS与BFS DFS797.所有可能的路径无向图和有向图的处理 BFS200.岛屿数量 DFS 文档讲解#xff1a;代码随想录 视频讲解#xff1a; 状态 本质上就是回溯算法。
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择#xff1a;本节点所连接的… 代码随想录Day66 | 图的DFS与BFS DFS797.所有可能的路径无向图和有向图的处理 BFS200.岛屿数量 DFS 文档讲解代码随想录 视频讲解 状态 本质上就是回溯算法。
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果}
}797.所有可能的路径 文档讲解代码随想录 视频讲解 状态 dfs搜索路径即可。 终止条件为当当前搜索点的下标为n-1时。
class Solution {
private:vectorvectorint res;vectorint path;
public:void dfs(int index,vectorvectorint graph){if(index graph.size()-1){res.push_back(path);return;}for(auto i : graph[index]){path.push_back(i);dfs(i,graph);path.pop_back();}}
public:vectorvectorint allPathsSourceTarget(vectorvectorint graph) {path.push_back(0);dfs(0,graph);return res;}
};无向图和有向图的处理
无向图在dfs的时候需要考虑后续节点的连通会与父节点连接所以dfs参数中需要加上一个父节点
void dfs(int n,int fa)
{for(int y : graph[n]){if(y ! fa){dfs();}}
}BFS 文档讲解代码随想录 视频讲解 状态 从出发点一圈一圈的搜索需要使用数据结构来存储遍历的数据可以是有队列或者栈。 以队列为例
//定义移动方向只能上下左右 不能对角线移动
vectorint dir {0,1,1,0,-1,0,0,-1}
// grid 是地图也就是一个二维数组
// visited标记访问过的节点不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {queuepairint, int que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] true; // 只要加入队列立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pairint ,int cur que.front(); que.pop(); // 从队列取元素int curx cur.first;int cury cur.second; // 当前节点坐标for (int i 0; i 4; i) { // 开始想当前节点的四个方向左右上下去遍历int nextx curx dir[i][0];int nexty 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; // 只要加入队列立刻标记避免重复访问}}}
}一定要注意当点加入队列就需要立刻标记否则会重复访问
200.岛屿数量
本题可以很好的练习了解BFS
class Solution {
private://搜寻方向 上下左右int dir[4][2] {0,1,1,0,-1,0,0,-1};
public://bfs//grid 地图//visited 记录访问过的节点//x,y遍历起点坐标void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y){//队列queuepairint,int que;que.push({x,y});visited[x][y] true;//开始BFSwhile(!que.empty()){pairint,int cur que.front();que.pop();int curx cur.first;int cury cur.second;for(int i0;i4;i){int nextx curx dir[i][0];int nexty cury dir[i][1];if(nextx 0 || nextx grid.size() || nexty0 || nexty grid[0].size()) continue;if(!visited[nextx][nexty] grid[nextx][nexty] 1){que.push({nextx,nexty});visited[nextx][nexty] true;}}}}
public:int numIslands(vectorvectorchar grid) {int n grid.size();int m grid[0].size();vectorvectorbool visited vectorvectorbool(n,vectorbool(m,false));int res 0;//对每个岛屿进行遍历搜寻四周岛屿for(int i 0;in;i){for(int j 0;jm;j){if(!visited[i][j] grid[i][j] 1){res;bfs(grid,visited,i,j);}}}return res;}
};
