迹忆客 专注技术分享

广度优先搜索是一种用于遍历或搜索树或图数据结构的算法。 在每个节点，算法在访问父节点之前先访问子节点。

换句话说，它从每个树级别的当前位置向外扩展，而不是向上移动到父级并向下移动到子级。

广度优先搜索用于查找图上的最短路径。 它已被用于在人工智能、计算机科学、数学和社会科学等许多领域寻找解决方案。

广度优先搜索算法

广度优先搜索是一种广度遍历树的搜索算法，以广度优先的方式扩展节点。

该算法从任意节点开始并扩展其所有子节点。 然后，它继续对其每个子级执行相同的操作，依此类推。

当该过程到达叶节点或找到目标状态时终止。

为了找到从一个节点到另一个节点的最短路径，我们需要知道它到该节点的距离。 这可以通过添加图中任意两个节点之间的边长来计算。

用 C++ 进行广度优先搜索迷宫的步骤

用C++做广度优先搜索迷宫的步骤如下：

• 创建一个图形对象并使用边和顶点对其进行初始化。
• 创建一个队列，其中包含我们要执行广度优先搜索的顶点。
• 将队列的前指针初始化为 NULL。
• 创建一个空列表，其中包含我们要执行广度优先搜索的顶点。
• 将列表的前指针初始化为 NULL。
• 将与其自身相连的起始顶点（索引为0的顶点）添加到队列中。
• 将起始顶点添加到列表中并将其父指针设置为 NULL。

当队列变为非空时，我们从中取出一个元素并递归地调用广度优先搜索算法，直到到达未探索的节点。

最后，当队列变空时，我们到达迷宫的一端并停止从该方向搜索未探索的节点。

C++ 广度优先搜索迷宫的示例

这是 C++ 中广度优先搜索迷宫的示例。 该代码实现了查找从给定起始节点到图中所有其他节点的最短路径的算法。

#include <bits/stdc++.h>
using namespace std;
#define HORI 3
#define VERT 3
struct Point
{
    int a;
    int b;
};
struct queueNode
{
    Point de;
    int sam;
};
bool isValid(int hori, int vert)
{
    return (hori >= 0) && (hori < HORI) &&
        (vert >= 0) && (vert < VERT);
}
int horiNum[] = {9, 7, 9, 2};
int vertNum[] = {3, 3, 4, 5};
int BFS(int lk[][VERT], Point ace, Point hello)
{
    if (!lk[ace.a][ace.b] || !lk[hello.a][hello.b])
        return -1;
    bool visited[HORI][VERT];
    memset(visited, false, sizeof visited);
    visited[ace.a][ace.b] = true;
    queue<queueNode> e;
    queueNode s = {ace, 0};
    e.push(s);
    while (!e.empty())
    {
        queueNode curr = e.front();
        Point de = curr.de;
        if (de.a == hello.a && de.b == hello.b)
            return curr.sam;
        e.pop();
        for (int i = 0; i < 4; i++)
        {
            int hori = de.a + horiNum[i];
            int vert = de.b + vertNum[i];
            if (isValid(hori, vert) && lk[hori][vert] &&
            !visited[hori][vert])
            {
                visited[hori][vert] = true;
                queueNode Adjcell = { {hori, vert},    curr.sam + 1 };
                e.push(Adjcell);
            }
        }
    }
    return -1;
}
int main()
{
    int lk[HORI][VERT] =
    {
        { 3, 9, 2 },
        { 4, 5, 3 },
        { 0, 3, 0 }
    };
    Point source = {0, 0};
    Point hello = {1, 1};
    int sam = BFS(lk, source, hello);
    if (sam != 1)
        cout << "Shortest Path:" << sam ;
    else
        cout << "Failed!!!";
    return 0;
}