Используя рекурсию, определить, можно ли по дорогам попасть из 1-го пункта в N-ый - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Имеется 10 населенных пунктов. Дана последовательность пар чисел пар чисел I и J (I<J), указывающих, что I –ый J-ый пункты соединены дорогой. Признак конца этой последовательности - пара нулей. Используя рекурсию, определить, можно ли по этим дорогам попасть из 1-го пункта в N-ый. Помогите, пожалуйста.

Решение задачи: «Используя рекурсию, определить, можно ли по дорогам попасть из 1-го пункта в N-ый»

textual
Листинг программы
#include <stdio.h>
 
#define MAXVERTICES 100
#define MAXEDGES    100
enum { NO, YES };
 
int n;
int found = NO;
int used[MAXVERTICES + 1] = { NO };
int edges[MAXEDGES + 1][2];
 
void walk(int vtx);     
 
int main()
{
        int i, j, cnt;
 
        printf("enter n:\n");
        scanf("%d", &n);
        if (n <= 0 || n > MAXVERTICES)
                return 1;
        printf("enter edges:\n");
        cnt = 0;
        while (cnt < MAXEDGES
                && scanf("%d %d", &i, &j) == 2 && i && j) {
                edges[cnt][0] = i;
                edges[cnt][1] = j;
                cnt++;
        }
        edges[cnt][0] = edges[cnt][1] = 0;
        walk(1);
        printf("one can%s\n", found ? "" : "not");
        return 0;
}
 
#define isnotused(vtx) (used[(vtx)] == NO)
 
void walk(int vtx)
{
        int i;
 
        used[vtx] = YES;
        if (vtx == n || found == YES) {
                found = YES;
                return;
        }
        for (i = 0; edges[i][0] != 0; i++)
                if (edges[i][0] == vtx && isnotused(edges[i][1]))
                        walk(edges[i][1]);
                else if (edges[i][1] == vtx && isnotused(edges[i][0]))
                        walk(edges[i][0]);
}

Объяснение кода листинга программы

В этом коде реализована функция, которая с помощью рекурсии проверяет, можно ли по дорогам попасть из 1-го пункта в N-ый. Для этого в коде представлены следующие элементы:

  1. Объявлены следующие переменные: n - количество вершин в графе, которое вводится пользователем. found - флаг, который указывает, можно ли добраться до последней вершины. used - массив, который отслеживает, была ли уже посещена та или иная вершина. edges - массив, который содержит информацию о ребрах графа.
  2. С помощью функции walk(int vtx) происходит обход графа.
  3. В функции main() пользователю предлагается ввести количество вершин и информацию о ребрах графа.
  4. После сбора данных происходит вызов функции walk(1), которая начинает обход графа с первой вершины.
  5. Результатом работы программы будет сообщение о том, можно ли добраться до последней вершины или нет.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 3.857 из 5
Похожие ответы