ALGORITMICA GRAFURILOR

ALGORITMICA GRAFURILOR

Cuprins

LABORATOR 1 2

Crearea unui arbore binar si parcurgerea sa prin cele 3 forme: RSD, SRD,SDR 2

LABORATOR 2 4

Citirea unui graf 4

Obtinerea dintr-un graf a unui alt graf prin contractie. 4

LABORATOR 3 6

Avand dat un graf,determinati un subgraf al sau. 6

Avand dat un graf,determinati un graf partial al sau. 6

Determinati vecinii unui varf al unui graf. 8

Determinati gradele varfurilor unui graf,gradul minim si gradul maxim. 8

Determinati w⁺(A)-multimea arcelor incidente cu A catre exterior, w^- (A)-multimea arcelor incidente cu A catre interior si vecinii lui A, unde A este o submultime de varfuri ale grafului. 10

Verificati daca un graf este simetric/antisimetric. 11

LABORATOR 4 12

Determinati daca doua grafuri sunt izomorfe. 12

LABORATOR 5 14

Algoritmul Roy-Warshall 14

Algoritmul Roy-Floyd 14

Algoritmul lui Dijkstra 16

LABORATOR 6 18

Algoritmul Bellman-Ford 18

Algoritmul lui Prim 19

Algoritmul lui Kruskal 20

Laborator 7 24

Colorararea secventiala a unui graf 24

Colorarea secventiala(algoritmul Larger First) 25

LABORATOR 8 28

Algoritmul Ford-Fulkerson 28

LABORATOR 1

Crearea unui arbore binar si parcurgerea sa prin cele 3 forme: RSD, SRD,SDR

# include <stdio.h>

# include <conio.h>

# include <alloc.h>

# include <ctype.h>

typedef struct arbore

arbore;

arbore *creare(void)

else return NULL;

void RSD(arbore *a)

void SRD(arbore *a)

void SDR(arbore *a)

void main(void)

LABORATOR 2

Citirea unui graf

# include <stdio.h>

# include <conio.h>

void main(void)

getch();

Obtinerea dintr-un graf a unui alt graf prin contractie.

# include <stdio.h>

# include <conio.h>

void main(void)

printf('n dati nodurile pe care doriti sa le uniti:');

scanf('%d',&x);

scanf('%d',&y);

if(a[x][y]==0) printf('n nu se poate face contractarea!');

else

else

if (i==x)

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

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

a[i][j]=a[i+1][j];

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

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

a[i][j]=a[i][j+1];

n=n-1;

printf('n matricea de adiacenta corespunzatoare noului graf este:n');

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

}

getch();

LABORATOR 3

Avand dat un graf,determinati un subgraf al sau.

# include <stdio.h>

# include <conio.h>

void main(void)

printf('n cate varfuri doriti sa eliminati?');

scanf('%d',&m);

printf('introduceti cele %d varfuri:',m);

for(i=1;i<=m;i++) scanf('%d',&v[i]);

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

printf('subgraful rezultat are %d varfuri,matricea sa fiind:n',n);

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

getch();

Avand dat un graf,determinati un graf partial al sau.

# include <stdio.h>

# include <conio.h>

void main(void)

printf('n pt a abtine un graf partial trebuie sa eliminati anumite arce!!');

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

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

}

printf('n graful partial obtinut are matricea de adiacenta:n');

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

/*am prezentat cazul grafului orientat. In cazul grafului neorientat algoritmul ar fi:

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

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

}*/

getch();

Determinati vecinii unui varf al unui graf.

# include <stdio.h>

# include <conio.h>

void main(void)

printf('dati varful ai carui vecini doriti sa-i aflati:');

scanf('%d',&x);

k=0;

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

if (a[i][x]==1 || a[x][i]==1)

printf('n vecinii lui %d sunt:',x);

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

printf('%d ',v[i]);

getch();

Determinati gradele varfurilor unui graf,gradul minim si gradul maxim.

# include <stdio.h>

# include <conio.h>

struct semigrad

semigrad[50];

int minim(int v[50],int n)

int maxim(int v[50],int n)

void main(void)

for(i=1;i<=n;i++) grad[i]=0;

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

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

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

