Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateC
C sharpCalculatoareCorel drawDot netExcelFox pro
FrontpageHardwareHtmlInternetJavaLinux
MatlabMs dosPascalPhpPower pointRetele calculatoare
SqlTutorialsWebdesignWindowsWordXml

ALGORITMICA GRAFURILOR

calculatoare

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Proceduri. Programe.
STUDIUL TEHNOLOGIILOR INFORMATICE DE INTEGRARE A APLICATIILOR
Administrarea unei instante Oracle9I
CONTROLERE LOGICE PROGRAMABILE
Algoritmi si scheme logice
Unelte de administrare a bazei de date Oracle9I
Intretinerea fisierelor de control Oracle9I
Administrarea datelor Undo Oracle9I
Simulari test grila
Crearea unei baze da date Oracle9I

ALGORITMICA GRAFURILOR



Cuprins

1. LABORATOR 1. 2

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

2. LABORATOR 2. 4

2.1. Citirea unui graf. 4

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

3. LABORATOR 3. 6

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

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

3.3. Determinati vecinii unui varf al unui graf. 8

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

3.5. 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

3.6. Verificati daca un graf este simetric/antisimetric. 11

4. LABORATOR 4. 12

4.1. Determinati daca doua grafuri sunt izomorfe. 12

5. LABORATOR 5. 14

5.1. Algoritmul Roy-Warshall. 14

5.2. Algoritmul Roy-Floyd.. 14

5.3. Algoritmul lui Dijkstra.. 16

6. LABORATOR 6. 18

6.1. Algoritmul Bellman-Ford.. 18

6.2. Algoritmul lui Prim 19

6.3. Algoritmul lui Kruskal. 20

7. Laborator 7. 24

7.1. Colorararea secventiala a unui graf. 24

7.2. Colorarea secventiala(algoritmul Larger First) 25

8. LABORATOR 8. 28

8.1. Algoritmul Ford-Fulkerson.. 28

1.    LABORATOR 1

1.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)

2.    LABORATOR 2

2.1.                     Citirea unui graf

# include <stdio.h>

# include <conio.h>

void main(void)

getch();



}

2.2.                     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();

}

3.    LABORATOR 3

3.1.                     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();

}

3.2.                     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();

}

3.3.                     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();

}

3.4.                     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();

}

3.5.                     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();

}

3.6.                     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();

}

4.    LABORATOR 4

4.1.                     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();

}

5.    LABORATOR 5

5.1.                     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();

}

5.2.                     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();

}

5.3.                     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();

}

6.    LABORATOR 6

6.1.                     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();

}

6.2.                     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();

}

6.3.                     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();

}

7.    Laborator 7

7.1.                     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();

}

7.2.                     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();

}

8.    LABORATOR 8

8.1.                     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();

}








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1283
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site