dede网站后台,怎么自己做网站免费的,广州建网站公司,长沙人才招聘网目录
一#xff0c;深度优先搜索
1#xff0c;DFS
2#xff0c;图的DFS遍历
(1)#xff0c;递归实现#xff08;隐士栈#xff09;
(2)#xff0c;显示栈实现#xff08;非递归#xff09;
二#xff0c;广度优先搜索
1#xff0c;BFS
2#xff0c;图的BF…
目录
一深度优先搜索
1DFS
2图的DFS遍历
(1)递归实现隐士栈
(2)显示栈实现非递归
二广度优先搜索
1BFS
2图的BFS遍历
3路径记录
小结
最短路径问题 BFS BFS(广度优先搜索和DFS深度优先搜索 BFS和DFS树是图/树遍历的两种基础算法核心在于探索顺序和适用场景的不同。 一深度优先搜索
1DFS
DFS即Depth First Search深度优先搜索。遍历顺序为沿分支深入到底再回溯优先探索最新发现的节点。简单来说就是一条路走到黑。比如对下面一颗树的遍历。 从A开始遍历再到B有两种情况意味着这条路还没有走完接着走到D之后就没路了。然后我就回溯到B因为B还有情况没走完接着再走到E之后没路了就回溯到B发现B的两种情况以及那个走完了就再回溯到A然后走到C......
简单理解就是一条路走动黑直到没路可走了再回溯回去尝试其他路径。
2图的DFS遍历
DFS的实现方式有两种一种是递归实现但递归实现有时会产生栈溢出的风险可改用显示栈实现。
(1)递归实现隐士栈
#include iostream
#include vector
using namespace std;void DFS(vectorvectorint graph, int node, vectorbool visited)
{visited[node] true;cout node ; //前序遍历for (int neighbors : graph[node]){if (!visited[neighbors])DFS(graph, neighbors, visited);}}int main()
{//邻接表表示(无向图vectorvectorint graph {{1,2}, //节点0的邻居是1 2{0,3,4}, //节点1的邻居是0 3 4{0,5}, //节点2的邻居是0 5{1}, //节点3的邻居是1{1}, //节点4的邻居是1{2} //节点5的邻居是2};//记录访问过的节点vectorbool visited(graph.size(), false);cout DFS结果为:;DFS(graph, 0, visited);return 0;
}
(2)显示栈实现非递归 #include iostream
#include stack
#include vector
using namespace std;
void DFS_Stack(vectorvectorint graph, int start)
{vectorbool visited(graph.size(), false);stackint s;s.push(start);visited[start] true;while (!s.empty()){int node s.top();s.pop();cout node ;//逆序入栈 以保证和递归顺序一致for (auto it graph[node].rbegin(); it ! graph[node].rend(); it){int neighbors *it;if (!visited[neighbors]){visited[neighbors] true;s.push(neighbors);}}}
}
int main()
{//邻接表表示(无向图vectorvectorint graph {{1,2}, //节点0的邻居是1 2{0,3,4}, //节点1的邻居是0 3 4{0,5}, //节点2的邻居是0 5{1}, //节点3的邻居是1{1}, //节点4的邻居是1{2} //节点5的邻居是2};cout 栈实现遍历结果为: endl;DFS_Stack(graph, 0);return 0;
}
二广度优先搜索
1BFS
BFS即Breadth First Search即广度优先搜索。DFS是一条路走到黑那么 BFS就可以理解成是在每个岔路口都向前走一步。也可以理解成是一层一层遍历。 从A开始遍历有两种情况BC。 将BC遍历完后再遍历D,E,F。一层一层的遍历。 上述是对树的BFS然而树也是一种 图。 不难发现我们每次搜索的位置都是离当前节点最近的点。因此BFS是具有最短路性质的。这里用到的贪心策略是想要找到最短路径保证每次在选节点时也就是每次前进的时候都是距离上一个节点最近的点。 因此BFS也可以求解最短路问题。 2图的BFS遍历
#include iostream
#include vector
#include queue
#include unordered_setusing namespace std;// BFS 遍历函数
void BFS(const vectorvectorint graph, int start) {vectorbool visited(graph.size(), false); // 访问标记数组queueint q;q.push(start);visited[start] true;while (!q.empty()) {int node q.front();q.pop();cout node ; // 输出当前节点可替换为自定义操作// 遍历所有邻接节点for (int neighbor : graph[node]) {if (!visited[neighbor]) {visited[neighbor] true;q.push(neighbor);}}}
}int main() {// 示例图的邻接表表示无向图vectorvectorint graph {{1, 2}, // 节点0的邻居是1和2{0, 3, 4}, // 节点1的邻居是0、3、4{0, 5}, // 节点2的邻居是0、5{1}, // 节点3的邻居是1{1}, // 节点4的邻居是1{2} // 节点5的邻居是2};cout BFS遍历结果;BFS(graph, 0); // 从节点0开始遍历// 输出0 1 2 3 4 5 return 0;
}
3路径记录
在图中寻找一条从开始到目标target的路径。
vectorint BFS_Path(vectorvectorint graph, int start, int target)
{vectorbool visited(graph.size(), false); //记录访问过的节点vectorint parent(graph.size(), -1); //记录父节点queueint q;q.push(start);visited[start] true;while (!q.empty()){int node q.front();q.pop();if (node target)break;for (int neighbors : graph[node]){if (!visited[neighbors]){visited[neighbors] true;parent[neighbors] node; //neighbors的父节点nodeq.push(neighbors);}}}vectorint path;for (int at target; at ! -1; at parent[at])path.push_back(at);reverse(path.begin(), path.end());return path;
}
最短路径问题 BFS
【题目描述】
给的那个一个n*m的二维整数数组用来表示迷宫数组中只包含1和00表示可以走的路1表示不可以通过的墙壁。
最初有一个人位于左上角(1,1)处已知改人每次可以向上下做右任意一个方向移动一个位置。请问改人从左上角移动到右下角(n,m至少需要移动多少次。数据保证00和n,m的位置均为0。且一定至少存在一条通路。
【输入格式】
第一行包含两个整数n和m。
接下来n行每行包含m个整数0或1表示迷宫。
【输出格式】
表示最少移动次数。
本题求的是最短路所以可以用bfs从当前节点出发每次向四周扩展。
#include iostream
#include queue
#include cstring
using namespace std;typedef pairint, int PII;//方向数组
int dx[4] { -1,0,1,0 }, dy[4] { 0,1,0,-1 };
const int N 110;
int map[N][N]; //迷宫
int mark[N][N]; //标记数组
int n, m;void BFS()
{memset(mark, -1, sizeof(mark));queuePII q;q.push({ 0,0 });mark[0][0] 0;while (!q.empty()){PII top q.front();q.pop();for (int i 0; i 4; i){int x top.first dx[i];int y top.second dy[i];if (x 0 x n y 0 y m mark[x][y] -1 map[x][y] 0){q.push({ x,y });mark[x][y] mark[top.first][top.second] 1;}}}coutmark[n - 1][m - 1]endl;
}
int main()
{cin n m;for (int i 0; i n; i)for (int j 0; j m; j)cin map[i][j];BFS();return 0;
}
小结 BFS优势与局限 优点 保证找到最短路径无权图。 避免深度过大的栈溢出风险。 缺点 空间消耗大存储整层节点。 不适合目标节点在深层的情况效率低。 DFS优势与局限 优点 空间效率高仅存储当前路径。 适合寻找所有解如回溯算法。 缺点 可能陷入无限深的分支需设置最大深度。 递归实现有栈溢出风险可改用显式栈。