printf("n gradul minim este %d,iar gradul maxim este %d!",minim(grad,n),maxim(grad,n));

getch();

Determinati w⁺(A)-multimea arcelor incidente cu A catre exterior, w^- (A)-multimea arcelor incidente cu A catre interior si vecinii lui A, unde A este o submultime de varfuri ale grafului.

# include <stdio.h>

# include <conio.h>

int in(int v[50],int n,int x)

void main(void)

printf('n cate elemente are submultimea de varfuri A?');

scanf('%d',&m);

printf('n dati cele %d elemente ale submultimii de varfuri A:',m);

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

scanf('%d',&A[i]);

printf('n multimea w_plus(A) este:');

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

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

if (a[A[i]][j]==1 && in(A,m,j)==0) printf('(%d,%d);',A[i],j);

printf('n multimea w_minus(A) este:');

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

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

if (a[i][A[j]]==1 && in(A,m,i)==0) printf('(%d,%d);',i,A[j]);

printf('n multimea vecinilor lui A este:');

k=0;

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

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

if ((a[A[i]][j]==1 || a[j][A[i]])&& ((in(A,m,j)==0)))

if (in(v,k,j)==0)

for(i=1;i<=k;i++) printf('%d ',v[i]);

getch();

Verificati daca un graf este simetric/antisimetric.

# include <stdio.h>

# include <conio.h>

void main(void)

ok=1;

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

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

if (a[i][j]!=a[j][i]) ok=0;

if (ok==1) printf('n graful este simetric!');

else printf('n graful nu este simetric!');

ok=1;

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

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

if (a[i][j]==1 && a[j][i]==1) ok=0;

if (ok==1) printf('n graful este antisimetric!');

else printf('n graful nu este antisimetric!');

getch();

LABORATOR 4

Determinati daca doua grafuri sunt izomorfe.

# include <stdio.h>

# include <conio.h>

int a[25][25],st[25],n,m,t,b[25][25];

void initializare(void)

int i,j;

FILE *f;

f=fopen('graf.txt','r');

fscanf(f,'%d',&n);

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

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

fscanf(f,'%d',&a[i][j]);

printf('primul graf are %d noduri,matricea sa de adicaenta fiind:n',n);

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

fscanf(f,'%d',&m);

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

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

fscanf(f,'%d',&b[i][j]);

printf('al doilea graf are %d noduri,matricea sa de adiacenta fiind:n',m);

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

fclose(f);

t=0;

for(i=1;i<25;i++) st[i]=0;

printf('%d %dn',n,m);

void tipar(int k)

int valid(int k)

void bktr(int k)

void main(void)

getch();

LABORATOR 5

Algoritmul Roy-Warshall

# include <stdio.h>

# include <conio.h>

int min(int a,int b)

void main(void)

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]);

printf('n matricea drumurilor este:n');

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

getch();

Algoritmul Roy-Floyd

# include <stdio.h>

# include <conio.h>

int min(int a,int b)

void afisare(int a[50][50],int n)

void main(void)

printf('n matricea drumurilor directe este:n');

afisare(m,n);

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

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

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

if (i!=k && j!=k && i!=j)

m[i][j]=min(m[i][j],m[i][k]+m[k][j]);

printf('n matricea distantelor minime este :n');

afisare(m,n);

getch();

Algoritmul lui Dijkstra

#include <stdio.h>

#include <conio.h>

#include <values.h>

#include <alloc.h>

typedef struct set

set;

int d[50];

int min(set *s)

return t;

set *stergere(set *s,int inf)

}

return s;

void main(void)

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

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

if (i==j) m[i][j]=0;

else

if (a[i][j]==0) m[i][j]=10000;

else

printf('dati varful de start :');

scanf('%d',&x);

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

if (i==x) d[i]=0;

else d[i]=10000;

s=NULL;q=NULL;

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

while(q!=NULL)

printf('vectorul d este:n');

for(i=1;i<=n;i++) printf('%d ',d[i]);

getch();

LABORATOR 6

Algoritmul Bellman-Ford

# include <stdio.h>

# include <conio.h>

void main(void)

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

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

