C++语法09:迷宫中的最短路径:广度优先搜索算法的应用

这篇具有很好参考价值的文章主要介绍了C++语法09:迷宫中的最短路径:广度优先搜索算法的应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一·引言

广搜,即广度优先搜索(Breadth-First Search, BFS),是图论和计算机科学中常用的一种算法。它从一个顶点开始,探索所有相邻的顶点,然后对每个相邻的顶点做同样的操作,直到找到目标顶点或遍历完所有顶点。广搜算法在实际应用中具有广泛的用途和诸多好处,本文将详细探讨这些方面,并介绍广搜算法的具体用法。

二·广搜算法的用途

1·图遍历

广搜算法最基本的应用是对图进行遍历。在图论中,遍历是指从图的某一顶点出发,按照某种规则访问图中的其余顶点,并使每个顶点仅被访问一次。广搜算法适用于非加权图或权值相同的图的遍历,能够有效地探索整个图的结构。

2·最短路径问题

虽然广搜算法通常用于非加权图的遍历,但在某些特定情况下,它也可以用于解决最短路径问题。例如,在迷宫求解中,如果将迷宫的每个格子视为一个顶点,格子之间的移动视为边,那么广搜算法可以用来找到从起点到终点的最短路径。

3·层次遍历

广搜算法常用于树的层次遍历。在树形结构中,层次遍历是指按照从上到下、从左到右的顺序访问树的节点。广搜算法通过维护一个队列来实现对树的层次遍历。

4·网络爬虫

网络爬虫是广搜算法在互联网领域的重要应用之一。爬虫程序从一个或多个初始网页开始,通过广度优先搜索策略,逐步访问并下载网页上的链接,从而实现对整个互联网或特定网站的遍历。

三·广搜算法的好处

1·简单易实现

广搜算法的思想直观且简单,容易理解和实现。通过维护一个队列来记录待访问的顶点,按照先进先出的原则进行遍历,使得算法的实现过程清晰明了。

2·空间复杂度低

相比于深度优先搜索(Depth-First Search, DFS),广搜算法通常具有较低的空间复杂度。在DFS中,需要使用递归或栈来保存中间状态,可能导致较大的空间开销。而广搜算法通过队列来保存待访问的顶点,空间占用相对较少。

3·适用于非加权图

广搜算法特别适用于非加权图的遍历和搜索问题。在非加权图中,所有边的权值相同,广搜算法能够以最短的时间找到目标顶点或遍历完整个图。

4·易于优化

广搜算法可以通过一些优化手段来提高效率。例如,在搜索过程中,可以通过剪枝来排除不可能到达的顶点,从而减少不必要的搜索。此外,还可以利用启发式信息来指导搜索方向,进一步提高算法的性能。

四·广搜算法的用法

广搜算法(BFS)通常使用队列(Queue)数据结构来实现。基本步骤如下

  1. 初始化:

    • 创建一个队列,用于存储待访问的节点。
    • 创建一个标记数组或集合,用于记录已经访问过的节点。
    • 将起始节点加入队列。
  2. 遍历队列:

    • 当队列不为空时,从队列中取出一个节点。
    • 检查该节点是否为目标节点,如果是,则算法结束,返回路径。
    • 如果不是目标节点,则将其所有未访问过的相邻节点加入队列,并标记为已访问。
  3. 结束条件:

    • 如果队列为空,说明没有路径可以到达目标节点,算法结束。

五·示例

下面是一个使用C++实现的广搜算法示例,该示例解决了一个简单的迷宫问题。

#include <iostream>  
#include <queue>  
#include <vector>  
  
using namespace std;  
  
// 定义迷宫节点的坐标  
struct Node {  
    int x, y;  
    Node(int _x, int _y) : x(_x), y(_y) {}  
};  
  
// 判断节点是否有效(在迷宫范围内且可通行)  
bool isValid(int x, int y, int m, int n, const vector<vector<int>>& maze) {  
    return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0;  
}  
  
// 使用BFS找到从起点到终点的最短路径  
vector<Node> bfs(const vector<vector<int>>& maze, Node start, Node end) {  
    int m = maze.size();  
    int n = maze[0].size();  
    vector<vector<bool>> visited(m, vector<bool>(n, false)); // 记录节点是否被访问过  
    queue<Node> q; // 用于BFS的队列  
    q.push(start); // 将起点加入队列  
    visited[start.x][start.y] = true; // 标记起点为已访问  
  
    vector<Node> path; // 存储路径的节点  
  
    while (!q.empty()) {  
        Node current = q.front(); // 取出队列中的第一个节点  
        q.pop(); // 从队列中移除该节点  
  
        // 如果当前节点是终点,则构造并返回路径  
        if (current.x == end.x && current.y == end.y) {  
            path.push_back(current); // 将终点加入路径  
            while (!q.empty()) {  
                path.insert(path.begin(), q.front()); // 将队列中剩余节点加入路径  
                Node prev = q.front();  
                q.pop();  
                if (prev.x > current.x) current.x++;  
                else if (prev.x < current.x) current.x--;  
                else if (prev.y > current.y) current.y++;  
                else current.y--;  
                visited[current.x][current.y] = false; // 重置访问状态,以便后续使用  
            }  
            return path;  
        }  
  
        // 将当前节点的未访问相邻节点加入队列,并标记为已访问  
        vector<Node> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 右、左、下、上  
        for (const auto& dir : directions) {  
            int newX = current.x + dir[0];  
            int newY = current.y + dir[1];  
            if (isValid(newX, newY, m, n, maze) && !visited[newX][newY]) {  
                q.push(Node(newX, newY));  
                visited[newX][newY] = true;  
            }  
        }  
    }  
  
    // 如果没有找到路径,返回一个空路径  
    return path;  
}  
  
