C语言 用于查找图的两个给定顶点之间是否存在路径的程序

Question

>我用 C 编写了以下代码来查找图的两个给定顶点之间是否存在路径。最初，我要求用户输入，然后使用广度优先搜索来检查两个指定顶点之间是否存在路径。

此代码对于某些测试用例工作正常，但对其他测试用例会引发分段错误。我哪里出错了？

#include <stdio.h>
#include <stdlib.h>
int main() {
    int v, e, e1, e2, t1, t2;
    printf("Enter num of vertices and edges: ");
    scanf("%d %d", &v, &e);
    int maze[v][v];
    for (int i = 0; i < v; i++)
        for (int j = 0; j < v; j++)
            maze[i][j] = 0;
    printf("Enter edges:n")
    for (int i = 0; i < e; i++) {
        scanf("%d %d", &e1, &e2);
        maze[e1 - 1][e2 - 1] = 1;
        maze[e2 - 1][e1 - 1] = 1;
    }
    printf("The maze looks like:n");
    for (int i = 0; i < v; i++) {
        for (int j = 0; j < v; j++) {
            printf("%d ", maze[i][j]);
        }
        printf("n");
    }
    printf("enter target edges: ");
    scanf("%d %d", &t1, &t2);
    //BFS starts from here.
    int queue[v * v];
    int k = 1;
    queue[0] = t1 - 1;
    for (int i = 0; i < v; i++)
        if (maze[t1 - 1][i] == 1) {
            queue[k] = i;
             k++;
        }
    int bp, ep;
    bp = 0;
    ep = k;
    while (bp <= ep) {
        if (queue[bp] + 1 == t2) {
            printf("npath existsn");
            exit(0);
        } else {
            for(int i = 0; i < v; i++)
                if (maze[queue[bp + 1]][i] == 1) {
                    queue[k] = i;
                    k++;
                }       
        }
        bp = bp + 1;
        ep = k;
    }
    printf("npath does'nt existn");
}

此代码适用于的测试用例：

    Testcase-1:
    4 2
    1 2
    3 2
    1 3
    Testcase-2:
    4 2
    1 2
    3 2
    1 4
    TestCase-3:
    7 6
    0 1
    0 2
    1 3
    1 4
    1 6
    5 6
    1 6

我遇到分段错误的测试用例：

    TestCase-4:
    7 6
    0 1
    0 2
    1 3
    1 4
    1 6
    5 6
    0 6
    TestCase-5:
    7 6
    0 1
    0 2
    1 3
    1 4
    1 6
    5 6
    2 4

Answer 1

尽管测试用例中存在错误，但代码仍存在一些问题，其中包括：

• 您将ep作为队列中下一个可用元素的索引，但循环条件将其视为上次使用的元素：

    while (bp <= ep) {

• 不要遍历排队的第一个顶点的边缘。 你看过去看第二：

                if (maze[queue[bp + 1]][i] == 1) {

• 您最多查找两个顶点，超过最后一个排队的顶点(已引用的行相同(

• 您没有避免多次访问同一顶点的机制，因此

  1. 当原则上只需要线性时，您使用二次队列空间，
  2. 但即使这样也不够，因为如果起始顶点是循环的一部分，但没有连接到所需的结束顶点，您的 BFS 将永远不会终止(直到程序崩溃(。

Answer 2

该方法是正确的，但在测试用例中，我在以后的测试用例中从"0"开始索引，这就是我遇到分段错误的原因，因此如果顶点标记从 1 开始，则此代码工作正常。