Нахождение кратчайшего цикла в графе - C (СИ) (154256)

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

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

Программа для нахождения кратчайшего цикла в графе. Не могу корректно отладить.Прошу помочь.Заранее благодарен.
#include <stdio.h>
#include <conio.h>
#define N 10
/* Vvod Grafa*/
void VvodGrafa(int g[N][N], int n)
{int i,j;// nomer stroki,stolbca
 printf("Vvedite matricy smeznosti:\n\n");
 printf(" | ");
 for(j=0;j<n;j++)
  printf("%d",j);
  putchar('\n');
 for(i=0;i<2*n+2;i++)
  putchar('-');
 for(i=0;i<n;i++)
  {printf("\n%d| ",i);
 for(j=0;j<n;j++)
  scanf("%d",&g[i][j]);}
}
 
/*Poisk cikla*/
int Poisk(int g[N][N],int n,int c[],int *dcmin)//c-vektor s nomerami vershin naidennogo cikla;dlina min.cikla - dcmin
{int k;// ukazatel steka
 int ver[N+1];//Stek s nomerami vershin 
 int st[N];//stek
 int tv;//nomer ocherednoi vershini tecushego puti
 int i,j;
 /*Obhod v glubinu*/
 *dcmin=n+1;
 for(ver[0]=1;ver[0]<=n && *dcmin>3;)/* Nachalnaya vershina*/
{/*Obhod v glubinu dereva putei,nachinayshihsya s ver[0]*/
 k=1;ver[1]=ver[0]+1;//nachalnyu nomer priemnikov s ver[0]
 do
 {/*nahogdenie vershini tv - priemnika ver[k-1]*/
 j=ver[k-1];
 for(tv=ver[k];tv<n && (g[i][tv]==0 || tv==ver[k-2]);ver++)
  if(tv<n && k<*dcmin)
   {ver[k]=tv;/*vpered:tv-v stek*/
    ver[k+1]=tv[0];/*nachalnyi priemnik ver[k]*/
    if(ver[0]==ver[k] && k>0) /*nashli cikl*/
    {*dcmin=k;
    /*Zapomnit' cikl ver[0]...ver[k]*/
    for(j=0;j<=k;j++) c[j]=ver[j];[B][/B]
    k=k-3;/*Nazad: udalit' dve vershini*/
    ver[k+1]++;/*Sled priemnik ver[k]*/
    }
    k++;
    }else
    {k--;/*udalit' ver[k] iz steka*/
    ver[k]++;
    }
   }while(k>0 && *dcmin>3);/*stek ne pustoi*/
  }
  return *dcmin>n;
}  
/*Glavnaya funkciya*/
main()
{int n;
 int g[N][N];
  printf("n=");
  scanf("%d",&n);
  VvodGrafa(g,n);
  Poisk(g,n);
  getch();
}

Решение задачи: «Нахождение кратчайшего цикла в графе»

textual
Листинг программы
#include <stdio.h>
#include <conio.h>
#define N 10
 
/***** Vvod Grafa *****/
 
void VvodGrafa(int g[N][N], int n)
{
int i,j;// nomer stroki,stolbca
   printf("Vvedite matricy smeznosti:\n\n");
   printf(" | ");
 for(j=0;j<n;j++)
     printf("%d",j);
     putchar('\n');
 for(i=0;i<2*n+2;i++)
     putchar('-');
 for(i=0;i<n;i++)
{
     printf("\n%d| ",i);
   for(j=0;j<n;j++)
       scanf("%d",&g[i][j]);}
}
 
 
/***** Poisk cikla *****/
 
int Poisk(int g[N][N],int n,int c[],int *dcmin)//c-vektor s nomerami vershin naidennogo cikla;dlina min.cikla - dcmin
{
 int k;// ukazatel steka
 int ver[N+1];//Stek s nomerami vershin 
 int st[N];//stek
 int tv;//nomer ocherednoi vershini tecushego puti
 int i,j;
  
  /*Obhod v glubinu*/
  
  *dcmin=n+1;
 for(ver[0]=1;ver[0]<=n && *dcmin>3;)/* Nachalnaya vershina*/
 
{/*Obhod v glubinu dereva putei,nachinayshihsya s ver[0]*/
 
    k=1;ver[1]=ver[0]+1;//nachalnyu nomer priemnikov s ver[0]
  do
 {/*nahogdenie vershini tv - priemnika ver[k-1]*/
    j=ver[k-1];
 for(tv=ver[k];tv<n && (g[i][tv]==0 || tv==ver[k-2]);ver++)
     if(tv<n && k<*dcmin)
     {
         ver[k]=tv;/*vpered:tv-v stek*/
         ver[k+1]=tv[0];/*nachalnyi priemnik ver[k]*/
     if(ver[0]==ver[k] && k>0) /*nashli cikl*/
     {
         *dcmin=k;
    /*Zapomnit' cikl ver[0]...ver[k]*/
    for(j=0;j<=k;j++) c[j]=ver[j];
        k=k-3;/*Nazad: udalit' dve vershini*/
        ver[k+1]++;/*Sled priemnik ver[k]*/
     }
         k++;
     }
     else
     {
         k--;/*udalit' ver[k] iz steka*/
         ver[k]++;
     }
     }
     while(k>0 && *dcmin>3);/*stek ne pustoi*/
     }
  return *dcmin>n;
}  
 
/***** Glavnaya funkciya *****/
 
main()
{int n;
 int g[N][N];
  printf("n=");
  scanf("%d",&n);
  VvodGrafa(g,n);
  Poisk(g,n);
  getch();
}

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

  1. Ввод графа:
    • Переменная n получает значение количества вершин в графе (ввод с клавиатуры).
    • Ввод матрицы смежности графа с помощью функции scanf.
  2. Поиск цикла:
    • Создание и инициализация векторов ver и st.
    • Переменная k инициализируется значением 1, а переменная ver[1] устанавливается равной ver[0]+1.
    • Цикл do начинается. В каждой итерации цикла:
      • Переменная j устанавливается равной ver[k-1].
      • Цикл for начинается. В каждой итерации цикла:
        • Переменная tv устанавливается равной ver[k].
        • Если tv меньше количества вершин и k меньше минимальной длины цикла, то:
          • ver[k] и ver[k+1] обновляются.
          • Если ver[0] равно ver[k], то:
            • k уменьшается на 3.
            • ver[k+1] увеличивается.
            • Если цикл найден, то:
              • Минимальная длина цикла сохраняется в переменной *dcmin.
              • Цикл сохраняется в массив c.
              • k уменьшается на 3.
              • ver[k+1] увеличивается.
              • Цикл продолжается, пока k больше 0 и *dcmin больше 3.
              • Если цикл не найден, то *dcmin устанавливается равным количеству вершин плюс 1.
              • Цикл завершается.
              • Функция main возвращает значение 0.
  3. Главная функция:
    • Переменная n получает значение количества вершин в графе (ввод с клавиатуры).
    • Функция VvodGrafa вызывается для ввода матрицы смежности графа.
    • Функция Poisk вызывается для поиска цикла в графе.
    • Функция getch вызывается для приостановки выполнения программы до нажатия клавиши.

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

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