Grafuri - noţiuni elementare, reprezentare, parcurgere
Rândul 1
1. Scrieţi funcţia GradMaxim, care returnează gradul cel mai mare pe care îl are un vârf dintr-un graf reprezentat prin liste de adiacenţă. Utilizând această funcţie, scrieţi funcţia VarfuriGradMaxim, care utilizând apeluri ale funcţiei GradMaxim, afişează nodurile de grad maxim din graf.
2. Scrieţi funcţia GrafComplet, care verifică dacă graful reprezentat prin liste de adiacenţă este graf complet. Funcţia va conţine şi un comentariu în care veţi da definiţia grafului complet.
3. Scrieţi funcţia Parcurgere, care primind ca parametri un întreg n şi un vector T care memorează n numere întregi şi returnează valoarea 1, dacă cele n numere întregi memorate în vectorul T sunt nodurile grafului scrise în ordinea parcurgerii BFS(1), sau va returna 0 în caz contrar. Se consideră că graful este reprezentat prin liste de adiacenţă.
Vectorul T se citeşte tot din fişierul graf.txt, cele n valori aflându-se pe ultima linie din fişier, deci veţi citi vectorul după ce aţi terminat de citit cele m muchii ale grafului.
Funcţia main va arăta astfel:
int T[201], n, m ;
nod *L[201] ;
int main()
{
CitireGraf() ;
cout<< “Varfurile de grad maxim : ” ;
VarfuriGradMaxim() ;
if (GrafComplet() == 1) cout<< “Graful este complet” ;
else cout<< “Graful nu este complet” ;
if (Parcurgere(n,T) == 1) cout<< “Parcurgere BFS(1) corecta” ;
else cout<< “Parcurgere BFS(1) incorecta” ;
return 0 ;
}
Rândul 2
1. Scrieţi funcţia GradExteriorCorect, care primind ca parametru un vector H de n întregi, returnează 1 dacă în H sunt memorate corect cele n grade exterioare ale unui digraf reprezentat prin matricea de adiacenţă, sau returnează 0 în caz contrar.
2. Scrieţi funcţia DigrafComplet, care verifică dacă graful reprezentat prin matricea de adiacenţă este digraf complet. Funcţia va conţine şi un comentariu în care veţi da definiţia digrafului complet.
3. Scrieţi funcţia Nivel, care primind ca parametru un întreg niv, afişează nodurile care se află pe nivelul niv în parcurgerea BFS(1) a digrafului reprezentat prin matricea de adiacenţă. Se consideră că vârful 1 este pe nivelul 1, adiacenţii lui 1 sunt pe nivelul 2, adiacenţii adiacenţilor sunt pe nivelul 3 ş.a.m.d.
Vectorul H se citeşte tot din fişierul graf.txt, cele n valori aflându-se pe ultima linie din fişier, deci veţi citi vectorul după ce aţi terminat de citit cele m muchii ale grafului.
Funcţia main va arăta astfel:
int H[201], d[201], n, m ;
nod *L[201] ;
int main()
{
CitireGraf() ;
if (GradExteriorCorect(H) == 1) cout<< “Grade exterioare corecte” ;
else cout<< “Grade exterioare incorecte” ;
if (DigrafComplet() == 1) cout<< “Digraful este complet” ;
else cout<< “Digraful nu este complet” ;
cout<<“Pe nivelul 2 se gasesc nodurile :” ;
Nivel(2) ;
return 0 ;
}
Despre autor
Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică
