parcurgere graf in adancime recursiv

Sa se parcurga in adancime DF un graf orientat.

Graful este dat prin matricea de adiacenta.

#include<fstream.h>
#include<iostream.h>
int v[20],a[20][20],n;
void citire()
{
int i,j;
fstream f(“matrice.txt”,ios::in);
f>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f>>a[i][j];
}
void df(int nod)
{
int k;
cout<<nod<<” “;
v[nod]=1;
for(k=1;k<=n;k++)
if((a[nod][k]==1) && (v[k]==0))
df(k);
}
void main()
{
citire();
df(1);
}

{joscommentenable}

Descompunerea in componente tare conexe a unui graf orientat

Descompunerea in componente tare conexe a unui graf orientat, dat prin matricea de adiacenta

Matricea de adiacenta se citeste dintr-un fisier text

#include <fstream.h>
int s[20],p[20],a[20][20],n,nr,i,j;
void df1(int nod)
{
int k;
s[nod]=nr;
for(k=1;k<=n;k++)
if ((a[nod][k]==1) && (s[k]==0))
df1(k);
}
void df2(int nod)
{
int k;
p[nod]=nr;
for(k=1;k<=n;k++)
if((a[k][nod]==1) && (p[k]==0))
df2(k);
}
void main()
{
fstream f(“grafo.txt”,ios::in);
f>>n;
while(f>>i>>j) a[i][j]=1;
f.close();
nr=1;
for (i=1;i<=n;i++)
if (s[i]==0)
{
s[i]=nr;
df1(i);df2(i);
for(j=1;j<=n;j++)
if (s[j]!=p[j]) s[j]=p[j]=0;
nr++;
}
for(i=1;i<=n;i++)
{
cout<<“componenta “<<i<<endl;
for(j=1;j<=nr;j++)
if(s[j]==1) cout<<j<<” “;
cout<<endl;
}
}

{joscommentenable}

Descompunerea in componente conexe a unui graf neorientat

Descompunerea in componente conexe a unui graf neorientat, dat prin matricea de adiacenta

grafneorientatcompconexe

#include<fstream.h>
int s[20],a[20][20],n,i,j,k;

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

void main()
{
fstream f(“graf.txt”,ios::in);
f>>n;
while(f>>i>>j) a[i][j]=1;
f.close();
k=1;
for(i=1;i<=n;i++)
 if(s[i]==0)
 {
 cout<<“componenta “<<k<<endl;
 df(i);
 cout<<endl;
 k++;
 }
}

{joscommentenable}

graf orientat tare conex

 

Graf orientat tare conex

 

#include<fstream.h>
#include<conio.h>
int s[50],a[50][50],n,suc[50],pred[50],i,j;
void citire(char fis[20],int a[50][50],int&n)
{
fstream f(fis,ios::in);
int i,j;
f>>n;
while(f>>i>>j) a[i][j]=1;
f.close();
}

void df1 (int nod)
{
int k;
suc[nod]=i;

for (k=1;k<=n;k++)
if ((a[nod][k]==1) && (suc[k]==0))
df1(k);
}
void df2(int nod)
{
int k;
pred[nod]=i;
for (k=1;k<=n;k++)
if((a[k][nod]==1)&&(pred[k]==0))
df2(k);
}
void main()
{
citire(“fis.txt”,a,n);
cout<<“nodul de pornire:”;cin>>i;
suc[i]=pred[i]=i;
df1(i);df2(i);
for(j=1;j<=n;j++)
if((suc[j]==pred[j])&&(suc[j]==i))
cout<<j<<” “;
getch();
}

{joscommentenable}

parcurgere graf in latime bf

Sa se parcurga un graf graf in latime (BF)

 

 

#include<fstream.h>
#include<conio.h>
struct nod
{
int inf;
nod* adr;
};

nod* l[20];
int c[20],s[20],i,sf,n;

void citire(char fisier[10],nod*l[20],int& n)
{nod* p;
int i,j;
fstream f(fisier,ios::in);
f>>n;
for(i=1;i<=n;i++) l[i]=0;
while(f>>i>>j)
{p=new nod;
p->adr=l[i];
p->inf=j;
l[i]=p;
}
f.close();
}

void bf()
{
nod* p;
if(i<=sf)
{
p=l[c[i]];
while(p)
{
if(s[p->inf]==0)
{sf++;
c[sf]=p->inf;
s[p->inf]=1;
}
p=p->adr;
}
i++;
bf();
}
}

void main()
{
citire(“graf.txt”,l,n);
i=1;sf=1;c[i]=1;s[1]=1;
bf();
for(int i=1;i<=sf;i++) cout<<c[i]<<” “;
cout<<endl;
getch();
}

{joscommentenable}

graf hamiltonian

Sa se verifice daca un graf este hamiltonian

