7/24/2019 reprezentarea grafurilor

1/7

MATRICEA DE ADIACENTA

REPREZENTAREAREPREZENTAREAGRAFURILORGRAFURILOR

7/24/2019 reprezentarea grafurilor

2/7

REPREZENTAREA GRAFURILOR

Exista mai multe moduri de reprezentare la nivel logic a unuigraf.

Aceste reprezentari pot folosite in algoritmii care prelucreazagrafuri.

Printre modurile de reprezentare a unui graf se numara:

Reprezentarea prin matricea de adiacenta

Reprezentarea prin lista muchiilor (arcelor)

Reprezentarea prin lista de adiacenta(lista vecinilor)

In functie de modul de reprezentare se utilizeaza diverse tipuride structuri de date: talouri idimensionale! vectori!inregistrari.

7/24/2019 reprezentarea grafurilor

3/7

REPREZENTAREA GRAFURILOR PRIN

MATRICEA DE ADIACENTA

"atricea de adiacenta # o matrice patrata inara de ordinuln ale carei elemente ai$ sunt denite astfel:

( )1, ,

0,

i j

ij

dac x x U a

altfel

=

Implementarea grafului prin matricea de adiacenta seface printr%o matrice patrata cu dimensiunea n astfel:

int a&'n&'n

Proprietatile matricei de adiacenta:*Elementele de pe diagonala principala au valoarea +.*In cazul grafului neorientat matricea de adiacentaeste simetrica fata de diagonala principala

7/24/2019 reprezentarea grafurilor

4/7

Exemplu:

,raf neorientat

,-(!/)-01!2!3!4!56 /-0&1!2!&1!3!&1!4!&1!5!&2!3!&2!4!&2!5!&3!46

0 1 1 1 1

1 0 1 1 1

1 1 0 1 0

1 1 1 0 0

1 1 0 0 0

7/24/2019 reprezentarea grafurilor

5/7

Exemplu

,raf orientat

,-(!/)

-01!2!3!4!56 /-0&1!2!&1!5!&2!1!&2!3!&3!1!&3!4!&5!26

0 1 0 0 1

1 0 1 0 0

1 0 0 1 0

0 0 0 0 0

0 1 0 0 0

7/24/2019 reprezentarea grafurilor

6/7

IMPLEMENTAREA GRAF NEORIENTAT

inta[10][10],n,m;

void scrie()

{inti,j;

cout

7/24/2019 reprezentarea grafurilor

7/7

inta[10][10],n,m;

voidscrie(){in$ i,j;

cout