广度优先搜索找不到正确的路径

Question

所以我有一个实验室使用邻接矩阵来实现广度优先搜索和深度优先搜索。要搜索的图的顶点编号为 0-(V-1)，因此例如具有 10 个顶点的图的顶点编号为 0-9。每个顶点也被赋予一个值。

在我要给出的示例中，每个顶点的数量等于它的值（例如，顶点 0 的值为 0，顶点 1 的值为 1，等等）。我将每个顶点的值存储在一个数组中，位置是顶点，数组中的项目是它的值，所以找到顶点 7 的值看起来像：

value = matrix[7];

我应该编写一个程序，使用广度优先搜索找到某个值并报告找到它的顶点，以及找到它需要多少 "steps"。

我的程序在每个测试用例中找到了值，但问题是 "steps" 不匹配。我认为问题一定出在我的 BFS 算法本身，但我找不到它。

例如，我在以下邻接矩阵中搜索值 7，它位于顶点 7：

0 1 1 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

一共有10个节点，编号为0-9，节点0连接到节点1和2，节点1连接到节点3和4，节点2连接到节点5和6，节点3连接到节点 7 和 8，节点 4 连接到节点 9。

如前所述，"vertices" 是顶点值数组。 "matrix" 是邻接矩阵。 "visited" 是一个布尔数组，用于跟踪是否访问了一个顶点。

我是"walking"带有双端队列容器的图表，我必须使用它。

这是我的 BFS：

steps = 1;
int cur_v = 0;
int vertexFound = 0;
bool found = false;
bool *visited = new bool[V];
for (int i = 0; i < V; i++) {
    visited[i] = false;
}
deque <int> q;
q.push_back(0);
visited[0] = true;
while (!q.empty()) {
    if (found == false) {
        steps++;
    }
    cur_v = q.front();
    q.pop_front();
    for (int n = 0; n < V; n++) {
        if (matrix[cur_v][n] == 1) {
            if (visited[n] == false) {
                if (vertices[n] == search) {
                    vertexFound = n;
                    found = true;
                }
                visited[n] = true;
                q.push_back(n);
            }
        }
    }
} 
if (found == true) {
    cout << steps << endl;
}

我要搜索的值是“7”，位于顶点 7。我应该需要 7 步才能到达那里，但我的程序说需要 5 步。

我遇到的另一个问题是，当我给程序输入应该让它在具有从值 0-7 的 8 个顶点的图中搜索值 8 时，它告诉我它找到了值在 9 个步骤中的顶点 0。

非常感谢任何帮助！

Answer 1

您不应该在第一次找到所需内容后更新 vertexFound。（事实上你可以立即停止搜索。）

广度优先搜索找不到正确的路径

Breadth First Search not finding correct path

c++

arrays

matrix

depth-first-search

breadth-first-search