Probleme Algoritmica Grafurilor

8/3/2019 Probleme Algoritmica Grafurilor

1/28

Student:Pruna Marian

Profesor Indrumator:Toader Florentina

Specializare:Informatica

Grupa:4138,An II

Pag 1 / 28


2/28

Probleme de nota 5-6

sub1. Fie G un graf orientat si A o submultime de varfuri . Determinati multimea arcelor

incidente cu A catre exterior si multimea arcelor incidente cu A catre interior.

#include

#include

void main (void)

{

int n,i,j,a[20][20], A[20];

FILE *f;

clrscr();

f=fopen("mat.txt","r");

fscanf(f,"%d",&n);for(i=1;i


3/28

sub2. Fie G un graf.Gradul minim, maxim, mediu.

#include

#include

void main (void)

{

int n,i,j,a[20][20],grad[20],min,max;

float mediu;

FILE *f;

clrscr();


fscanf(f,"%d",&n);for(i=1;i


4/28

int n,i,j,a[20][20],ok1,ok2;

FILE *f;

clrscr();


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

for(i=1;i


5/28

printf("%4d",a[i][j]);

printf("\n");

}

ok1=1;

int k;

for(i=1;i


6/28

else printf("Graful nu este %d-graf",p);

getch();

}

sub6.Tipul grafului:graf turneu.

#include

#include

void main (void)

{

int n,i,j,a[20][20],ok1=1,ok2=1,ok3=1;

FILE *f;

clrscr();


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

for(i=1;i


7/28

clrscr();


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

for(i=1;i


8/28

if(a[i][j]==1) nr++;

grad[i]=nr;

}

for(i=1;i


9/28

if(!ok) printf("graful nu e tare conex");

else

printf("graful e tare conex");

getch();

}

sub10.Tipul grafului: cvasi-tare conex

#include"stdio.h"

#include"conio.h"

int a[10][10],n,i,j,k,ok=1;

FILE *f;

void main(void)

{

clrscr();


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

for(i=1;i


10/28

sub11.Algoritmi pentru determinarea drumurilor intr-un graf

Algoritmul Roy-Warshall */

#include"stdio.h"

#include"conio.h"

void main(void)

{

int a[10][10],n,j,i,k,b[10][10];FILE *f;

clrscr();


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

for(i=1;i


11/28

for(i=1;i


12/28

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

if (ok2) printf("\n Muchia %d-%d nu este critica",x,y);

else printf("\n Muchia %d-%d este critica",x,y);

}

getch();

}

sub13.Determinati daca un varf intr-un graf neorientat conex este critic

#include

#include

void main (void)

{

int n,i,j,a[20][20],k;

FILE *f;

clrscr();


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

for(i=1;i


13/28

for(i=1;i


14/28

printf("%d ",a[i][j]);

}

}

int min(int x,int y)

{

if(x


15/28

sub15. Algoritmul pentru determinarea distantei minime intr-un graf : Roy-Floyd

#include"stdio.h"

#include"conio.h"

void main(void)

{

int a[10][10],n,j,i,k;

FILE *f;clrscr();


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

for(i=1;i


16/28

citire_matrice(m);

printf("\n");

scriere_matrice(m);

printf("\n");

for(i=1;i


17/28

nod=i;

}

if(min==inf) break;

u[nod]=1;

for(i=1;id[nod]+m[nod][i])

{

d[i]=d[nod]+m[nod][i];

pred[i]=nod;

}

}

}

sub17. Algoritmul pentru determinarea distantei minine intr-un graf : Beldman-Ford

#include

#include

void main(void)

{

int a[20][20],i,j,s,n,d[20],u,v;

FILE *f;

clrscr();


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

for(i=1;i


18/28

else

for (i=1;i


19/28

if(v[i]==0)

{

s=i;

break;

}

nr++;

printf("componenta conexa %3d este", nr);

for(j=1;j


20/28

}

int eulerian(int varfuri[20],int m,int a[20][20])

{

int ok,i;

ok=1;

for(i=1;i


21/28

for (i=1;i


22/28

int i,j,min,l,col;

min=999;

for (i=1;i


23/28

for(i=1;i


24/28

clrscr();

citire_matrice(a);

printf("\n");

scriere_matrice(a);

printf("\n");

printf("nodul de start este=");scanf("%d",&x);

prim(x);

getch();

}

sub22. Algoritmul de gasire a arborilor de cost minim intr-un graf: Krushal

#include

#include

typedef struct muchie_min

{

int coloana;

int linie;

} muchie_min;

int a[30][30], t[30][30],n, k, ok, v[30], w[30];

void initializare(int w[30])

{

int i;

for( i=1;i1 && t[w[k]][w[k-1]]==0 || t[w[k]][w[k-1]]==999)

return 0;

for(i=2;i


25/28

}

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

{

int i,j;

for(i=1;i


26/28

{

x=minim(a,n).linie;

y=minim(a,n).coloana;

t[x][y]=a[x][y];

t[y][x]=t[x][y];

if(i>2)

{

ok=0;

bktr(1,y);

if(ok==1)

{

t[x][y]=0;

t[y][x]=0;

k++;}

}

a[x][y]=a[y][x]=999;

}printf("\n Arborele de cost minim este: \n");

afisare(t,n);

getch();

}

sub23.Algoritmul pentru colorarea grafului : Greedy

#include

#include

void main (void)

{

int n,a[20][20],F[20],nr,c1[20],o[20],i,j,min;

FILE *f;

clrscr();


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

for(i=1;i


27/28

printf("o[%d]=",i);scanf("%d",&o[i]);

F[i]=0;

}

F[1]=1;

printf("\n Numarul de culori disponibile: "); scanf("%d",&nr);

c1[1]=0;

for(i=2;i


28/28

{

for(j=1;j

Probleme Algoritmica Grafurilor

Documents

Transcript of Probleme Algoritmica Grafurilor