Acasa Tehnologie Componente conexe intr-un graf

Componente conexe intr-un graf

by Dragos Schiopu

>Componente conexe intr-un graf

//ptr un varf k, se ia linia si coloana k din matricea drumurilor
//si se face intersectia=>comp conexa
#include <stdio.h>
#include <conio.h>

int min(int a, int b)
{
if(a<=b) return a;
else return b;
}

void main()
{
int i,j,k,n,a[20][20],linie[20],coloana[20],v,nr;
FILE *f=fopen("c:date.txt","r");

//se citeste nr de varfuri din fisier text
fscanf(f,"%d",&n);

//se citeste matricea de adiacenta
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
fscanf(f,"%d",&a[i][j]);
fclose(f);

//se calculeaza matricea drumurilor folosind Roy-Warshall
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if((a[i][j]==0)&&(i!=k)&&(j!=k)) a[i][j]=min(a[i][k],a[k][j]);

//afisare matricea drumurilor
printf("Matricea drumurilor este:n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf(" %d ",a[i][j]);
printf("n");
}

//se citeste varful
printf("Dati v:");
scanf("%d",&v);

//se copiaza elem de pe linia v nevide succesorii vf v
for(i=1;i<=n;i++)
if(a[v][i]==1) linie[i]=i; else linie[i]=0;

//se copiaza elem de pe linia v nevide predecesorii vf v
for(i=1;i<=n;i++)
if(a[i][v]==1) coloana[i]=i; else coloana[i]=0;

printf("componenta conexa ce contine varful %d este: ",v);
nr=0;

//se face intersectia si se afeseaza comp conexa
for(i=1;i<=n;i++)
if((coloana[i]!=0)&&(linie[i]!=0)&&(coloana[i]==linie[i]))
{
printf("%d ",linie[i]);
nr++;
}
if(nr==0) printf("%d",v);
getch();
}

s-ar putea sa-ti placa