Программа для нахождения кратчайшего цикла в графе.
Поиск цикла обходом графа в ширину.
Проблема в том,что после ввода матрицы смежности,программа выполняется,но выдает рандомные цифры в пункте "кратчайший цикл".
Код:
#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
printf ("Vvedite kol-vo vershin <= 10 \n\n");
printf("Vvedite matricy smeznosti:\n\n n=");
scanf("%d", &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 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 *dcmin, 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*/
/*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*/
}
return *dcmin>n;
}
#define NMAX 10 /*Max kol-vo vershin*/
main()
{
int n,j;
int *dcmin;
int g[NMAX][NMAX];
int cmin[j];
for(j=0;j<n;j++)
{
printf("Kratchaishiy cikl:");
printf(" %d ", cmin[j]);
printf("\n\n");
printf("******************************\n");
VvodGrafa(g,n);
Pminc(g,n,dcmin,cmin);
getch();
}
}