1.
SCOPUL
LUCRĂRII:
-Studierea algoritmilor de căutare în graf şi a
diferitor forme de păstrare şi prelucrare a datelor.
-Elaborarea procedurii de căutare în adâncime.
-Studierea
algoritmului de căutare în lărgime;
-Elaborarea
programului de căutare în lărgime
2.SARCINA
DE BAZĂ
1. Elaboraţi procedura care va realiza algoritmul de
parcurgere a grafului în lărgime;
2. Folosind procedurile din lucrările precedente,
elaboraţi programul care va permite:
*
introducerea grafului în calculator;
3.Elaboraţi procedura căutării în adâncime într-un
graf arbitrar;
4.Elaboraţi un program cu următoarele
posibilităţi:
Ø
introducerea grafului în calculator,
Ø
parcurgerea grafului în adâncime,
NOTE
DE CURS
Structuri
de date: liste
Fiecare tip
de listă defineşte o mulţime de şiruri finite de elemente de tipul declarat.
Numărul de elemente care se numeşte lungimea listei poate varia pentru diferite
liste de acelaşi tip. Lista care nu conţine nici un element se va numi vidă.
Pentru listă sunt definite noţiunile începutul, sfârşitul listei şi respectiv
primul şi ultimul element, de asemenea elementul curent ca şi predecesorul şi
succesorul elementului curent. Element curent se numeşte acel unic element care
este accesibil la momentul dat.
Structuri de date : fire de aşteptare
Firele de aşteptare
(FA, rând, coadă, şir de aşteptare)
se vor folosi pentru a realiza algoritmul de prelucrare a elementelor listei în
conformitate cu care elementele vor fi eliminate din listă în ordinea în care
au fost incluse în ea (primul sosit - primul servit).
Operaţiile de bază cu firele de aşteptare:
Ø
Formarea unui FA vid;
Ø Verificare dacă FA nu este vid;
Ø Alegerea primului element cu eliminarea lui din
FA;
Ø Introducerea unei valori noi în calitate de ultim
element al FA.
Structuri
de date: stive
Stiva se utilizează pentru a realiza algoritmul de
prelucrare a elementelor după principiul "ultimul sosit - primul
prelucrat" (LIFO).
Operaţiile de bază cu stivele sunt următoarele:
Ø
Formarea unei stive vide;
Ø
Verificare la vid;
Ø Alegerea elementului din topul stivei cu sau fără
eliminare;
Ø Introducerea unui element nou în topul stivei.
Structuri de date - arbori
Se va defini o mulţime de structuri fiecare din
care va consta dintr-un obiect de bază numit vârf sau rădăcina arborelui dat
şi o listă de elemente din mulţimea definită, care (elementele) se vor numi subarbori ai arborelui dat. Arborele
pentru care lista subarborilor este vidă se va numi arbore trivial, iar rădăcina lui - frunză.
Rădăcina arborelui
se va numi tatăl vârfurilor care servesc drept rădăcini pentru subarbori;
aceste vârfuri se vor mai numi copiii rădăcinii arborelui: rădăcina primului
subarbore se va numi fiul cel mai mare,
iar rădăcina fiecărui subarbore următor în listă se va numi frate.
Operaţiile de bază pentru arbori vor fi:
Ø
Formarea unui arbore trivial;
Ø Alegerea sau înlocuirea rădăcinii arborelui;
Ø Alegerea sau înlocuirea listei rădăcinilor
subarborilor;
Ø Operaţiile de bază care sunt valabile pentru
liste.
Listingul
programului:
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#define N 20
#define M 20
typedef struct nod{
int v;
struct nod *next;
}NOD;
NOD *c,*h[20],*p;
void int_list_de_adiac(int n)
{int i,j;
clrscr();
printf("Introdu elementele listei:\n");
for(i=0;i<n;i++){
h[i]=(NOD*)malloc(sizeof(*h));
c=h[i];
printf("%d | ",i+1);
while(1){
scanf("%d", &c->v);
if(c->v==0){
c->next=NULL;
break;
}
p=(NOD*)malloc(sizeof(*p));
c->next=p;
c=p;}
}
}
void afis_list_de_adiac(int n)
{
int i;
clrscr();
printf("Lista de adiacenta este:\n");
for (i=0;i<n;i++){
c=h[i];
printf("%d | ",i+1);
while(1){
printf("%3d",c->v);
if(c->v==0)break;
c=c->next;
}
printf("\n");
}
getch();
}
void parc_graf_in_adinc(int n)
{int i,f,u,m;
NOD *r,*g,*a,*t[20];
clrscr();
u=0;
for(i=0;i<n;i++)
t[i]=h[i];
g=(NOD*)malloc(sizeof(NOD));
textcolor(12);
printf("\n Introduceti radacina: ");
scanf("%d",&f);
g->v=f;
g->next=NULL;
a=g;
printf("%d",f);
r=t[f-1];
while(g!=NULL)
{
if(r->v!=0){r=t[f-1];
if(r->v!=0){
printf("\t %d",r->v);
u++;
t[f-1]=t[f-1]->next;
f=r->v;
g=(NOD*)malloc(sizeof(NOD));
g->v=r->v;
g->next=a;
a=g;}}
else if(r->v==0){
a=a->next;
free(g);
g=a;
f=a->v;
r=t[f-1];
}
}
getch();}
void parc_graf_in_latim(int n)
{int i=0,r;
NOD *c,*t,*o,*l;
clrscr();
t=(NOD*)malloc(sizeof(NOD));
textcolor(16);
printf("Inroduceti radacina: ");
scanf("%d",&r);
printf("%d",r);
t->v=r;
t->next=NULL;
c=t;
l=t;
while((t!=0)&&(c!=0)){
if(i==0){o=h[r-1];i=1;}
if(o->v!=0){
printf("\t%d",o->v);
t=(NOD*)malloc(sizeof(NOD));
t->v=o->v;
t->next=NULL;
l->next=t;
l=t;
o=o->next;}
else if(o->v==0) {o=c->next;free(c);c=o;
r=c->v;i=0;}
}
getch();
}
void main()
{
int n,m;
char d;
clrscr();
printf("Introduceti numarul de virfuri ale
grafului - ");
scanf("%d",&n);
printf("Introduceti numarul de arcuri ale
grafului - ");
scanf("%d",&m);
while(1){
clrscr();
printf
("\t\t\tMENIU \n");
printf("\t1 - Introducerea
listei de adiacenta. \n ");
printf("\t2 - Afisarea
listei de adiacenta.\n ");
printf("\t3 - Parcurgerea
grafului in adincime \n");
printf("\t4 - Parcurgerea
grafului in latime \n" );
printf("\t0 - Iesire
\n");
textcolor(GREEN);
cprintf("\n Comanda: ");
d=getch();
switch(d){
case '1':{
int_list_de_adiac(n); break;}
case '2':{ afis_list_de_adiac(n);break;}
case '3':{parc_graf_in_adinc(n);break;}
case '4':{parc_graf_in_latim(n);break;}
case '0':{exit(0);break;}
}}}
Concluzie:
La lucrarea de laborator cu tema:” Parcurgerea
grafului in largime si adincime.”,am studiat algoritmii de căutare în graf şi diferite forme de păstrare şi
prelucrare a datelor, am elaborat proceduri de căutare în adâncime si lărgime.
