| CATEGORII DOCUMENTE |
FACULTATEA DE MATEMATICA-INFORMATICA
SPECIALIZAREA INFORMATCA
STRUCTURI DE DATE AVANSATE
Teme Laborator
Daca se doreste inserarea intr-un arbore binar ordonat care se doreste a fii si perfect echilibrat (pentru ca procesul de cautare sa fie cat mai eficient), atunci operatia de inserare se complica foarte mult, incercand sa pastram dupa inserare arbore tot binar ordonat, perfect echilibrat. De aceea oamenii au slabit conditia de perfect echilibrat cerand ca arborele sa fie echilibrat dupa inaltime. Cei care au facut asta au fost Adelson-Velskii si Landis, motiv pentru care arborele echilibrat dupa inaltime se mai numeste si arbore AVL, dupa numele lor. Intr-un arbore AVL lungimea drumului de cautare nu creste considerabil.
Def: Un arbore binar se zice ca e echilibrata dupa inaltime daca diferenta din inaltimea subarborelui stang respective drept pentru fiecare nod al arborelui este cel mult 1. Fiecare subarbore a unui arbore AVL este tot AVL. Un arbore perfect echilibrat este in acelasi timp si echilibrat dupa inaltime. Asadar arborele perfect echilibrate sunt cazuri ai arborilor AVL.
Adelson-Velskii si Landis au demonstrate ca inaltimea unui arbore achilibrat dupa inaltime cu un anumit numar de noduri este cu cel mult 45% mai mare decat inaltimea unui arbore perfect echilibrat cu un numar egal de noduri , prin urmare lungimea drumului de cautare nu creste considerabil iar numarul de comparari de cheie ce se efectueaza in cadrul operatiilor de cautare, inserare, suprimare este tot de ordinul logn in baza 2, unde n-numarul de noduri ale arborelui, ca si in cazul arborelui perfect echilibrat cu aceeasi numar de noduri.
Impementarea AVL se va face ca in cazul arborelui binar.
Tema 1:Crearea si vizualizarea unui arbore binar ordonat in preordine,inordine,postordine cu ajutorul modului grafic:
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <graphics.h>
#include <ctype.h>
#include <dos.h>/*delay*/
#define raza 12
struct nod
;
typedef struct nod Tnod;
typedef Tnod *ref;
ref radacina;
int N,x;
char op;
int timp=1000;
void tip(ref anod, int nivel, int x1, int x2, int c1,int c2,char *s)
/*Tip*/
void inordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
}/*inordine*/
void preordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
}/*preordine*/
void postordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
}/*postordine*/
void initializare(void)
}/*initializare*/
void InArbore(int x, ref *t)
else if (x<(*t)->cheie)
InArbore(x,&((*t)->st));
else
InArbore(x,&((*t)->dr));
} /*InArbore*/
void creare(void)
} /*creare*/
void main(void)
}
break;
case 'P': if (radacina==NULL)
printf('Arborele este vid!n');
else
break;
case 'I': if (radacina==NULL)
printf('Arborele este vid!n');
else
break;
case 'S': if (radacina==NULL)
printf('Arborele este vid!n');
else
break;
case 'E': break;
default: printf('Ati tastat gresit! n');
break;
} /*switch*/
printf('Tastati enter!n');
getch();
} while (op!='E');
}/*main*/
-Lab 2-
Fie R radacina unui arbore si S subarborele stang, D subarbore drept, si presupunem fara a restrange generalitatea dorim sa inseram un nou nod in subarborele D.
In cazul inserarii unui nod in AVL avem 3 cazuri:
Daca inainte de inserare
hs < hd
hs = hd
hs > hd
Dupa inserare
hs = hd - crieteriul de echilibru se imbunatateste
hs > hd - nu se strica criteriul de echilibru
se strica criteriul si trebuie sa echilibram.
Cazul III - daca inainte de inserare, inaltimea subarborelui stang de radacina R era cu 1 mai mare fata de subarborele drept si mai inseram un nod nou in subarborele stang al arborelui R => se strica echilibrul si arborele trebuie reechilibrat.
Cum realizam reechilibrarea
Inserarea nodului cu cheia 9 si 11 in arborele initial (cel cu linie continua), nu ridica probleme de echilibrare, dar inserarea nodurilor 1, 3, 5, 7, strica echilibrul arborelui de radacina 8 si arborele va trebui reechilibrat.
Cazul 1. a.) Inserarea nodului 1 SS (in stanga celui din urma)
Dupa inserarea nodului 1 arborele se dezechilibreaza. Fie p variabile pointer care desemneaza adresa nodului radacinii si p1 variabila pointer care desemneaza adresa radacinii subarborelui sau stang. Si dupa reechilibrare secventa cheia va trebui sa ramana monoton crescator si sa echilibram dupa inaltime. Pentru rechilibrare nodul adresa p1 va deveni nod radacina, iar nodul de adresa p va deveni radacina subarborelui drept al celui de adresa p1, si pentru ca la traversarea in ordine, secventa cheilor sa fie monoton crescatoare, atunci subarborele drept al nodului de adresa p1 => subarborele stang al nodului de adresa p. Dar in momentul reechilibrarii se cunoaste doar valoarea lui p.
Secventa de program care va realize reechilibrarea va fi urmatoarea:
P
P1 = p -> st;
P -> st = p1 -> dr;
P1 -> dr = p;
P = p1.
Cazul 1. b.) inseram nodul 3 SSD (in dreapta celui din urma)
Dupa inserarea nodului 3 arborele se dezechilibreaza, trebuie reechilibrat. Il vom ridica pe nodul p1 pointer ca nod radacina si fostul nod va radacina p deveni radacina subarborelui sau drept pentru ca la traversarea cheilor in ordine, secventele cheilor sa fie monoton crescatoare, locul lui 6 va fii dupa nodul 4, inaintea lui 8, subarborele drept a lui p1 pointer va deveni
Succesiunea de operatii ce va realiza reechilibrarea va fii urmatoarea:
p
p1 = p -> st;
p -> st = p1 -> dr;
p1 -> dr = p;
p = p1;
Cazul 2. a.) Inserarea nodului 5 (SD in stanga celui din urma)
In urma inserarii nodului 5 arborele cu radacina 8 se dezechilibreaza, trebuie sa reechilibram. Fie p variabila pointer a subarborelui stang si p2 care desemneaza radacina subarborelui drept a lui p1 pointer. Vom ridica nodul p2 pointer ca nod radacina intre p1 pointer si p pointer, pentru ca la traversarea in ordine cheia sa fie monoton crescatoare nodul, iar ref. stang a lui *p trebuie sa fie nula, operatie echivalenta cu a face subarborele stang a lui *p cel ce a fost arborele drept al lui *p.
In momentul reechilibrarii se cunoaste doar valoarea lui p, succesiunea de operatii care va descrie reechilibrarea va fi:
P
P1 = p -> st;
P2 = p1 -> dr;
P1 -> dr = p2 -> st;
P -> st = p2 -> dr;
P2 -> st = p1;
P2 -> dr = p;
P = p2;
Cazul 2. b.) Inserarea nodului cu cheia 7 SD (in dreapta celui din urma):
Se constata ca arborele se dezechilibreaza si pentru reechilibrare fie p,
P1 = p -> st; p2 = p1 -> dr
Subarborele drept a lui p2 va deveni subarbore stang a lui *p, iar ref. drept a lui *p1 va deveni nula, lucru echivalent cu a face ca subarborele drept a lui p1 sa devina cel ce a fost subarborele stang a lui p2. Secventa de operatii care va descrie echilibrarea, avem cunoscuta pe p:
P
P1 = p -> st;
P2 = p1 -> dr;
P1 -> dr = p2 -> st;
P -> st = p2 -> dr;
P2 -> st =p1;
P2 -> dr = p;
P = p2.
D. Cazul I DD / Cazul II DS - similar inlocuind ref dreapta cu stanga.
Tema 1 : Crearea, inserarea si vizualizarea naturala a unui arbore binar AVL ordonat in inordine, preordine si postordine :
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <graphics.h>
#include <ctype.h>
#include <dos.h>/*delay*/
#define raza 12
struct nod
typedef struct nod Tnod;
typedef Tnod *ref;
ref radacina;
int N,x,h;
char op;
int timp=1000;
void tip(ref anod, int nivel, int x1, int x2, int c1,int c2,char *s)
/*Tip*/
void inordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
}/*inordine*/
void preordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
}/*preordine*/
void postordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
}/*postordine*/
void initializare(void)
}/*initializare*/
void insertechil(int x, ref *p, int *h)
else
if (x<(*p)->cheie)
else /* cazul II Stanga */
(*p)->ech=0;
*h=0;
break;
} /* switch */
}/*ram. st*/
else
if (x>(*p)->cheie)
else /* cazul II Dreapta */
(*p)->ech=0;
*h=0;
break;
} /* switch */
}
else
} /* insertechil */
void creare(void)
} /*creare*/
void main(void)
}
break;
case 'A': printf('Introduceti cheia noului nod: ');
scanf('%d',&x);
h=0;
insertechil(x,&radacina,&h);
break;
case 'P': if (radacina==NULL)
printf('Arborele este vid!n');
else
break;
case 'I': if (radacina==NULL)
printf('Arborele este vid!n');
else
break;
case 'S': if (radacina==NULL)
printf('Arborele este vid!n');
else
break;
case 'E': break;
default: printf('Ati tastat gresit! n');
break;
} /*switch*/
printf('Tastati enter!n');
getch();
} while (op!='E');
}/*main*/
-Lab 3+4-
Inrtu-cat arborii AVL pe care-i utilizam sunt si arbori binari ordonati, suprimarea intr-un arbore AVL se va face dupa aceleasi principii ca si la arborii binari ordonati.
Cazul cel mai simplu este acela in care nodul de suprimat este un nod frunza sau are cel mult un fiu, cand suprimarea presupune modificarea referintei din nodul parinte al nodului de suprimat care indica nodul de suprimat astfel incat sa indice unicul sau fiu. In cazul in care nodul de suprimat are 2 fii, acesta se va inlocui cu predecesorul acestuia in inordine si apoi vom sterge predecesorul. Singrua problma care apare in plus este ca dupa suprimare arborele sa ramana tot AVL.
Tema1:Suprimarea unui nod intr-un arbore AVL
#include <conio.h>
#include <graphics.h>
#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
#include <ctype.h>
#include <dos.h>
struct nod
typedef struct nod Tnod;
typedef Tnod* ref;
ref radacina;
int raza, timp,x,h=0;
char op,c;
void initializare(void)
}/*initializare*/
void insertechil(int x,ref *p,int *h)
else
if (x<(*p)->cheie)
else /* cazul II S*/
(*p)->ech=0;
*h=0;
break;
}
}/*ramura stanga*/
else
if (x>(*p)->cheie)
else /* cazul II S*/
(*p)->ech=0;
*h=0;
break;
}
}/*ramura dreapta*/
else
}/*intertechil*/
void echilibru2(ref *p,int *h)
else
*p=p1;
}/*cazul 1 st*/
else
else if (p2->ech==0)
else
p2->ech=0;
*p=p2;
}
break;
}/*switch*/
} /*echilibru2*/
void echilibru1(ref *p,int *h)
else
*p=p1;
}/*cazul 1 st*/
else
else if (p2->ech==0)
else
p2->ech=0;
*p=p2;
}
break;
}/*switch*/
} /*echilibru1*/
void suprfd(ref *r,int *h,ref *q)
else
}/*suprfd*/
void supr_echil(int x, ref *p, int *h)
else
if (x < (*p)->cheie)
else
if (x > (*p)->cheie)
else
else
if (q->st == NULL)
else
free(q);
} /* sf suprimare */
} /* sf supr_echil */
void tip(ref anod, int nivel, int x1, int x2, int c1, int c2, char *s)
/*tip*/
void preordine(ref rad, int niv, int x1, int x2, int c1, int c2)
}/*preordine*/
void inordine(ref rad, int niv, int x1, int x2, int c1, int c2)
}/*inordine*/
void postordine(ref rad,int niv,int x1,int x2,int c1,int c2)
}/*postordine*/
void creare(void)
} /*creare*/
void main(void)
break;
case 'A':if (radacina!=NULL)
else printf('Arbore vidn');
break;
case 'B':if (radacina!=NULL)
else printf('Arbore vidn');
break;
case 'P':if (radacina!=NULL)
else printf('Arbore vidn');
break;
case 'I':if (radacina==NULL)
printf('Arbore vid! Creati intai un arbore');
else
break;
case 'S':printf('Introduceti cheia nodului de suprimat: ');
scanf('%d',&x);
h=0;
supr_echil(x,&radacina,&h);
break;
case 'E':break;
default:printf('Optiune gresitan');
}
} while(op!='E');
}/*main*/
-Lab 5-
In vederea prelucrarii unui graf cu ajutorul unei structuri de calcul va trebui sa cunoastem sa tranzitionam sistemul de calcul modul de reprezentare al acestuia, adica asa cum am procedat pentru toate structurile de date avansate, trebuie sa precizam structurile de date concrete ( care au corespondent in caracteristica hardware al sistemului de calcul care le prelucreaza), care va reprezenta structura de date abstract graf. Exista mai multe metode de implementare al TD graf depinzand de not graful si de not operatiilor care urmeaza a fii efectuate asupra SD de tip graf respective. Vom prezenta in cele ce urmeaza doua tehnici de implementare a SD de tip graf, una bazata de SD de tip tablou si alta bazata pe tipul pointer.
Cel mai simplu mod de a reprezenta un graf este prin matricea de adiacenta. Daca avem un graf G=; N=, atunci prin matricea de adiacenta asociata grafului intelegem o matrice de tipul [n * m] de tip boolean cu conditia ca A[x].[y]=TRUE, iar in cazul grafului neorientat avem A[y].[x]=TRUE, daca exista (x,y).
Foarte adesea valorile logice TRUE=1, se inlocuiesc cu FALSE=0
Un graf este precizat prin multimea nodurilor sale si prin multimea arcelor sale. O prima etapa in implementarea unui graf prin matricea de adiacenta este precizarea nodurilor si stabilirea unei corespondente intre multimea nodurilor si indicii lor de acces in matricea de adiacenta. In modul in care e definite matricea de adiacenta => in cazul unui graf neorientat ca ea este o matrice simetrica. Exista posibilitatea ca sa ne definim intr-un graf ca exista nod de la el la el insusi, lucru care se concretizeaza in matrice adiacenta, punand pe true in fiecare element de pe diagonala principala. Asocierea intre multimea nodurilor si intregi, care reprezinta indicile de acces in matricea de adiacenta poate fii facuta implicit (alegand in mod correspondent tipul de baza a multimii nodurilor) sau explicit (prin definirea unei aplicatii pe multimea nodurilor cu valoare in multimea intregilor care reprezinta indici de acces in matricea de adiacenta). Asocierea implicita intre multimea nodurilor si multimea intregilor se poate face simplu denumind nodurile ca intregi, de la 1 la n , sau denumirea nodurilor prin cate o litera, ele fiind litere consecutive din alfabet. Atat in Pascal, cat si in C, exista constructiide limbaj, care realizeaza conversia numelor nodurilor in intregi care reprezinta indici de acces a nodurilor in matricea de adiacenta. In cazul conversiei explicite exista tehnici simple prin care se realizeaza corespondenta: bazata pe tablouri sau pe liste liniare; sau tehnici mai sofisticate bazate pe structuri de tip arbore sau pe metoda dispersiei.
In cele ce urmeaza vom utiliza pentru simplificarea descrierii algoritmului pentru denumirea nodurilor primele litere consecutive din alfabet.
TEMA 1 : Crearea, vizualizarea sub forma naturala a unui graf implementat cu matricea de adiacenta varianta I
#include <stdio.h>
#include <graphics.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#define pi 2*asin(1)
#define R 180
#define r 20
#define maxN 100
int g[maxN][maxN];
char s[2],n1,n2;
int n,a,i,j,k;
void initializare_mod_grafic(void)
}/*initializare_mod_grafic*/
int index(char c)
/*index*/
void desenareNoduri(void)
}/*desenareNoduri*/
void desenareGraf(void)
delay(2000);
closegraph();
}/*desenareGraf*/
void main(void)
printf('Introdu al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
j=index(n2);
while (j<0||j>n-1)
g[i][j]=1;
g[j][i]=1;
xi=x0+R*cos(2*pi*i/n);
yi=y0-R*sin(2*pi*i/n);
xj=x0+R*cos(2*pi*j/n);
yj=y0-R*sin(2*pi*j/n);
setcolor(WHITE);
line(xi,yi,xj,yj);
printf('Mai intr. un arc?(D/N)');
fflush(stdin); scanf('%c',&rasp); rasp=toupper(rasp);
}
closegraph();
desenareGraf();
}/*main*/
-Lab 6-
Presupunem urmatoarele declaratii si tipuri de structuri de date:
#define maxN 100
typedef char TipCheie;
typedef int TipInfo;
typedef strcut
TipEl;
typedef TipEl TipTabel[maxN];
typedef int TipMatAdi[maxN][maxN];
typedef struct
Graf;
typedef struct
TipArc;
Graf g;
TipEl e;
TipArc IndiceArc.
Operatiile care se vor descrie asupra unui graf depend de natura structurii tabloului noduri. Tabloul noduri poate fii ordinat sau neordonat, in primul caz cautarea unui nod in multimea nodurilor se va face printr-o cautare binara, pe cand in cel de-al doilea caz nu poate fii decat o cautare liniara. Daca multimea nodurilor graf nu este ordonata atunci inserarea unui nou nod in graf va presupune, in primul rand incrementarea contorului asociat grafului g, si apoi a pune in tabloul noduri a grafului
g.contor++;
g.Noduri[g.contor-1]=e;
Daca nodul nou de inserat este un nod izolat, atunci inserarea luie in graful g presupune completarea matricii de adiacenta cu o noua linie si coloana.
Inserarea nodului 'E' in graful g ne va conduce la fig.3, va presupune inserarea unei noi linii si unei coloane pe linia si coloana indicate de g.contor-1.
Obs Se poate cosidera in aplicatie ca fiecare nod este conectat cu el insusi, ceea ce inseamna ca toate elementele de pe coloana principala pe 1, acest lucru nu este obligatoriu, el diferind de la caz la caz.
De foarte multe ori in alicatie tipul nodurilor grafului coincide cu tipul cheie, si deci atunci, in alte aplicatii nici macar cheia nodurilor nu trebuie precizata, dar atunci trebuie sa stim numarul nodurilor in vederea asocierii cu indicele lui de acces al nodurilor in matricea de adiacenta.
TEMA 1 :Scrieti programul C care permite efectuarea tuturor operatiilor asupra unui graf implementat prin matricea de adiacenta varianta II.
#include <stdio.h>
#include <conio.h>
#include <graphics.h>
#include <math.h>
#include <process.h>
#include <ctype.h>
#define PI (2*asin(1))
#define r 100
#define PATH 'C:BORLANDCBGI'
#define maxN 20
typedef int TipCheie;
typedef int TipInfo;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[maxN];
typedef int TipMatAdi[maxN][maxN];
typedef int TipContor;
typedef struct
Graf;
typedef struct
TipArc;
Graf g;
TipEl e;
TipArc IndiceArc;
int IndiceNod;
int x0, y0, i, j, n;
void Creare(Graf *);
int CautNod(Graf, TipCheie);
void InserNod(Graf *, TipEl);
void InserArc(Graf *, TipArc);
void SuprimaNod(Graf *, int);
void SuprimArc(Graf *, TipArc);
void asteptare(void);
void initializare_mod_grafic(void);
void afisareGraf(Graf g);
void main(void)
else
afisareGraf(g);
break;
case 'C':
clrscr();
Creare(&g);
break;
case 'I':
clrscr();
if(g.Contor==0)
printf('Introduceti cheia nodului: ');
fflush(stdin); scanf('%c',&e); e = toupper(e);
InserNod(&g,e);
afisareGraf(g);
break;
case 'N':
clrscr();
if(g.Contor==0)
printf('Introduceti nodul de pornire: ');
fflush(stdin);
scanf('%c',&ch); ch = toupper(ch);
if((IndiceArc.lin = CautNod(g,ch)) == -1)
printf('Introduceti nodul de sosire: ');
fflush(stdin);
scanf('%c',&ch); ch = toupper(ch);
if((IndiceArc.col = CautNod(g, ch)) == -1)
InserArc(&g, IndiceArc);
afisareGraf(g);
break;
case 'S':
clrscr();
if (g.Contor>0)
else
}
else
break;
case 'T':
clrscr();
if (g.Contor>0)
else
}
else
break;
default: printf('Ati tastat optiune gresita!n');
break;
}/* switch */
}
while (optiune!='X');
}/* main */
void initializare_mod_grafic(void)
} /* initializare */
int CautNod(Graf g, TipCheie cheie)
/* CautNod */
void InserNod(Graf *g, TipEl e)
g->Arce[g->Contor-1][g->Contor-1]=1;
} /* InserNod */
void InserArc(Graf *g, TipArc IndiceArc)
/* InserArc */
void SuprimaNod(Graf *g, int IndiceNod)
g->Arce[IndiceNod][IndiceNod] = 1;
g->Contor--;
} /* SuprimaNod */
void SuprimArc(Graf *g, TipArc IndiceArc)
/* SuprimArc */
void afisareNoduri(Graf g)
;
int i,xi,yi;
x0 = (getmaxx()/2)+80;
y0 = getmaxy()/2;
for (i=0; i<g.Contor; i++)
setcolor(WHITE);
}/* afisareNoduri */
void afisareGraf(Graf g)
outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');
getch();
closegraph();
}/* afisareGraf */
void Creare(Graf *g)
if (g->Contor!=0)
printf('Introduceti arc?(D/N):');
fflush(stdin);scanf('%c',&c); c = toupper(c);
closegraph();
}/* Creare */
void asteptare(void)
/* asteptare */
LABORATOR 7
TEMA 1:
Scrieti programul C care va va permite calculul inchiderii tranzitive a unei matrici de adiacenta asociate grafului g folosind implementarea grafurilor varianta II 2.
TEMA 2:
Programul C care permite efectuarea tuturor operatiilor asupra unui graf valoric implementat cu matricea de adiacenta varianta II 2. Vizualizarea grafului e sub forma naturala, precum si afisarea raspunsului daca intre 2 noduri date ale drumului exista sau nu un drum.
ANALIZA:
In cadrul implementarii structurii de date de tip garf cu ajutorul matricei de adiacenta cand multimea nodurilor este ordonata inserarea unui nou nod in graf presupune mai intai cautera locului de inserat in tabloul noduri pentru noul nod, dupa care toate nodurile cu indicele de acces mai mare ca acesta vor fi deplasate sper sfarsitul tabloului, urmand sa se insereze natural. Acelasi lucru se intampla si incazul suprimarii unui nod dintr-un graf.
In cazul in care numarul de noduri ale grafului este fix, ceea ce presupune ca vom putea adauga noi arce sau suprima noi arce in structura de date de tip graf, dar nu si noduri atunci tipurile de date folosite si variabilele utilizate prelucrarea structurii de date de tip graf vor constitui varianta II 2 de implementare.
Inchiderea tranzitiva a matricei unui graf
Stim ca un graf este complet definit daca se cunoaste matricea de adiacenta Arce. In implementarea de mai jos vom presupune ca numarul de noduri ale grafului este fix, prin urmare graful este complet definit de matricea de adiacenta Arce. O expresie de forma Arce[i][k] && Arce[k][j] are valoarea true doar daca exista arc de la nodul i la nodul k si respective de la nodul k la nodul j . Aceasta expresia va fi true daca exista un drum de lungime 2 de la nodul cu indexul i la nodul cu indexul j. Daca luam in considerare acest lucru o expresie de forma
(Arce[i][1]&&Arce[1][j])||(Arce[i][2] && Arce[2][j])||.||(Arce[i][NrNoduri]&& Arce[NrNoduri][j]) este true daca cel putin una din expresiile din paranteze este true, deci daca avem cel putin un drum de lungime 2 de la nodul i la nodul j.
Notam Arce2 produsul logic al matricei Arce cu ea insasi, deci Arce2[i][j] are valoarea true daca exista un drum de lungime 2 de la nodul i la nodul j.
Exemplu:
Fie graful de mai jos:
A B C D E
0 0 1 1 0 A 0 0 0 1 1
0 0 1 0 0 B 0 0 0 1 1
Arce= 0 0 0 1 1 Arce2= C 0 0 0 1 1
0 0 0 0 1 D 0 0 0 1 0
0 0 0 1 0 E 0 0 0 0 1
In mod analog determinam matricea Arce3 cu proprietatea ca Arce3[i][j]=true daca exista un drum de lungime 3 de la i la j , ca fiind produsul logic intre matricile Arce2 si Arce. Prin inductie matematica se constata ca matricea ArceNrNoduri ne va preciza daca exista un drum de la i la j de lungime NrNoduri.
Consideram o matrice Drum cu proprietatea ca Drum[i][j]=true daca exista un drum de la i la j de lungime mai mica sau egala cu NrNoduri.
Drum[i][j]=Arce[i][j] || Arce2[i][j] || .|| ArceNrNoduri[i][j]
Daca presupunem prin absurd ca ar exista un drum de lungime m>NrNoduri si fie acesta i,i1,i2,i3,.,im,j atunci pentru ca graful are doar NrNoduri exista cel putin un index k care apare de cel putin doua ori. Eliminand toate eventualele cicluri vom obtine in final un drum format din noduri distincte deci de lungime mai mica decat NrNoduri .
Avand in vedere formulele de calcul:
Drum=Drum+Arcek
Arcek=Arcek-1*Arce
si doua functii ajutatoare Atribuire si Produs vom putea calcula inchiderea tranzitiva
( matricea drumurilor) a matricei de adiacenta Arce.
Procedand in acest mod pana cand pe drum vor ramane doar noduri distincte vom obtine un drum sigur de lungime mai mica sau egala cu n.
Matricea drum astfel obtinuta se mai numeste inchidera tranzitiva a matricei de adiacenta.
In cazul in care numarul de noduri ale grafului este fix, ceea ce presupune ca vom putea adauga noi arce sau suprima in structura de date de tip graf, dar nu si noduri, atunci tipurile de date folosite si variabilele utilizate in prelucrarea structurii de tip graf cu varianta II 2 vor fi urmatoarele:
#define NrNoduri 5
typedef char TipCheie;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
Pentru a calcula inchidera tranzitiva vom folosi o functie Inchidere Tranzitiva. Vom folosi si o functie Produs care va seta matricea C ca fiind produsul dintre A si B. Atribuie(a,b) care va realiza cea de-a doua matrice primei.
void InchTranz(TipMatAdi Adi, TipMatAdi Drum)
}/* InchTranz */
Functiile care vor descrie operatiile efectuate asupra structurii de tip graf astfel implementata vor presupune si testul daca exista arc intre 2 noduri x si y. Functia care realizeaza acest lucru este:
int Adiacent(TipEl x, TipEl y, Graf g)
/* Adiacent */
Functia index realizeaza corespondenta nume nod - indice de acces in matricea de adiacenta.
Grafurile orientate sunt simple restrictii ale grafurilor orientate, in sensul ca daca exista arc de la x la y, <x, y> se materializeaza punand pe linia corespunzatoare lui x si coloana corespunzatoare lui y in matricea Arce valoarea 1, dar nu si pe corespunzatoare lui y si coloana coreapunzatoare lui x.
In cazul grafurilor valorice stim ca fiecare arc are asociat un numar numit valoarea(costul) arcului, prin urmare in implementarea grafurilor valorice va trebui sa reprezentam si valoarea asociata fiecarui arc.
Tipurile de structuri de date si variabile folosite in implementarea unui graf valoric cu varianta II 2 vor fi urmatoare:
#define NrNoduri 5
typedef char TipCheie;
typedef int TipInfo;
typedef struct
TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipVal;
typedef struct
TipArc;
typedef TipArc TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
TipVal v;
Functii folosite in implementarea grafurilor valorice:
void InitGraf(Graf *g); - realizeaza initializarea grafului
void AdaugaV(TipEl x, TipEl y, TipVal v, Graf *g); - adauga un arc de la x la y de valoare v;
void Sterge(TipEl x, TipEl y, TipVal *v,Graf *g); - sterge arcul de la x la y(daca exista) si seteaza pe v la valoarea asociata grafului;
PROGRAMELE C:
LABORATOR NR.7
TEMA 1 :
Scrieti programul C care permite efectuarea tuturor operatiilor asupra unui graf implementat cu matricea de adiacenta varianta II 2. Vizualizarea grafului este sub forma naturala.
#include <stdio.h>
#include <conio.h>
#include <ctype.h> /* pt. functia toupper() */
#include <graphics.h>
#include <stdlib.h>
#include <math.h>
#define CALE 'E:BORLANDCBGI'
#define PI (2*asin(1))
#define r 100
#define NrNoduri 5
typedef char TipCheie;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
int Adiacent(TipEl, TipEl, Graf);
void InitGraf(Graf *);
void Adauga(TipEl, TipEl, Graf *);
void Sterge(TipEl, TipEl, Graf *);
int index(char );
void asteptare(void);
void initializare_mod_grafic(void);
void afisareNoduri(Graf);
void afisareGraf(Graf);
void main(void)
while(op == 'N');
afisareGraf(g);
break;
case 'I':
printf('nIntroduceti nodul de pornire: ');
x = toupper(getche());
printf('nIntroduceti nodul de sosire: ');
y = toupper(getche());
Adauga(x, y, &g);
afisareGraf(g);
break;
case 'S':
printf('nIntroduceti nodul de pornire: ');
x = toupper(getche());
printf('nIntroduceti nodul de sosire: ');
y = toupper(getche());
Sterge(x, y, &g);
afisareGraf(g);
break;
}
while(optiune != 'X');
int Adiacent(TipEl x, TipEl y, Graf g)
/* Adiacent */
void InitGraf(Graf *g)
}/* InitGraf */
void Adauga(TipEl x, TipEl y, Graf *g)
else
}/* Adauga */
void Sterge(TipEl x, TipEl y, Graf *g)
else
}/* Sterge */
int index(char c)
/* index */
void asteptare(void)
/* asteptare */
void initializare_mod_grafic(void)
} /* initializare */
void afisareNoduri(Graf g)
int i, xi, yi, x0, y0;
x0 = (getmaxx()/2) + 80;
y0 = getmaxy()/2;
for(i=0; i<NrNoduri; i++)
setcolor(WHITE);
}/* afisareNoduri */
void afisareGraf(Graf g)
outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');
getch();
closegraph();
}/* afisareGraf */
LABORATORUL NR.8
TEMA 2 :
Scrieti programul C care permite efectuarea tuturor operatiilor asupra unui graf valoric implementat cu matricea de adiacenta varianta II 2. Vizualizarea grafului este sub forma naturala.
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include <graphics.h>
#include <ctype.h>
#include <string.h>
#define PI 2*asin(1)
#define r 100
#define CALE 'E:BORLANDCBGI'
#define NrNoduri 4
typedef char TipCheie;
typedef int TipInfo;
typedef struct
TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipVal;
typedef struct
TipArc;
typedef TipArc TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
TipVal v;
int Adiacent(TipEl , TipEl , Graf );
void InitGraf(Graf *);
void AdaugaV(TipEl ,TipEl ,TipVal ,Graf *);
void Sterge(TipEl ,TipEl ,TipVal *,Graf *);
void initializare_mod_grafic(void);
void afisareNoduri(Graf);
void afisareGraf(Graf);
int CautNod(Graf, TipCheie);
void creare(void);
void main()
}
afisareGraf(g);
break;
case 'D':
printf('Introduceti primul nod: ');
fflush(stdin); scanf('%c',&x); x = toupper(x);
if(CautNod(g,x)<0)
printf('Nodul nu exista!n');
else
}
afisareGraf(g);
break;
case 'E':break;
default:printf('Optiune gresita!n');
}while(c != 'E');
}/* main */
int CautNod(Graf g,TipCheie cheie)
/* CautNod */
int index(char c)
/* index */
void InitGraf(Graf *g)
}/* InitGraf */
void creare()
if(ok)
i--;
else
}
printf('Trasati un arc?(d/n)');fflush(stdin);
scanf('%c',&c);c=toupper(c);
while(c=='D')
}
printf('Trasati un arc?(d/n)'); fflush(stdin);
scanf('%c', &c); c = toupper(c);
}
}/* creare */
int Adiacent(TipEl x, TipEl y, Graf g)
/* Adiacent */
void AdaugaV(TipEl x, TipEl y, TipVal v, Graf *g)
else
}/* Adauga */
void Sterge(TipEl x, TipEl y, TipVal *v, Graf *g)
else
}/* Sterge */
void initializare_mod_grafic(void)
} /* initializare */
void afisareNoduri(Graf g)
int i, xi, yi, x0, y0;
x0 = getmaxx()/2;
y0 = getmaxy()/2;
for(i=0; i<NrNoduri; i++)
setcolor(WHITE);
}/* afisareNoduri */
void afisareGraf(Graf g)
outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');
getch();
closegraph();
}/* afisareGraf */
-Lab 8-
Intr-ucat algoritmul clasic de determinare a inchiderii tranzitive a unei matrici de adiacenta asociat unui graf G=(N,A) orientat are (n4), unde n este numarul de noduri, se pune problema daca nu exista un algoritm mai efficient pentru determinarea matricei Drum, a inchiderii tranzitive.
Warshall a fost cel care a determinat un algoritm mai eficient pentru calculul inchiderii tranzitive decat cel anterior. In acest sens ne declaram o matrice Drumk astfel incat Drumk[i][j] == 1 daca exista un drum de la nodul i la nodul j care nu trece prin nici un alt nod cu numarul > k, exceptand eventual nodurile s si j. Subintelegem ca am denumit nodurile 1, 2, , n. k poate lua valori de la 0 la numarul total de noduri.
Drum0[i,j] este matricea care are pe pozitia i,j true daca exista un drum de la i la j care nu trece prin nici un nod > 0, cu exceptia lui i si j. Deci Drum0[i][j]=Arce[i][j], deoarece singura posibilitate de a ajunge de la i la j este calea directa de la i la j, adica arcul(i,j).
Ne propunem sa determinam Drumk+1[i][j] pornind de la Drumk. Evident Drumk[i][j]=1 acolo unde Drumk[i][j]=1, deoarece, daca avem un drum de la i la j care nu trece prin nici un nod cu numarul > k, vom avea drum de la i la j care nu trece prin nici un nod cu numarul > k+1.
Singura posibilitate ca Drumk+1[i][j]=1 si Drumk[i][j]==0 este daca exista un drum de la i la j prin nodul k+1, care insa sa treaca numai prin nodurile de la 1 la k. Deci vom avea un drum de la nodul i la nodul k+1 care nu trece prin nici un nod cu indice > k.
Cu alte cuvinte, Drumk+1[i][j] = 1 daca:
Drumk[i][j] = 1 sau
Drumk[i][k+1] = 1 si Drumk[k+1][j] = 1 .
=>Drumk+1[i][j] = Drumk[i][j] || (Drumk[i][k+1] && Drumk[k+1][j] ) .
Conform acestui algoritm Drum0 = Arce si DrumNrNoduri = Drum deci chiar matricea inchiderii tranzitive cautata .
Functia care va calcula matricea drum se numeste Warshall si primeste ca si parametru matricea Arce si va intoarce tot prin intermediul parametrilor matricea Drum.
TEMA 1: Matricea drumurilor cu algoritmul lui Warshall.
#include <stdio.h>
#include <graphics.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <dos.h>/*delay*/
#define pi 2*asin(1)
#define R 180
#define r 20
#define maxN 10
typedef char TipCheie;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[maxN];
typedef int TipMatAdi[maxN][maxN];
typedef struct
Graf;
typedef struct
TipArc;
Graf g;
TipMatAdi Drum;
TipEl e;
TipArc IndiceArc;
int IndiceNod;
char s[2];
int NrNoduri;
void initializare_mod_grafic(void)
}/*initializare_mod_grafic*/
int CautaNod(Graf g,TipEl e)
/*CautaNod*/
void Atribuie(TipMatAdi a, TipMatAdi b)
/*Atribuie*/
void Produs(TipMatAdi a, TipMatAdi b, TipMatAdi c)
}/*Produs*/
void Warshall(TipMatAdi Adi, TipMatAdi Drum)
/* Warshall */
void desenareNoduri(void)
setcolor(WHITE);
}/*desenareNoduri*/
void desenareGraf(void)
}/*desenareGraf*/
void InserNod(Graf *g,TipEl e)
}/*InserNod*/
void InserArc(Graf *g, TipArc IndiceArc)
/*InserArc*/
void SuprimaArc(Graf *g,TipArc IndiceArc)
/*SuprimaArc*/
void SuprimaNod(Graf *g,int IndiceNod)
/*SuprimaNod*/
void afisare_drum(void)
/*afisare_drum*/
void creare(void)
cleardevice();
gotoxy(1,1);
desenareGraf();
/*introducere interactiva a arcelor*/
printf('Doriti sa introduceti primul arc? (D/N)');fflush(stdin);
scanf('%c',&c);c=toupper(c);
while (c=='D')
printf('Introdu al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col==-1)
InserArc(&g,IndiceArc);
xi=x0+R*cos(2*pi*IndiceArc.lin/g.Contor);
yi=y0-R*sin(2*pi*IndiceArc.lin/g.Contor);
xj=x0+R*cos(2*pi*IndiceArc.col/g.Contor);
yj=y0-R*sin(2*pi*IndiceArc.col/g.Contor);
setcolor(WHITE);
line(xi,yi,xj,yj);
printf('Mai intr. un arc?(D/N)');
fflush(stdin); scanf('%c',&c); c=toupper(c);
}
}/*creare*/
void main(void)
printf('Introdu al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col<0||IndiceArc.col>g.Contor-1)
Warshall(g.Arce,Drum);
if (Drum[IndiceArc.lin][IndiceArc.col]!=0)
printf('Exista drum intre nodul %c si nodul %cn',n1,n2);
else
printf('Nu exista drum intre nodul %c si nodul %cn',n1,n2);
}
printf('Tastati enter!');
getch();
break;
case 'T': if (g.Contor==0)
printf('Graful este vid!');
else
printf('Tastati Enter!');
getch();
break;
case 'A': printf('Intr.noul nod:');fflush(stdin);
scanf('%c',&e);e=toupper(e);
InserNod(&g,e);
break;
case 'S': if (g.Contor==0)
printf('Graful este vid!');
else
break;
case 'I': printf('Introdu primul nod: ');fflush(stdin);
scanf('%c',&n1);n1=toupper(n1);
IndiceArc.lin=CautaNod(g,n1);
while (IndiceArc.lin<0||IndiceArc.lin>g.Contor-1)
printf('Introdu al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col<0||IndiceArc.col>g.Contor-1)
InserArc(&g,IndiceArc);
break;
case 'D': if (g.Contor!=0)
printf('Intr al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col<0||IndiceArc.col>g.Contor-1)
SuprimaArc(&g,IndiceArc);
}
else
printf('Graful este vid!');
break;
}
initializare_mod_grafic();
cleardevice();
desenareGraf();
printf('Tastati enter');
getch();
closegraph();
}while (rasp!='E');
}/*main*/
Algoritmul lui Djikstra
Lab 9+10
Folosim algoritmul lui Djikstra pentru determinarea celui mai scurt drum de la S la T, care se mai numeste si drum special. Pentru inregistrarea costurilor drumurilor speciale ale unui graf, folosim o matrice distanta care se modifica la fiecare pas al algoritmului.
Initial : distanta[S]=0
distanta[i]=INFINIT, oricare ar fi i diferit de S
Cel mai scurt drum de la S la nodurile grafului este arcul <S,j> de valoare minima. Urmatorul in ordinea costurilor este un arc cu extremitatea in S sau un drum (S, j, p). Alegem in continuare drumuri in ordinea crescatoare a costurilor pana cand am determinat drumuri minime de la S la toate varfurile grafului pentru care exista un drum pornind din S. Folosim un tablou perm in care pastram toate nodurile a caror distanta minima de la S este determinata. Deci daca un nod i este membru a lui perm atunci distanta[i] este distanta minima de la S la nodul i . Initial perm are un singur membru, pe S. La fiecare pas adaugam in perm un nod k (ce nu apartinea deja tabloului perm) cu proprietatea ca drumul de la S la k are cel mai mic cost dintre toate drumurile de la S la k.
Algoritmul foloseste si o variabila curent care este nodul ce a fost adaugat la perm cel mai recent. Initial curent=S. De fiecare data cand un nod curent e adaugat la perm distanta trebuie recalculata pentru toti succesorii lui current. Pentru fiecare successor i a lui current daca
distanta[curent]+valoare[curent][i] < distanta[i]
atunci distanta de la S la i prin curent e mai mica decat oricare distanta de la S la i gasita pana acum si deci distanta[i] trebuie modificata la aceasta distanta mai mica. Daca distanta a fost recalculata pentru fiecare successor j a lui curent atunci distanta[j] va reprezenta cel mai scurt drum de la S la j ce include doar membrii lui perm. Astfel k poate fi adaugat la perm, curent e modificat la valoarea lui k si procedeul se repeta. Odata ce T devine membru a lui perm, cea mai mica distanta de la S la T este cunoscuta si algoritmul se incheie.
TEMA 1: Algoritmul lui Djikstra de determinare a drumului minim.
#include <stdio.h>
#include <graphics.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <dos.h>/*delay*/
#include <math.h>/*atan2*/
#define pi 2*asin(1)
#define R 180
#define r 20
#define NrNoduri 10
#define INFINIT 32000
#define TRUE 1
#define FALSE 0
#define MEMBRU 1
#define NEMEMBRU 0
typedef int TipContor;
typedef char TipCheie;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int mat[NrNoduri][NrNoduri];
typedef int vector[NrNoduri];
typedef int TipVal;
typedef struct
tiparc;
typedef struct
TipArc;
typedef tiparc TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
char s1[10];
TipMatAdi Drum;
TipTabEl precede;
TipEl e,s,t;
TipVal Val;
tiparc Arc;
TipArc IndiceArc;
int IndiceNod,is,it;
long lung;
mat Valoare;
void initializare_mod_grafic(void)
}/*initializare_mod_grafic*/
void desenareNoduri(void)
setcolor(WHITE);
}/*desenareNoduri*/
void desenareGrafValoric(void)
}/*desenareGrafValoric*/
int CautaNod(Graf g,TipEl e)
/*CautaNod*/
void InserNod(Graf *g,TipEl e)
}/*InserNod*/
void InserArc(Graf *g, TipArc IndiceArc, TipVal Val)
/*InserArc*/
void SuprimaArc(Graf *g,TipArc IndiceArc, TipVal *Val)
/*SuprimaArc*/
void SuprimaNod(Graf *g,int IndiceNod)
/*SuprimaNod*/
long DrumScurt(TipTabEl precede, mat Valoare, int is, int it)
distanta[is]=0;
perm[is]=MEMBRU;
k=is;
curent=is;
contor=0;
while((curent!=it)&&(contor<2*g.Contor))
if (distanta[i]<distMin)
}
curent=k;
perm[k]=MEMBRU;
contor++;
}
return distanta[it];
}/*DrumScurt*/
void creare(void)
cleardevice();
gotoxy(1,1);
desenareGrafValoric();
/*introducere interactiva a arcelor*/
printf('Doriti sa introduceti primul arc? (D/N)');fflush(stdin);
scanf('%c',&c);c=toupper(c);
while (c=='D')
printf('Introdu al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col==-1)
printf('Intr valoarea arcului: ');scanf('%d',&va);
InserArc(&g,IndiceArc,va);
cleardevice();
gotoxy(1,1);
desenareGrafValoric();
printf('Mai intr. un arc?(D/N)');
fflush(stdin); scanf('%c',&c); c=toupper(c);
}
}/*creare*/
void main(void)
printf('Introd. nodul destinatie: ');
fflush(stdin);scanf('%c',&t);
t=toupper(t);
it=CautaNod(g,t);
while (it==-1)
lung=DrumScurt(precede,Valoare,is,it);
if (lung!=INFINIT)
printf('Costul celui mai scurt drum de la %c la %c este: %dn',g.Noduri[is],g.Noduri[it],lung);
else
printf('Nu exista drum de la %c la %cn',g.Noduri[is],g.Noduri[it]);
}
else printf('Graf vid!');
printf('Tastati Enter!');
fflush(stdin);getch();
initializare_mod_grafic();
desenareGrafValoric();
printf('Tastati Enter!');
fflush(stdin);getch();
closegraph();
break;
case 'V': initializare_mod_grafic();
desenareGrafValoric();
printf('Tastati Enter!');
fflush(stdin);getch();
closegraph();
break;
case 'A': printf('Intr.noul nod:');fflush(stdin);
scanf('%c',&e);e=toupper(e);
InserNod(&g,e);
break;
case 'F': printf('Intr.nodul de suprimat:');fflush(stdin);
scanf('%c',&e);e=toupper(e);
indice=CautaNod(g,e);
if (indice>=0)
else
printf('Nodul %c nu se afla in Grafn',e);
break;
case 'I': printf('Introdu primul nod: ');fflush(stdin);
scanf('%c',&n1);n1=toupper(n1);
IndiceArc.lin=CautaNod(g,n1);
while (IndiceArc.lin<0||IndiceArc.lin>g.Contor-1)
printf('Introdu al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col<0||IndiceArc.col>g.Contor-1)
printf('Intr valoarea arcului: ');scanf('%d',&va);
InserArc(&g,IndiceArc,va);
initializare_mod_grafic();
desenareGrafValoric();
printf('Tastati Enter!');
fflush(stdin);getch();
closegraph();
break;
case 'D': printf('Intr primul nod: ');fflush(stdin);
scanf('%c',&n1);n1=toupper(n1);
IndiceArc.lin=CautaNod(g,n1);
while (IndiceArc.lin<0||IndiceArc.lin>g.Contor-1)
printf('Intr al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col<0||IndiceArc.col>g.Contor-1)
SuprimaArc(&g,IndiceArc,&Val);
initializare_mod_grafic();
desenareGrafValoric();
printf('Tastati Enter!');
fflush(stdin);getch();
closegraph();
break;
}
} while (rasp!='E');
}/*main*/
Algoritmul lui Ford Fulkerson.
-Lab 11-
Tema 1:Algoritmul lui Ford Fulkerson.
#include <stdio.h>
#include <graphics.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <dos.h>/*delay*/
#include <math.h>/*atan2*/
#define pi 2*asin(1)
#define R 180
#define r 20
#define NrNoduri 10
#define INFINIT 32000
typedef int TipContor;
typedef char TipCheie;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int mat[NrNoduri][NrNoduri];
typedef int vector[NrNoduri];
typedef int TipVal;
typedef struct
tiparc;
typedef struct
TipArc;
typedef tiparc TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
char s1[10];
TipMatAdi Drum;
TipEl e,s,t;
TipVal Val;
tiparc Arc;
TipArc IndiceArc;
int IndiceNod,is,it;
long lung;
mat Valoare;
void initializare_mod_grafic(void)
}/*initializare_mod_grafic*/
void desenareNoduri(void)
setcolor(WHITE);
}/*desenareNoduri*/
void desenareGrafValoric(void)
}/*desenareGrafValoric*/
int CautaNod(Graf g,TipEl e)
/*CautaNod*/
void InserNod(Graf *g,TipEl e)
}/*InserNod*/
void InserArc(Graf *g, TipArc IndiceArc, TipVal Val)
/*InserArc*/
void SuprimaArc(Graf *g,TipArc IndiceArc, TipVal *Val)
/*SuprimaArc*/
void SuprimaNod(Graf *g,int IndiceNod)
/*SuprimaNod*/
int Exista(vector sfDrum, int *nd)
return -1;
}/*Exista*/
void FluxMax(mat c,mat f,int S,int T,int *FluxTotal)
SfDrum[S]=1;
peDrum[S]=1;
mareste[S]=INFINIT;
while ((peDrum[T]==0)&&(Exista(SfDrum,&nd)==1))
if ((peDrum[i]==0)&&(f[i][nd]>0))
}/*for*/
}/*while*/
if (peDrum[T]==1)
/*while*/
}/*if*/
}while (peDrum[T]==1);
}/*FluxMax*/
void creare(void)
cleardevice();
gotoxy(1,1);
desenareGrafValoric();
/*introducere interactiva a arcelor*/
printf('Doriti sa introduceti primul arc? (D/N)');fflush(stdin);
scanf('%c',&c);c=toupper(c);
while (c=='D')
printf('Introdu al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col==-1)
printf('Intr valoarea arcului: ');scanf('%d',&va);
InserArc(&g,IndiceArc,va);
cleardevice();
gotoxy(1,1);
desenareGrafValoric();
printf('Mai intr. un arc?(D/N)');
fflush(stdin); scanf('%c',&c); c=toupper(c);
}
}/*creare*/
void deseneazaGrafFlux(mat f)
}/*desenareGrafFlux*/
void main(void)
printf('Dati nodul terminal: ');
fflush(stdin);scanf('%c',&t);t=toupper(t);
it=CautaNod(g,t);
while (it==-1)
for (i=0;i<g.Contor;i++)
for (j=0;j<g.Contor;j++)
FluxMax(capacitate,flux,is,it,&FluxTotal);
initializare_mod_grafic();
cleardevice();
deseneazaGrafFlux(flux);
printf('Fluxul maxim de la nodul %c la nodul %c este: %dn',s,t,FluxTotal);
fflush(stdin);getch();
closegraph();
break;
case 'V': initializare_mod_grafic();
desenareGrafValoric();
printf('Tastati Enter!');
fflush(stdin);getch();
closegraph();
break;
case 'A': printf('Intr.noul nod:');fflush(stdin);
scanf('%c',&e);e=toupper(e);
InserNod(&g,e);
break;
case 'S': printf('Intr.nodul de suprimat:');fflush(stdin);
scanf('%c',&e);e=toupper(e);
indice=CautaNod(g,e);
if (indice>=0)
else
printf('Nodul %c nu se afla in Grafn',e);
break;
case 'I': printf('Introdu primul nod: ');fflush(stdin);
scanf('%c',&n1);n1=toupper(n1);
IndiceArc.lin=CautaNod(g,n1);
while (IndiceArc.lin<0||IndiceArc.lin>g.Contor-1)
printf('Introdu al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col<0||IndiceArc.col>g.Contor-1)
printf('Intr valoarea arcului: ');scanf('%d',&va);
InserArc(&g,IndiceArc,va);
initializare_mod_grafic();
desenareGrafValoric();
printf('Tastati Enter!');
fflush(stdin);getch();
closegraph();
break;
case 'D': printf('Intr primul nod: ');fflush(stdin);
scanf('%c',&n1);n1=toupper(n1);
IndiceArc.lin=CautaNod(g,n1);
while (IndiceArc.lin<0||IndiceArc.lin>g.Contor-1)
printf('Intr al doilea nod: ');fflush(stdin);
scanf('%c',&n2);n2=toupper(n2);
IndiceArc.col=CautaNod(g,n2);
while (IndiceArc.col<0||IndiceArc.col>g.Contor-1)
SuprimaArc(&g,IndiceArc,&Val);
initializare_mod_grafic();
desenareGrafValoric();
printf('Tastati Enter!');
fflush(stdin);getch();
closegraph();
break;
}
} while (rasp!='E');
}/*main*/
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1218
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
