dp.rar_广度优先_深度优先_深度搜索广度搜索_深度优先搜索与广度优先搜索区别资源-CSDN下载

共2个文件

cpp：1个

rar：1个

版权申诉

93 浏览量 2022-09-24 09:05:41 上传评论收藏 1.05MB RAR 举报

在计算机科学领域，图遍历是解决许多问题的关键技术之一，而深度优先搜索（DFS，Depth First Search）和广度优先搜索（BFS，Breadth First Search）就是两种常用的图遍历算法。这两个算法主要应用于有向图或无向图的遍历，以及寻找路径、判断连通性等问题。 **深度优先搜索**是一种用于遍历或搜索树或图的算法。它沿着树的深度方向进行探索，尽可能深地搜索子树。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。 DFS的实现通常采用递归方式或者使用栈来辅助。在C++中，可以使用以下伪代码表示： ```cpp void DFS(Node* node) { // 访问当前节点 visit(node); // 遍历所有相邻节点 for (Node* neighbor : node->neighbors) { if (!visited(neighbor)) { DFS(neighbor); } } } ``` **广度优先搜索**则是从根节点开始，逐层地搜索图的所有节点。首先访问根节点，然后访问所有与根相邻的节点，再访问这些相邻节点的相邻节点，以此类推，直到访问完所有节点。BFS通常使用队列来辅助实现。在C++中，BFS的基本伪代码如下： ```cpp void BFS(Node* root) { queue<Node*> q; q.push(root); while (!q.empty()) { Node* node = q.front(); q.pop(); // 访问当前节点 visit(node); // 将所有未访问的邻居节点入队 for (Node* neighbor : node->neighbors) { if (!visited(neighbor)) { q.push(neighbor); } } } } ``` 这两个算法各有优缺点。DFS在空间效率上相对较高，因为只需要存储有限个递归调用的栈帧，但可能会陷入无限循环。而BFS则能保证找到最短路径，适用于寻找最近的邻居或解决最短路径问题，但需要额外的空间存储队列中的节点。在实际应用中，"深搜广搜.cpp"文件可能包含了这两个算法的实现。"cpp.rar"文件可能是一个压缩包，其中包含与这两个算法相关的其他C++源代码或资源。理解并掌握这两种搜索算法对于学习数据结构和算法、进行图形处理以及解决实际问题具有重要意义。

资源推荐

资源详情

资源评论

收起资源包目录

dp.rar （2个子文件）

cpp.rar 1.07MB

深搜广搜.cpp 2KB

#include<stdio.h> #include<queue.h> char map[11][11]={"#S######.#","......#..#",".#.##.##.#",".#........","##.##.####","....#....#",".#######.#","....#.....",".####.###.","....#...G."}; int fx_x[4]={-1,1,0,0},fx_y[4]={0,0,-1,1}; int row=10,col=10,minStep=1000000,maxStep=-1; struct node{ int x,y,step; }; queue<node> q; int main() { void dfs(int x,int y,int step); int bfs(int x,int y); int i,j,start_x,start_y; for (i=0;i<row;i++) { for (j=0;j<col;j++) { if (map[i][j]=='S') { start_x=i; start_y=j; } } } // dfs(start_x,start_y,0); // printf("最短:%d 最大:%d\n",minStep,maxStep); printf("%d\n",bfs(start_x,start_y)); return 0; } /*深搜*/ void dfs(int x,int y,int step) { // printf("当前第 %d 步 [%d][%d] = %c\n",step,x,y,map[x][y]); if (map[x][y]=='G') { if (step<minStep) { minStep=step; } if (step>maxStep) { maxStep=step; } return ; } int i,xx,yy; char c; for (i=0;i<4;i++) { xx=x+fx_x[i]; yy=y+fx_y[i]; if (xx<0 || x>=row || y<0 || y>=col) continue; c=map[xx][yy]; if (c=='#') continue; char temp=map[x][y]; map[x][y]='#'; dfs(xx,yy,step+1); map[x][y]=temp; } } /*广搜*/ int bfs(int x,int y) { node n={x,y,0}; q.push(n); int nx,ny,nStep; while(!q.empty()) { n=q.front(); q.pop(); nx=n.x; ny=n.y; nStep=n.step; if (map[nx][ny]=='G') { return nStep; } int i,xx,yy; char c; for(i=0;i<4;i++) { xx=nx+fx_x[i]; yy=ny+fx_y[i]; if (nx<0 || nx>=row || ny<0 || ny>=col) continue; c=map[xx][yy]; if (c=='#') continue; char temp=map[nx][ny]; map[nx][ny]='#'; node tn={xx,yy,nStep+1}; q.push(tn); } } return -1; }

评论收藏

内容反馈

版权申诉