8/18/2019 Reprezentarea În Memorie a Unui Graf Neorientat

1/2

Reprezentarea în memorie a unui graf neorientat.

Pb1. Din fișierul grafneo.txt  se citesc de pe prima liniedouă numere naturale, reprezentând numărul de vârfuri,

respectiv numărul de muchii dintr-un graf neorientat. Se

citesc apoi cele m linii, pe fiecare linie fiind specificate

două numere cuprinse între 1 și n, reprezentând

extremitățile unei muchii din graf. Să se construiască

matricea de adiacență a grafului. 

Indicație:

-  Se declară o matrice 

-  Se inițializează elementele matricei cu 0 

- 

Se citesc muchiile din fișier și pentru fiecare muchie,

[i,j] se modifică valoarea din matrice: a[i][j]=1

-  Se afișează matricea 

Pb2.

Fie G un graf neorientat, cu n vârfuri si m muchii,

reprezentat prin matricea de adiacentă.

Să se realizeze programe, în C/C++, care:

8/18/2019 Reprezentarea În Memorie a Unui Graf Neorientat

2/2

a) afisează gradele tuturor vârfurilor;

b) afisează vârfurile de grad par;

c) afisează vârfurile izolate;

d) afisează vârfurile terminale;

e) verifică dacă graful are vârfuri izolate;

t) verifică dacă graful are vârfuri terminale;

g) verifică dacă graful are vârfuri interioare (nu sunt

nici izolate nici terminale);

h) verifică dacă graful are toate vârfurile izolate;

i) verifică dacă graful are toate vârfurile interioare (nu

sunt nici izolate nici terminale);

 j) afisează gradul unui vârf dat;

Indicatie: Construiti subprogramul grad care

returneaza gradul unui varf. Folositi aceasta functie

pentru rezolvarea problemelor!