如何用C++编写BFS函数？

Question

#include <iostream>
#include <string>
#include <queue>

using namespace std;
void BFS(const string&, const string[], int[][10]);

int main()
{
    const int CAP = 10;

    string states[CAP] = { "Arizona", "California", "Idaho", "Nevada", "Oregon", "Utah", "Washington" };
    string Point;

    int matrix[CAP][CAP] =
    {
    {0,1,0,1,0,1,0},
    {1,0,0,1,1,0,0},
    {0,0,0,1,1,1,1},
    {0,1,1,1,0,0,1},
    {1,1,1,1,0,0,0},
    {0,0,1,0,1,0,0},
    {0,0,1,0,1,0,0}
    };


    BFS("California", states, matrix);


}

void BFS(const string& Point, const string states[], int matrix[][10])
{
    int SPoint = 0;
    queue<string> visited;
    queue<string> Queue;


    string temp = Point;

    visited.push(temp);
    do
    {

        for (int i = 0; i < 10; i++)
        {
            if (states[i] == temp)
            {
                SPoint = i;
            }
        }
        for (int i = 0; i < 10; i++)
        {
            if (matrix[SPoint][i] == 1)
            {
                Queue.push(states[i]);
            }
        }

        visited.push(Queue.front());
        Queue.pop();

        temp = visited.back();

    } while (!Queue.empty());


    for (int i = 0; i < 10; i++)
    {
        cout << visited.front();
        visited.pop();
    }


}

我正在做一个练习，我必须创建一个函数来执行广度优先搜索并打印出访问过的路径。但是我的函数不会打印任何东西。我在这里做错了什么？

注：矩阵按字母顺序排列，表示状态之间的联系。

我的预期输出：加利福尼亚州亚利桑那州俄勒冈州内华达州犹他州爱达荷州华盛顿

Exercise description

Answer 1

虽然我不会提供完整的解决方案，但我可以帮助确定代码中出现的一些问题。

主要问题

由于您有一个循环图，因此在 BFS 期间将节点标记为已访问非常重要，否则您将陷入无限循环（这就是为什么在您当前的实现中不打印任何内容的原因）。您的 visited 队列可能是 unordered_set。当访问节点时，将它们添加到集合中并编写条件以避免再次访问它们。
邻接矩阵显示不正确。由于它是一个无向图，我预计矩阵将从左上角到右下角进行镜像，但事实并非如此。此外，图中没有自边，但内华达州在矩阵中似乎有自己的边。
无需遍历邻接矩阵——您可以通过适当映射数字索引和字符串名称来对其进行索引。如果确实需要循环，运行 10 在 7x7 矩阵上超出范围。

小问题

任意限制矩阵大小是没有意义的。尽管赋值强制执行了这一点，但这是一个糟糕的设计选择，因为每当您想使用不同的输入图时都需要重写代码。
矩阵在这里似乎是一种有点笨拙的数据结构，因为它引入了一个额外的间接层来将字符串转换为整数并返回。虽然项目不允许，但我更喜欢使用这样的结构：
```
std::unordered_map<std::string, std::vector<std::string>> graph({
    {"California", {"Oregon", "Nevada", "Arizona"}},
    // ... more states ...
});
```
理想情况下，这些将是具有 neighbor 个向量成员而不是字符串的 Node 个对象。
C++ 提供 std::vector 和 std::array，它们优于 C 数组。我假设它们还没有在你的 class 中引入或者不允许在作业中引入，但是如果你遇到困难，你可以尝试使用它们编写代码，然后在你之后重新引入你的教师的约束让它工作。如果不出意外，这将是一次学习经历。
避免using namespace std;.
为 class 名称保留大写变量名称。对象和基元应该是小写的。

BFS 伪代码

这假定了上面的首选数据结构；您可以根据需要在字符串和邻接矩阵索引之间进行相互转换。

func BFS(string start, unordered_map<string, vector<string>> graph):
    vector traversal
    queue worklist = {start}
    unordered_set visited = {start}

    while !worklist.empty():
        curr = worklist.pop_front()            
        traversal.push_back(curr)

        for neighbor in graph[curr]:
            if neighbor not in visited:
                visited.insert(neighbor)
                worklist.push(neighbor)

    return traversal

由于这是一项作业，我就此打住，让您再次破解代码。祝你好运。

如何用C++编写BFS函数？

How to write BFS function in C++?

c++

graph

breadth-first-search

matrix

nodes

主要问题

小问题

BFS 伪代码