1 Árbol de expansión mínima Algoritmo de Prims

2 Ejemplo 1

3 v1 () v4 () v2 () v6 () v3 () v5 () Cola v7 () 2 1013 2 4 5 7 6 4 1 8

4 v1 () v4 () v2 () v6 () v3 () v5 () v1, 0 v2, inf v3, inf v4, inf v5, inf v6, inf v7, inf Cola v7 () 2 1013 2 4 5 7 6 4 1 8 Inicio

5 v1 v4 (v1, 1) v2 (v1, 2) v6 () v3 (v1, 4) v5 () v1, 0 v4, 1 v2, 2 v3, 4 v5, inf v6, inf v7, inf Cola v7 () 2 1013 2 4 5 7 6 4 1 8 Inicio

6 v1 v4 (v1, 1) v2 (v1, 2) v6 () v3 (v1, 4) v5 () v4, 1 v2, 2 v3, 4 v5, inf v6, inf v7, inf Cola v7 () 2 1013 2 4 5 7 6 4 1 8 Inicio

7 v1 v4 (v1, 1) v2 (v1, 2) v6 (v4,8) v3 (v4, 2) v5 (v4, 7) v4, 1 v2, 2 v3, 2 v7, 4 v5, 7 v6, 8 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

8 v1 v4 (v1, 1) v2 (v1, 2) v6 (v4,8) v3 (v4, 2) v5 (v4, 7) v2, 2 v3, 2 v7, 4 v5, 7 v6, 8 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

9 v1 v4 (v1, 1) v2 (v1, 2) v6 (v4,8) v3 (v4, 2) v5 (v4, 7) v2, 2 v3, 2 v7, 4 v5, 7 v6, 8 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

10 v1 v4 (v1, 1) v2 (v1, 2) v6 (v4,8) v3 (v4, 2) v5 (v4, 7) v3, 2 v7, 4 v5, 7 v6, 8 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

11 v1 v4 (v1, 1) v2 (v1, 2) v6 (v3,5) v3 (v4, 2) v5 (v4, 7) v3, 2 v7, 4 v6, 5 v5, 7 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

12 v1 v4 (v1, 1) v2 (v1, 2) v6 (v3,5) v3 (v4, 2) v5 (v4, 7) v7, 4 v6, 5 v5, 7 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

13 v1 v4 (v1, 1) v2 (v1, 2) v6 (v3,5) v3 (v4, 2) v5 (v4, 7) v7, 4 v6, 1 v5, 6 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

14 v1 v4 (v1, 1) v2 (v1, 2) v6 (v7,1) v3 (v4, 2) v5 (v7, 6) v6, 1 v5, 6 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

15 v1 v4 (v1, 1) v2 (v1, 2) v6 (v7,1) v3 (v4, 2) v5 (v7, 6) v6, 1 v5, 6 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

16 v1 v4 (v1, 1) v2 (v1, 2) v6 (v7,1) v3 (v4, 2) v5 (v7, 6) v5, 6 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

17 v1 v4 (v1, 1) v2 (v1, 2) v6 (v7,1) v3 (v4, 2) v5 (v7, 6) v5, 6 Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

18 v1 v4 (v1, 1) v2 (v1, 2) v6 (v7,1) v3 (v4, 2) v5 (v7, 6) Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

19 v1 v4 (v1, 1) v2 (v1, 2) v6 (v7,1) v3 (v4, 2) v5 (v7, 6) Cola v7 (v4, 4) 2 1013 2 4 5 7 6 4 1 8 Inicio

20 v1 v4 (v1, 1) v2 (v1, 2) v6 (v7,1) v3 (v4, 2) v5 (v7, 6) Cola v7 (v4, 4) 2 1 2 6 4 1 Inicio Costo 16

21 Ejemplo 2

22 v0 () v4 () v5 () v1 () v3 () v2 () 2428 1112 15 20 13 () Cola

23 v0 (v0, 0) v4 (inf) v5 (inf) v1 (inf) v3 (inf) v2 (inf) 2428 1112 15 20 13 v0, 0 v1,inf v2, inf v3, inf v4, inf v5, inf v6, inf Cola Inicio

24 v0 (v0, 0) v4 (inf) v5 (v0, 28) v1 (v0, 24) v3 (inf) v2 (inf) 2428 1112 15 20 13 v0, 0 v1, 24 v5, 28 v2, inf v3, inf v4, inf v6, inf Cola Inicio

25 v0 (v0, 0) v4 (inf) v5 (v0, 28) v1 (v0, 24) v3 (inf) v2 (inf) 2428 1112 15 20 13 v1, 24 v5, 28 v2, inf v3, inf v4, inf v6, inf Cola Inicio

26 v0 (v0, 0) v4 (inf) v5 (v0, 28) v1 (v0, 24) v3 (inf) v2 (v1, 11) 2428 1112 15 20 13 v1, 24 v2, 11 v5, 28 v3, inf v4, inf v6, inf Cola Inicio

27 v0 (v0, 0) v4 (inf) v5 (v0, 28) v1 (v0, 24) v3 (inf) v2 (v1, 11) 2428 1112 15 20 13 v2, 11 v5, 28 v3, inf v4, inf v6, inf Cola Inicio

28 v0 (v0, 0) v4 (inf) v5 (v0, 28) v1 (v0, 24) v3 (v2, 11) v2 (v1, 11) 2428 1112 15 20 13 v2, 11 v3, 13 v5, 28 v4, inf v6, inf Cola Inicio