网站建设厘金手指排名二一,河南海华工程建设监理公司网站,广州专业的网站建设,长沙网络科技公司✨博主#xff1a;命运之光 ✨专栏#xff1a;算法基础学习 目录
DFS与BFS\树与图
✨DFS
✨BFS
#x1f353;宽搜流程图如下#xff1a;
#x1f353;宽搜流程#xff1a;
#x1f353;广搜模板
✨树与图
#x1f353;树是特殊的图#xff08;连通无环的图命运之光 ✨专栏算法基础学习 目录
DFS与BFS\树与图
✨DFS
✨BFS
宽搜流程图如下
宽搜流程
广搜模板
✨树与图
树是特殊的图连通无环的图
树与图的存储
用宽搜框架来搜索图 前言算法学习笔记记录日常分享需要的看哈O(∩_∩)O感谢大家的支持 DFS与BFS\树与图 ✨DFS
//回溯剪枝
当使用深度优先搜索DFS回溯算法来搜索图时我们需要考虑以下几个步骤
初始化数据结构创建一个栈通常使用先进后出的原则来存储待探索的节点以及一个集合通常使用哈希集合或集合来记录已访问的节点。将起始节点放入栈中并将其标记为已访问。进入循环直到栈为空 从栈中取出一个节点。检查该节点是否为目标节点。如果是则搜索完成返回结果。如果不是目标节点则将其所有未访问过的邻居节点加入栈并标记为已访问。继续下一轮循环。
如果循环结束时仍未找到目标节点则图中不存在目标节点。 剪枝可以提前判断当前方案一定不合法就不用往下搜
✨BFS 宽搜流程图如下 宽搜流程 广搜模板
q.push(初始状态);
while(q.empty()){aq.front();q.pop();for(枚举a的所有可达状态v){if(本状态v合法){执行标记操作;q.push(v);}}
} 连通块问题
例题全球变暖
#includeiostream
#includequeue
#includecstring
using namespace std;
const int N1005;
bool v[N][N],book[N*N];
char a[N][N];
int n,w[N][N],s,cnt;
int dx[4]{-1,0,1,0};
int dy[4]{0,1,0,-1};
typedef struct node
{int x,y;
}node;
queuenodeq;
bool check(int x,int y)
{if(x1||xn||y1||yn)return false;return true;
}
bool judge(int x,int y)
{if(check(x1,y)a[x1][y].)return false;if(check(x,y1)a[x][y1].)return false;if(check(x-1,y)a[x-1][y].)return false;if(check(x,y-1)a[x][y-1].)return false;return true;
}
void bfs()
{while(!q.empty()){node head,tail;headq.front();q.pop();for(int i0;i4;i){tail.xhead.xdx[i];tail.yhead.ydy[i];if(check(tail.x,tail.y)a[tail.x][tail.y]#w[tail.x][tail.y]0){w[tail.x][tail.y]cnt;q.push(tail);}}}
}
int main()
{cinn;for(int i1;in;i){for(int j1;jn;j){cina[i][j];}}for(int i1;in;i){for(int j1;jn;j){if(a[i][j]#w[i][j]0){cnt;w[i][j]cnt;node tmp{i,j};q.push(tmp);bfs();}}}for(int i1;in;i){for(int j1;jn;j){if(a[i][j]#){if(judge(i,j)){book[w[i][j]]true;}}}}for(int i1;icnt;i){if(book[i]true){s;}}coutcnt-s;return 0;
}
问题2
两个BFS
例题Fire
/*
预处理预处理出火传染到(i,j)点的最早时间
人在去想要走到(i,j)点时到(i,j)点的时刻一定要小于火最早到(i,j)的s时刻
*/
#include iostream
#include queue
#include cstring
using namespace std;
const int N10005;
const int INF0x3f3f3f3f;
typedef struct Node{int x,y;int t;
}Node;
int t,n,m;
int ti[N][N];//ti[i][j]是火最早到(i,j)的时间
char a[N][N];
queueNode fq,q;
bool vis[N][N];
int _next[4][2]{{-1,0},{0,1},{1,0},{0,-1}};
bool judge(int x,int y)
{if(x1||xn||y1||ym)return false;return true;
}
void FireBFS()
{Node _new;while(!fq.empty()){Node tpfq.front();fq.pop();for(int i0;i4;i){_new.xtp.x_next[i][0];_new.ytp.y_next[i][1];if(judge(_new.x,_new.y)a[_new.x][_new.y].ti[_new.x][_new.y]INF){_new.ttp.t1;ti[_new.x][_new.y]_new.t;fq.push(_new);}}}
}
int ManBFS(){Node _new;while(!q.empty()){Node tpq.front();q.pop();if(tp.x1||tp.xn||tp.y1||tp.ym){return tp.t1;}for(int i0;i4;i){_new.xtp.x_next[i][0];_new.ytp.y_next[i][1];if(judge(_new.x,_new.y)a[_new.x][_new.y].!vis[_new.x][_new.y]){_new.ttp.t1;if(_new.tti[_new.x][_new.y]){vis[_new.x][_new.y]true;q.push(_new);}}}}return -1;
}
void init(){memset(ti,0x3f,sizeof(ti));memset(vis,false,sizeof(vis));while(!fq.empty())fq.pop();while(!q.empty())q.pop();
}
int main(){cint;while(t--){init();cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];if(a[i][j]F){Node tmp{i,j,0};ti[i][j]0;fq.push(tmp);}else if(a[i][j]J){Node tmp{i,j,0};vis[i][j]true;q.push(tmp);}}}FireBFS();int ansManBFS();if(ans-1)coutIMPOSSIBLEendl;elsecoutansendl;}
}
/*
2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F
*/
✨树与图
树是特殊的图连通无环的图 树与图的存储 树是一种特殊的图与图的存储方式相同。 对于无向图中的边ab存储两条有向边a-b, b-a。 因此我们可以只考虑有向图的存储。 (1) 邻接矩阵g[a][b] 存储边a-b
(2) 邻接表
// 对于每个点k开一个单链表存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a-b
void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx ;
}
// 初始化
idx 0;
memset(h, -1, sizeof h);
树与图的遍历
时间复杂度 O(nm)O(nm), nn 表示点数mm 表示边数
(1) 深度优先遍历 int dfs(int u)
{st[u] true; // st[u] 表示点u已经被遍历过for (int i h[u]; i ! -1; i ne[i]){int j e[i];if (!st[j]) dfs(j);}
}
(2) 宽度优先遍历 queueint q;
st[1] true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{int t q.front();q.pop();for (int i h[t]; i ! -1; i ne[i]){int j e[i];if (!st[j]){st[j] true; // 表示点j已经被遍历过q.push(j);}}
}
用宽搜框架来搜索图 当使用宽度优先搜索BFS框架搜索图时我们可以按照以下步骤进行操作
选择一个起始节点并将其添加到队列中同时将其标记为已访问。重复以下步骤直到队列为空 从队列中取出一个节点作为当前节点。检查当前节点是否满足搜索条件。如果是则返回结果或执行相应操作。遍历当前节点的所有相邻节点。对于每个未被访问的相邻节点将其添加到队列中并将其标记为已访问。
如果队列为空且没有找到满足条件的节点则搜索结束可以返回相应的结果或执行其他操作。
以下是使用宽度优先搜索框架在C中搜索图的示例代码
#include iostream
#include queue
#include unordered_set
#include unordered_map
#include vector
bool bfs(const std::unordered_mapchar, std::vectorchar graph, char startNode, char targetNode) {std::queuechar queue; // 创建一个队列std::unordered_setchar visited; // 创建一个集合用于记录已访问的节点queue.push(startNode); // 将起始节点放入队列visited.insert(startNode); // 标记起始节点为已访问while (!queue.empty()) {char node queue.front(); // 从队列中取出一个节点queue.pop();if (node targetNode) // 检查是否为目标节点return true;const std::vectorchar neighbors graph.at(node); // 获取当前节点的邻居节点for (char neighbor : neighbors) {if (visited.find(neighbor) visited.end()) { // 如果邻居节点未被访问过queue.push(neighbor); // 将邻居节点加入队列visited.insert(neighbor); // 标记邻居节点为已访问}}}return false; // 循环结束未找到目标节点
}
int main() {std::unordered_mapchar, std::vectorchar graph {{A, {B, C}},{B, {D, E}},{C, {F}},{D, {}},{E, {F}},{F, {}}};char startNode A;char targetNode F;bool result bfs(graph, startNode, targetNode);if (result)std::cout The target node targetNode is reachable from the start node startNode .\n;elsestd::cout The target node targetNode is not reachable from the start node startNode .\n;return 0;
} 在上述代码中使用std::unordered_map来表示图的邻接表其中键是节点值是该节点的邻居节点列表。还使用std::queue来作为队列存储待探索的节点std::unordered_set用于记录已访问的节点。 注意上述代码仅为示例假设图中的节点标识为字符A, B, C等您可以根据实际情况进行修改和适应。
