Grafos

Pablo Rojas V.

Matriz Adyacente

• Grafo Dirigido

1

4

2

3

V={1,2,3,4}

E={(1,2), (1,4), (1,3), (2,2), (2,3), (3,4)}

0111

1010

A= 0001

0000

• Grafo No Dirigido

1

2

6

9

V={1,2,6,9}

E={(1,2), (1,9), (1,6), (2,1), (2,9),

(2,6), (2,1), (6,2), (6,1), (6,9),

(9,2), (9,6), (9,1)}

0111

A=

1011

1101

1110

Lista Adyacente y Arreglos para listas de

Adyacencia

• Grafo Dirigido

1. Matriz Adyacente

A

45

E

9

20

20

C

G

35

V={A,C,E,G}

E={(A,C), (A,E), (C,G), (C,E), (E,G)}

0 9 45 0

A= 0 0 20 35

0 0 0 20

0 0 0 0

2. Lista Adyacente

A

C

E

G

C 9

E 20

G 20

Null null

E 45

G 35

A

C

E

G

3. Arreglo Para Lista de Adyacencia

Vértices Arreglo de lista adyacente

C

E

0

E

G

0

G

null

• Grafo No Dirigido

A

40

E

120

5

15

C

G

10

V={A,C,E,G}

E={(A,C), (A,E), (C,A), (C,E), (C,G),

(E,G), (E,A), (E,C), (G,E), (G,C)}

0 120 40 0

A= 120 0

5 10

40 5 0 15

0 10 15 0

2. Lista Adyacente

A

C

E

G

C 120

A 120

G 15

C 10

C 40

E 5

A 40

E 15

C 10

G 5

A

C

E

G

3. Arreglo Para Lista de Adyacencia

Vértices Arreglo de lista adyacente

C

E

0

A

E

G

0

C