邢台网站招聘员工123,做网站用什么网最好,网站点击量作用,网站开发流程及进度安排[算法日志]图论#xff1a; 广度优先搜索(BFS)
广度优先概论
广度优先遍历也是一种常用的遍历图的算法策略#xff0c;其思想是将本节点相关联的节点都遍历一遍后才切换到相关联节点重复本操作。这种遍历方式类似于对二叉树节点的层序遍历#xff0c;即先遍历完子节点后…[算法日志]图论 广度优先搜索(BFS)
广度优先概论
广度优先遍历也是一种常用的遍历图的算法策略其思想是将本节点相关联的节点都遍历一遍后才切换到相关联节点重复本操作。这种遍历方式类似于对二叉树节点的层序遍历即先遍历完子节点后再去遍历子节点的各个子节点。
代码框架
int dir[4][2] {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; // 只要加入队列立刻标记避免重复访问}}}
}通过队列辅助进行迭代操作是BFS的常用遍历手段(当然也可以使用栈)而除了会额外使用一个visited数组辅助进行路径判断其他的步骤都可以照搬二叉树的层序遍历。
BFS的简单应用
leetcode 200(岛屿数量)
BFS示例代码 const int dir[4][2] { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };void BFS(const vectorvectorchar g, vectorvectorbool v, queuepairint,int h){while (!h.empty()){int X h.front().first;int Y h.front().second;h.pop();for (int i 0; i 4; i){int nextX X dir[i][0];int nextY Y dir[i][1];if (nextX 0 || nextY 0 || nextX g[0].size() || nextY g.size())continue;if (!v[nextY][nextX] g[nextY][nextX] 1){v[nextY][nextX] true;h.push(pairint, int(nextX, nextY));}}}return;}int numIslands(const vectorvectorchar gird){if (gird.empty())return 0;vectorvectorbool visited(gird.size(), vectorbool(gird[0].size(), false));queuepairint, int help;int count 0;for (int i 0; i gird.size(); i)for (int j 0; j gird[0].size(); j){if (!visited[i][j] gird[i][j] 1){count;help.push({j, i});visited[i][j] true;BFS(gird, visited, help); }}return count;}当然对于这种岛屿问题并没有对遍历方式做限制因此自然有DFS解法。 const int dir[4][2] { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };void DFS2(vectorvectorbool v, int c,int depth ,int nextX, int nextY){if (depth 0 (nextX 0 || nextY 0 || nextX v[0].size()|| nextY v.size() || v[nextY][nextX]))return;for(int i nextY; i v.size(); i)for (int j nextX; j v[0].size(); j){if (v[i][j]){if (depth 0)return;continue;}if (depth 0)c;v[i][j] true;for (int k 0; k 4; k){DFS2(v, c, depth 1, j dir[k][0], i dir[k][1]);}}return;}int numIslands1(const vectorvectorchar grid){if (grid.empty())return 0;vectorvectorbool visited(grid.size(), vectorbool(grid[0].size()));int count 0;for (int i 0; i grid.size(); i)for (int j 0; j grid[0].size(); j){if (grid[i][j] 1)visited[i][j] false;elsevisited[i][j] true;}DFS2(visited, count, 0, 0, 0);return count;}