int main() {  
    // 迷宫布局,0表示可通行,1表示障碍物  
    vector<vector<int>> maze = {  
        {0, 0, 0, 0, 0},  
        {1, 1, 0, 1, 0},  
        {0, 0, 0, 1, 0},  
        {0, 1, 1, 1, 1},  
        {0, 0, 0, 0, 0}  
    };  
  
    // 起点和终点坐标  
    Node start(0, 0);  
    Node end(4, 4);  
  
    // 调用BFS函数寻找路径  
    vector<Node> path = bfs(maze, start, end);  
  
    // 输出路径  
    if (!path.empty()) {  
        cout << "Path found:" << endl;  
        for (const auto& node : path) {  
            cout << "(" << node.x << ", " << node.y << ") ";  
        }  
        cout << endl;  
    } else {  
        cout << "No path found." << endl;  
    }  
  
    return 0;  
}

六·总结

在迷宫的世界中,广度优先搜索算法为我们提供了一种可靠且高效的方式来寻找最短路径。通过逐步扩展并检查每个节点的邻居,我们能够确保不会错过任何可能的路径,直到我们到达终点。然而,值得注意的是,尽管BFS在许多情况下都表现良好,但它并不总是最优的选择。对于某些特定的迷宫或图结构,其他算法如Dijkstra或A*可能会更加高效。因此,在选择路径查找算法时,我们需要根据具体的问题和场景来做出决策。

最后,都看到这里了,留下一个免费的赞和关注呗~跪谢~

关注我,C++语法中的其它文章同样精彩,持续更新哦! 文章来源地址https://www.toymoban.com/news/detail-827611.html

到了这里,关于C++语法09:迷宫中的最短路径:广度优先搜索算法的应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 广度优先搜索(BFS)算法求解单源最短路径问题

      单源最短路径问题是图论中一类重要且常见的应用问题。在这个问题中,我们需要找到从一个给定源节点到其他节点的最短路径。广度优先搜索(BFS)算法是一种常用且有效的求解这一问题的算法。   本篇博客将重点讨论单源最短路径问题及其实际应用,同时简要介绍

    2024年02月13日
    浏览(45)
  • C++ 宽度优先搜索 || 模版题:走迷宫

    给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1 ,其中 0 表示可以走的路,1 表示不可通过的墙壁。 最初,有一个人位于左上角 (1,1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。 请问,该人从左上角移动至右下角 (n,m) 处,至

    2024年01月16日
    浏览(33)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(47)
  • C++:第十三讲BFS广度优先搜索

    今天带领大家学一下BFS。 DFS可以看——C++:第十二讲DFS深搜(二)_c++匿名函数dfs-CSDN博客 广度优先搜索(breadth-first search,缩写为bfs)又名宽度优先搜索,是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。其别名又叫BFS,属于一种盲目搜寻法,目的是

    2024年01月25日
    浏览(49)
  • 蛮力算法之深度优先遍历和广度优先遍历——图的深度优先遍历和广度优先遍历,附带案例:迷宫问题及矩阵中传染性传播问题

    这两种搜索方法本质上都是基于蛮力法思路 这两种搜索方法对有向图和无向图都适用 1.1 邻接矩阵 邻接矩阵示意图: 1.2 邻接表 注意:边结点代表的是图中的边,而并非图中的结点;头结点才表示图中的结点;头结点身后所连接的为边结点 邻接表示意图:(一般默认为出边

    2024年02月05日
    浏览(64)
  • 每天一道leetcode:1926. 迷宫中离入口最近的出口(图论&中等&广度优先遍历)

    给你一个 m x n 的迷宫矩阵 maze ( 下标从 0 开始 ),矩阵中有空格子(用 \\\'.\\\' 表示)和墙(用 \\\'+\\\' 表示)。同时给你迷宫的入口 entrance ,用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。 每一步操作,你可以往 上 , 下 , 左 或者 右 移动一个格子。你不能进

    2024年02月12日
    浏览(34)
  • 广度优先遍历与最短路径(Java 实例代码源码包下载)

    目录   广度优先遍历与最短路径 Java 实例代码 src/runoob/graph/ShortestPath.java 文件代码:   广度优先遍历从某个顶点 v 出发,首先访问这个结点,并将其标记为已访问过,然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} ,并将其标记为已访问过,然后将 {vi,...,vj} 中的每一个

    2024年02月12日
    浏览(31)
  • 【图论--搜索篇】宽度优先搜索,广度优先搜索

    今日语录: 成功是一种心态,如果你相信自己能做到,那你已经迈出成功的第一步。

    2024年01月24日
    浏览(46)
  • 【深度优先搜索】和【广度优先搜索】的区别介绍

    深度优先搜索(Depth-First Search,DFS)和广度优先搜索(Breadth-First Search,BFS)是两种常见的图搜索算法。它们的主要区别在于搜索的方式和顺序不同。 从某个节点出发,沿着一条路径直到底部,然后返回到前一个节点,继续搜索下一条路径,直到搜索完整张图。DFS使用栈或者

    2024年02月06日
    浏览(37)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)

    深度优先搜索(DFS)和广度优先搜索(BFS)是图论中两个非常重要的算法,主要用于拓扑排序,寻路(走迷宫)和搜索引擎等。在我们写算法时经常会遇到需要使用DFS和BFS的题目,例如leetcode中的岛屿相关的问题以及有关树的题目大多都会使用DFS或者BFS。 深度优先搜索 深度优

    2024年02月10日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包