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

Question

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

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

value = matrix[7];

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

我的程序在每个测试用例中都找到了值，但问题是“步骤”不匹配。我认为问题一定出在我的 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。

如前所述，“顶点”是顶点值的数组。 “矩阵”是邻接矩阵。 “visited”是一个 bool 数组，用于跟踪某个顶点是否已被访问。

我正在使用我需要使用的双端队列容器“遍历”图形。

这是我的 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。 (事实上​​你可以立即停止搜索。)