Программа для нахождения кратчайшего цикла в графе.
Поиск цикла обходом графа в ширину.
Проблема в функции VvodGrafa.В проверке условий if(n > 10 || n<=3 ),условие находит ошибки при вводе вершин.
НЕ получается сделать так,чтобы при невыполнении условия цикл завершался.
Пробовал рекурсией и break,но не выходит(
Код:
#include <stdio.h>
#include <conio.h>
#define NMAX 10 /*Max kol-vo vershin*/
/***** Vvod Grafa *****/
void VvodGrafa(int g[NMAX][NMAX], int n)
{
int i,j;/* nomer stroki,stolbca */
if(n > 10 || n<3 )
{
printf("\nOshibka! Vvedite 3 <= n <= 10 \n\n");
}
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 && g[i][i]!=1;j++)
{
scanf("%d",&g[i][j]);
}
if(j<n)
{printf("Petli v grafe!");
}
}
}
/*Poisk obhodom v shirinu*/
/*Matrica smegnosti-g,nomera vershin cikla vektor-cmin,dlina cikla-dcmin(3...n)*/
/*0-cikl naiden,1-graf ne imeet ciklov*/
#define NOV -1 /*Vershina novaya,ne vstrechalas*/
int Pminc(int g[NMAX][NMAX], int n, int cmin[])
{
int p[NMAX]; /*Kratchayschie puti k nachalnoy vershine*/
int q[NMAX]; /*Ochered vershin na posechenie(vektor)*/
int in,ik; /*Indexi nachala i konca ocheredi*/
int i,j; /*Nomera vershin*/
int vn,v,vpr; /*Nomera nachalnyi,tekuchei i prediduchei vershin*/
int c[NMAX+1]; /*Tekuchui cikl*/
int dcmin;
/*Poisk kratchaishego cikla obhodom grafa v shirinu*/
dcmin=n+1; /*Dlina min. cikla(3..n)*/
for(vn=0;vn<n && dcmin>3;vn++) /*Nachalnaya vershina*/
{
/*Obhod v shirinu dereva putei,nachinaushihsya c vn*/
for(i=0;i<n;i++)
p[i]=NOV; /*Vse vershini novie*/
in=0;
ik=1; /*Pustaya ochered <==vn*/
q[0]=vn;
do
{
/*Vzyat iz ocheredi i posetit vershinu v*/
v=q[in];
in++; /*q[0...n-1]*/
vpr=p[v];
for(j=0;j<n;j++)
if(g[v][j]==1 && j!=vpr)
if(p[j]==NOV) /*Vershina j ne posechalas*/
{
/*Ochered na posechenie*/
q[ik]=j;
ik++; /*q[0...n-1]*/
p[j]=v; /*Predidushaya vershina puti k vn*/
}
else /*Cikl iz dvuh putei vn...j*/
{
/*Sozdat spisok vn->...->v->j*/
for(i=v;j!=vn;)
{
vpr=p[i];
p[i]=j;
j=i;
i=vpr;
}
/*Zapomnit cikl v->j...->v v vektore c*/
c[0]=v;
i=v;
j=0;
do
{
i=p[i];
c[j++]=i;
}
while(i!=v);
if(j<dcmin)
{
/*Zapomnit cikl c[0]...c[j]*/
dcmin=j;
while(j>=0)
cmin[j]=c[j--];
}
in=ik;
break;
}
}
while(in!=ik && dcmin>3); /*Ochered ne pusta*/
printf("Kratchaishiy cikl dlinoy");
printf(" %d:\n",dcmin);
for(j=0;j<n-1;j++)
{if(dcmin<3)
{printf("Cikla net");
break;}
printf(" %d ", cmin[j]);
}
}
return dcmin;
}
#define NMAX 10 /*Max kol-vo vershin*/
main()
{
int n,j;
int dcmin;
int cmin[j];
int g[NMAX][NMAX];
printf ("\n\nVvedite kol-vo vershin <= 10 \n n=");
scanf("%d",&n);
VvodGrafa(g,n);
Pminc(g,n,cmin);
printf("\n\n");
getch();
}