Fiind dat un graf neorientat memorat prin matricea de adiacenta sa se determine daca graful este Hamiltonian sau nu.

Notiuni teoretice

Definitie: Se numeste ciclu hamiltonian un ciclu elementar care trece prin toate varfurile grafului

Definitie: Un graf care admite un ciclu hamiltonian se numeste graf hamiltonian

#include<fstream.h>

int st[100],n,m,k,a[20][20];

int ns;

int e_valid()

{if(k>1)

if(!a[st[k-1]][st[k]])

return 0;

else

for(int i=1;i<=k-1;i++)

if(st[i]==st[k])

return 0;

if(k==n)

if(!a[st[1]][st[k]])

return 0;

return 1;

}

void afisare()

{for(int i=1;i<=n;i++)

cout<<st[i]<<” “;

cout<<st[1];

k=0;

ns++;

}

void back()

{k=1;

while(k>0)

if(st[k]<n)

{st[k]++;

if(e_valid())

if(k==n)

afisare();

else

{k++;

st[k]=0;}

}

else

k–;

}

void main()

{

fstream f;

f.open(“hamiltonian.in”,ios::in);

int u,v;

if(f)

cout<<“ok!”;

else

cout<<“eroare”;

cout<<endl;

f>>n>>m;

for(int i=1;i<=m;i++)

{f>>u>>v;

a[u][v]=a[v][u]=1;

}

cout<<“matricea de adiacenta “<<endl;

for( i=1;i<=n;i++)

{for(int j=1;j<=n;j++)

cout<<a[i][j]<<” “;

cout<<endl;

}

back();

if(ns==0)

cout<<”nu exista solutii”;

}

{joscommentenable}

subgraf

Subgraf

Se citesc 2 grafuri neorientate, unul cu n noduri si m muchii, iar celalalt cu k varfuri si l muchii, ambele date prin vectorul muchiilor. Sa se determine daca al doilea graf este subgraf al primului.

#include<fstream.h>
fstream f(“date.in”,ios::in);
fstream g(“date2.in”,ios::in);

int a[100][100],b[100][100],n,m,k,l;
void citire()
{int x,y,i;
f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=1;
a[y][z]=1;
}
g>>k>>l;
for(i=1;i<=l;i++)
{g>>x>>y;
b[x][y]=1;
b[y][x]=1;
}
}

int subgraf()
{for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
if(a[i][j]!=b[i][j]) return 0;
return 1;
}

void main()
{citire();
if(subgraf()) cout<<“da”;
else cout<<“nu”;
}

{joscommentenable}

roy floyd-grafuri orientate

#include<fstream.h>
#include<conio.h>
const float pinf=1.e20;
float a[50][50];
int n;

void citire(char nume[20],float a[50][50],int& n)
{
int i,j;
float c;
fstream f(nume,ios::in);
f>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (i==j) a[i][j]=0;
else a[i][j]=pinf;
while(f>>i>>j>>c) a[i][j]=c;
f.close();
}

void drum(int i,int j)
{
int k=1,gasit=0;
while ((k<=n) && !gasit)
{
if ((i!=k) && (j!=k) && (a[i][j]==a[i][k]+a[k][j]))
{
drum(i,k);drum(k,j);
gasit=1;
}
k++;
}
if (!gasit) cout<<j<<” “;
}

void tipar(int nodi,int nodf)
{
if (a[nodi][nodf]<pinf)
{
cout<<“drumul de la “<<nodi<<” la “<<nodf<<” are lungimea “
<<a[nodi][nodf]<<endl;
cout<<nodi<<” “;
drum(nodi,nodf);
}
else
cout<<“nu exista drum”;
}

void lungime()
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
}

void main()
{
citire(“ponderi.txt”,a,n);
lungime();
tipar(4,2);
getch();
}

{joscommentenable} 

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}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

parcurgere in latime bf recursiv

#include<fstream.h>
#include<conio.h>
struct nod
{int inf;
nod* adr;
};

nod* l[20];
int c[20],s[20],i,sf,n;

void citire(char fisier[20],nod* l[20],int& n)
{nod* p;
int i,j;
fstream f(fisier,ios::in);
f>>n;
for(i=1;i<=n;i++) l[i]=0;
while(f>>i>>j)
{p=new nod;
p->adr=l[i];
p->inf=j;
l[i]=p;
}
f.close();
}

void bf()
{nod* p;
if(i<=sf)
{
p=l[c[i]];
while(p)
{
if(s[p->inf]==0)
{sf++;
c[sf]=p->inf;
s[p->inf]=1;}
p=p->adr;
}
i++;
bf();
}
}

void main()
{
citire(“graf.txt”,l,n);
i=1;sf=1;c[1]=1;s[1]=1;
bf();
for(int i=1;i<=sf;i++) cout<<c[i]<<” “;
cout<<endl;
getch();
}

{joscommentenable}