Aplicatii

1.Reprezentarea grafurilor cu ajutorul matricei de adiacenta.

Se citesc n, numarul nodurilor, si m, numarul muchiilor unui graf, de la tastatura. Se citesc, de asemenea, pe rand, m perechi de numere cu valori cuprinse intre 1 si n,reprezentand muchiile grafului.Sa se memoreze graful cu ajutorul matricei de adiacenta si sa se afiseze matricea .

#include

#define max 10

void citire(int &n, int a[max][max]);

void afisare(int n, int a[max][max]);

void initializare(int a[max][max]);

void main()

{int a[max][max], n; //a-matricea de adiacenta,n-nr noduri

initializare(a) ;

citire(n,a) ;

afisare(n,a);

}

void initializare(int a[max][max]) // initializarea matricei

{int i,j;

for(i=0;i

for(j=0;j

a[i][j]=0;

}

void citire(int &n, int a[max][max]) //construirea matricei de adiacenta

{int x,y,i,m;

cout<< ‘‘n=’’ ;cin>>n ;

cout<< ‘‘m=’’ ;cin>>m ; // m-nr muchii

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

{cout<< “muchia”<

cin>>x>>y;

a[x][y]=1;

a[y][x]=1; //construim matricea simetrica

}

}

void afisare(int n, int a[max][max]) //afisarea matricei de adiacenta

{int i,j ;

cout<<’’Matricea de adiacenta :’’<

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

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

cout<

cout<

}

}

2.Reprezentarea grafului cu ajutorul listelor de adiacenta .

#include

#define max 10

void citire(int &n, int l[max][max]);

void afisare(int n, int l[max][max]);

void initializare(int l[max][max]);

void main()

{int a[max][max], n; //l-matricea de adiacenta,n-nr noduri

initializare(l) ;

citire(n,l) ;

afisare(n,l);

}

void initializare(int l[max][max])

{int i,j;

for(i=0;i

for(j=0;j

a[i][j]=0;

}

void citire(int &n, int l[max][max])

{int x,y,i,m;

cout<< ‘‘n=’’ ;cin>>n ; //n-nr nodurilor

cout<< ‘‘m=’’ ;cin>>m ; // m-nr muchii

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

{cout<< “muchia”<

cin>>x>>y; //citim doua noduri adiacente

i[x][0]++; //indicele de sfarsit a l listei nodului x

i[y]l[x][0]]=y; //element in lista nodului x

i[y][0]++ ; //indicele de sfarsit al listei nodului y

i[y][1[y][0]]=x ; //element in lista nodului x

}

}

void afisare(int n, int l[max][max])

{int i,j ;

cout<<’’Matricea de adiacenta :’’<

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

{cout<<’’nodul’’<

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

cout<

cout<

}

}

3.Reprezentarea grafurilor in memorie folosind lista muchiilor.

#include

#define max 10

Struct muchie //structura pentru memorarea unei muchii

{intx,y;

};

Muchie e[max]; //vectorul de muchii

int n,m ;

void citire() ;

void afisare() ;

void main()

{citire() ;

afisare() ;

}

void citire()

{int x,y,i ;

cout<<’’n=’’;cin>>n;

cout<<’’m=’’ ;cin>>m ; //m-nr muchii

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

{cout<<’’muchia’’<<<’’:’’;

cin>>x>>y;

e[i].x=x //memoreaza un capat al muchiei

e[i].y=y //memoreaza al doilea capat al muchiei

}

}

void afisare()

{int i,j;

cout<<’’Graful are’’<

cout<<’’Muchiile grafului:”<

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

cout<

}

Category: 0 comentarii

Niciun comentariu:

Trimiteți un comentariu