if (i==j) m[i][j]=0;

else

if (a[i][j]==0) m[i][j]=1000;

else

printf('n matricea drumurilor directe este:n');

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

printf('s=');

scanf('%d',&s);

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

if (s==i) d[i]=0;

else d[i]=10000;

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

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

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

printf('vectorul d este:');

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

printf('%d ',d[i]);

getch();

Algoritmul lui Prim

# include <stdio.h>

# include <conio.h>

# include <values.h>

typedef struct min

min;

int n,a[50][50],m[50][50];

void afisare(int a[50][50],int n)

int in(int v[50],int n,int x)

min minim(int v[50],int k)

return min0;

void main(void)

else

printf('n matricea costurilor este :n');

afisare(m,n);

printf('introduceti un nod v (1<=v<=%d)',n);

scanf('%d',&v);

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

for(j=1;j<=n;j++) t[i][j]=0;

k=1;vec[k]=v;

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

printf('arborele de cost minim rezultat este:n');

afisare(t,n);

getch();

Algoritmul lui Kruskal

# include <stdio.h>

# include <conio.h>

# include <values.h>

typedef struct min

min;

int n,a[50][50],m[50][50],t[50][50],k,ok,v[50],st[50];

void initializare(void)

int valid(int k)

void bktr(int k,int n)

void afisare(int a[50][50],int n)

min  minim(int a[50][50],int n)

return min0;

void main(void)

else

printf('n matricea costurilor este :n');

afisare(m,n);

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

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

t[i][j]=0;

k=0;

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

}

m[x][y]=1000;

m[y][x]=1000;

}

printf('arborele de cost minim este:n');

afisare(t,n);

getch();

Laborator 7

Colorararea secventiala a unui graf

# include <stdio.h>

# include <conio.h>

# include <alloc.h>

void stergere(int v[50],int n,int x)

void afisare(int a[50][50],int n)

int minim(int v[50],int n)

void main(void)

printf('introduceti nr de culori:');

scanf('%d',&k);

for(i=1;i<=k;i++) v[i]=i;

for(i=1;i<=n;i++) f[x[i]]=0;

f[x[1]]=1;

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

if (f[x[i]]==0)

f[x[i]]=minim(v1,k1);

}

printf('varfurile colorate arata astfel:');

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

printf('n varful %d a primit culoarea %d',x[i],f[x[i]]);

getch();

Colorarea secventiala(algoritmul Larger First)

# include <stdio.h>

# include <conio.h>

# include <alloc.h>

typedef struct grad

gr;

void stergere(int v[50],int n,int x)

void afisare(int a[50][50],int n)

int minim(int v[50],int n)

int grad(int a[50][50],int n,int x)

void main(void)

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

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

if(d[j].grad>d[i].grad)

for(i=1;i<=n;i++) x[i]=d[i].varf;

printf('introduceti nr de culori:');

scanf('%d',&k);

for(i=1;i<=k;i++) v[i]=i;

for(i=1;i<=n;i++) f[x[i]]=0;

f[x[1]]=1;

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

if (f[x[i]]==0)

f[x[i]]=minim(v1,k1);

}

printf('varfurile colorate arata astfel:');

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

printf('n varful %d a primit culoarea %d',x[i],f[x[i]]);

getch();

LABORATOR 8

Algoritmul Ford-Fulkerson

# include <stdio.h>

# include <conio.h>

# include <values.h>

struct retea

a[50][50];

int r[50][50],st[50],n,k,min,intrare,iesire,flux,t;

void initializare(void)

int valid(int p)

void tipar(int p)

t++;

}

void bktr(int p)

else bktr(p+1);

}

void main(void)

min=MAXINT;

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

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

if (a[i][j].arc==1)

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

for(j=1;j<=n;j++) r[i][j]=0;

//am initializat matricea reziduala cu 0

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

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

if (a[i][j].arc==1)

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

if (ok==0) intrare=i;

if (ok1==0) iesire=i;

}

do

while(k==1);

flux=0;

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

if (a[intrare][i].arc==1) flux=flux+a[intrare][i].flux;

printf('n fluxul maxim este %d!',flux);

getch();