Reprezentarea şi implementarea grafului: -Matricea de adiacenţă, matricea de incideţă, lista muchiilor (arcelor), lista de adiacenţă (listele vecinilor), matricea costurilor.
Reprezentarea prin matricea de adiacenţă:
Matricea de adiacenţă al unui graf de ordin n este o matrice pătratică de ordin n,
Matricea de adiacenţă al unui graf de ordin n este o matrice pătratică de ordin n,
Implementarea grafului prin matricea de adiacenţă se face printr-un tablou bidimensional, astfel:
int a[<n>,<n>];
int a[<n>,<n>];
Algoritmi pentru reprezentarea grafurilor folosind matricea de adiacenţă.
Implementarea algoritmilor pentru reprezentarea grafurilor cu matricea de adiacenţă.
1. Crearea matricei de adiacenţă prin introducerea extremităţilor muchiilor (arcelor) de la tastatură. Memorarea şi afișarea gradelor (intern și extern pentru grafurile orientate) tuturor nodurilor, cu specificarea că este nod izolat sau nod terminal. Salvarea matricei de adiacenţă în fişierul matrice_a.in.
Implementarea algoritmilor pentru reprezentarea grafurilor cu matricea de adiacenţă.
1. Crearea matricei de adiacenţă prin introducerea extremităţilor muchiilor (arcelor) de la tastatură. Memorarea şi afișarea gradelor (intern și extern pentru grafurile orientate) tuturor nodurilor, cu specificarea că este nod izolat sau nod terminal. Salvarea matricei de adiacenţă în fişierul matrice_a.in.
2. Crearea matricei de adiacenţă prin citirea ei din fişier. Determinarea numărului de vecini ai tuturor nodurilor. Afişarea muchiilor (arcelor) grafului.
Reprezentarea prin matricea de incidenţă -este o matrice binară cu n linii şi m coloane;
a) Graful Neorientat
b) Graful Orientat
Implementarea grafului prin matricea de incidenţă se face printr-un tablou bidimensional, astfel: int a[<n>,<m>];
Algoritmi pentru reprezentarea grafurilor folosind matricea de incidenţă.
1. Crearea matricei de incidenţă prin introducerea extremităţilor muchiilor de la tastatură. Calcularea gradelor şi afişarea lor pentru toate nodurile (folosind informațiile din matricea de incidență) şi specificarea dacă este nod izolat sau terminal. Salvarea matricei de incidenţă într-un fişier text cu numele matrice_i.out.
Crearea matricei de incidenţă prin citirea datelor din matricea de adiacenţă.
Graful neorientat:
-parcurgem doar elementele de sub diagonala principală
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
-parcurgem doar elementele de sub diagonala principală
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
Graful orientat:
-parcurgem toată matricea de adiacență
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
-parcurgem toată matricea de adiacență
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)