graf eulerian

Graf eulerian

#include<fstream.h>
#include<conio.h>
struct nod
{
int nd;
nod *adr_urm;
};
int a[10][10],s[10],n;
nod *lista, *indice;

void citire(char graf[10],int a[10][10],int& n)
{int i,j;
fstream f(graf,ios::in);f>>n;
while (f>>i>>j) a[i][j]=a[j][i]=1;
f.close();
}

void ciclu(nod* v)
{int nodul;
nod *nod_baza,*nod_gasit,*nod_urm;
nod_urm=v->adr_urm;
nod_baza=v;
do
{ nodul=1;
while (a[nod_baza->nd][nodul]==0) nodul++;
a[nod_baza->nd][nodul]=0;a[nodul][nod_baza->nd]=0;
nod_gasit=new nod;nod_gasit->nd=nodul;
nod_gasit->adr_urm=0;
nod_baza->adr_urm=nod_gasit;nod_baza=nod_gasit;
}while (nod_gasit->nd!=v->nd);
nod_baza->adr_urm=nod_urm;
}

int adauga()
{
int i,gasit=0;
indice=lista;
while(indice && !gasit)
{
for(i=1;i<=n;i++)
if (a[indice->nd][i]==1) gasit=1;
if (!gasit) indice=indice->adr_urm;
}
if(indice)
{ciclu(indice);
return 1;}
else return 0;
}

int grade_pare()
{
int i=1,j,s,gasit=0;
while ((i<=n) && !gasit )
{
s=0;
for(j=1;j<=n;j++) s+=a[i][j];
if (s%2) gasit=1;
i++;
}
return !gasit;
}

void df(int nod)
{
int k;
s[nod]=1;
for(k=1;k<=n;k++)
if ((a[nod][k]==1) && (s[k]==0)) df(k);
}

int conex()
{
int gasit=0,i;
df(1);
for(i=1;i<=n;i++)
if (s[i]==0) gasit=1;
return !gasit;
}

void main()
{
citire(“graf1.txt”,a,n);
if (conex())
if (grade_pare())
{
lista=new nod;
lista->nd=1;lista->adr_urm=0;
while (adauga());
indice=lista;
while (indice)
{ cout<<indice->nd<<” “;
indice=indice->adr_urm;
}
}
else cout<<“nu par”;
else cout<<“nu conex”;
getch();
}

{joscommentenable}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Facebook Comments