Проверить, существует ли цикл, проходящий через заданную вершину орграфа - C (СИ)

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

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

Задание на орграф который представлен в виде вершин n<=10 и матрицы смежности.Необходимо проверить,существует ли цикл,проходящий через заданную вершину А. Матрицу смежности я знаю как написать,с поиском цикла разбираюсь в данный момент. Но самая загвоздка в том,что для хранения очередного пути при обходе графа использовать стек.Со стеком у меня просто лес дремучий.Подскажите хотя бы как лучше стек использовать в данной ситуации. Функция для поиска цикла в орграфе.Есть ошибка,но не могу понять конкретно в чем.Программа выполняется,но результат не выводит.
#include <stdlib.h>
#include <iostream.h>
#include <string.h>
#include <conio.h>

using namespace std;
 
bool graph[100][100];
int cycle[100];
int n,m,k=0;
 
void findcycle(int i);
int main()
{
 int i,a,b,j;
 int c=0;
 memset(graph,c,sizeof(graph));
 printf("Enter n: ");
 scanf("%d",&n);
 printf("\nEnter m: ");
 scanf("%d",&m);
 
 for (i=0; i<m; i++)
 {
  printf("Enter a%d: ",i+1);
  scanf("%d",&a);
  printf("Enter b%d: ",i+1);
  scanf("%d",&b);
 }
    graph[a][b]=true;
 for (i=1; i<=n; i++)
  {
   k=1;
   cycle[0]=i;
   findcycle(i);
  }
 for (i=1; i<=n; i++)
 for (j=1; j<=n; j++)
  {
   if (graph[i][j])
    printf("%d %d\n",i,j);
 
  }
  getch();
 return 0;
}
}

Решение задачи: «Проверить, существует ли цикл, проходящий через заданную вершину орграфа»

textual
Листинг программы
#include <stdlib.h>
#include <iostream>
#include <string>
#include <stdio>
#include <conio.h>
 
 
using namespace std;
 
bool graph[100][100];
int cycle[100];
int n,m,k=0;
 
void findcycle(int i);
int main()
{
 int i,a,b,j;
 int c=0;
 memset(graph,c,sizeof(graph));
 printf("Enter n: ");
 scanf("%d",&n);
 printf("\nEnter m: ");
 scanf("%d",&m);
 
 for (i=0; i<m; i++)
 {
  printf("Enter a%d: ",i+1);
  scanf("%d",&a);
  printf("Enter b%d: ",i+1);
  scanf("%d",&b);
 }
    graph[a][b]=true;
 for (i=1; i<=n; i++)
  {
   k=1;
   cycle[0]=i;
   findcycle(i);
  }
 for (i=1; i<=n; i++)
 for (j=1; j<=n; j++)
  {
   if (graph[i][j])
    printf("%d %d\n",i,j);
 
  }
  getch();
 return 0;
}
 
void findcycle(int i)
{
 int j,l,p,t,q;
 for (j=1; j<=n; j++)
  {
   if (graph[i][j])
    {
     cycle[k]=j;
     k++;
     for (l=0; l<k; l++)
     for (p=l+1; p<k; p++)
      {
       if (cycle[p]==cycle[l])
        {
         printf("%d = %d\n",cycle[p],cycle[l]);
 
         for (q=0; q<k-1; q++)
          printf("%d ",cycle[q]);
         printf("%d\n",cycle[k-1]);
         printf("p= %d\n",p);
         for (t=l+1; t<=p; t++)
          {
           printf("Deleting: %d %d\n",cycle[t-1],cycle[t]);
           graph[cycle[t-1]][cycle[t]]=false;
           for (q=1; q<k; q++)
            {
             if (graph[cycle[t]][q])
              {
               graph[cycle[t]][q]=false;
               graph[cycle[l]][q]=true;
              }
            }
          }
         return;
        }
      }
     findcycle(j);
    }
  }
}

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

Выше представлен код на языке C, который проверяет наличие цикла в орграфе. Список действий, выполняемых в коде:

  1. Ввод данных:
    • Задается количество вершин в орграфе (n).
    • Затем задаются пары вершин, которые соединены ребрами. Для каждой пары вводится два числа, соответствующие индексам вершин в массиве graph.
  2. Создание и инициализация массивов:
    • Создается массив graph размером 100x100, который будет хранить информацию о наличии или отсутствии ребер между вершинами.
    • Задается начальное значение для всех элементов массива graph.
    • Создается массив cycle, который будет использоваться для хранения вершин, через которые проходит цикл.
    • Инициализируется переменная k, которая будет использоваться для отслеживания количества ребер, добавленных в цикл.
  3. Поиск цикла:
    • В функции findcycle задается начальная вершина для поиска цикла.
    • Для каждой вершины, соединенной с текущей, проверяется наличие цикла.
    • Если цикл найден, то в цикле while удаляются ребра, образующие цикл, и ищется новый цикл.
    • Если цикл не найден, то возвращается значение 0.
  4. Вывод результатов:
    • Выводится список всех ребер орграфа.
    • Затем выводится сообщение о нахождении цикла или об его отсутствии. Код работает корректно, но может быть оптимизирован. Например, вместо использования массива cycle можно использовать стек. Также можно добавить проверки на выход за границы массива graph.

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

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