Программа, чтобы найти, существует ли путь между двумя заданными вершинами графа - PullRequest
Новая
       40

Программа, чтобы найти, существует ли путь между двумя заданными вершинами графа

0 голосов
/ 04 июня 2019

Я написал следующий код на 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 exists\n");
            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 exist\n");
}

Тестовые случаи, для которых работает этот код: 

    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

Ответы [ 2 ]

1 голос
/ 05 июня 2019

Несмотря на ошибки в ваших тестовых примерах, у вас есть несколько проблем с вашим кодом, среди которых:

  • вы поддерживаете ep в качестве индекса следующего доступного элемента вашей очереди, но ваше условие цикла обрабатывает его как последний использованный элемент: 
    while (bp <= ep) {
  • вы не пересекаете краяпервая вершина поставлена ​​в очередь.Вы смотрите мимо него на секунду: 
                if (maze[queue[bp + 1]][i] == 1) {

  • вы смотрите на две вершины после последней в очереди (те же строки уже процитированы)

  • у вас нет механизма, позволяющего избежать посещения одной и той же вершины более одного раза, поэтому

    1. вы используете квадратное пространство очереди, когда в принципе вынужно только линейное,
    2. , но даже этого недостаточно, потому что в случае, если начальная вершина является частью цикла, но не связана с желаемой конечной вершиной, ваша BFS никогда не прекратит работу (до тех пор, пока не произойдет сбой программы).
0 голосов
/ 05 июня 2019

Подход верный, но в тестовых случаях я начал индексировать с '0' в более поздних, поэтому я получил ошибку сегментации, поэтому, если маркировка вершин начинается с 1, этот код работает нормально.

...