Árbol de expansiónmínima

Algoritmo de Prims

Ejemplo 1

()

()

()

()

()

()

()

Cola2

101 3

2

4

5

7

64

1

8

v1, 0

v2, inf

v3, inf

v4, inf

v5, inf

v6, inf

v7, inf

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v1, 0

v4, 1

v2, 2

v3, 4

v5, inf

v6, inf

v7, inf

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v4, 1

v2, 2

v3, 4

v5, inf

v6, inf

v7, inf

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v4, 1

v2, 2

v3, 2

v7, 4

v5, 7

v6, 8

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v2, 2

v3, 2

v7, 4

v5, 7

v6, 8

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v2, 2

v3, 2

v7, 4

v5, 7

v6, 8

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v3, 2

v7, 4

v5, 7

v6, 8

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v3, 2

v7, 4

v6, 5

v5, 7

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v7, 4

v6, 5

v5, 7

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v7, 4

v6, 1

v5, 6

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v6, 1

v5, 6

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v6, 1

v5, 6

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v5, 6

Cola2

101 3

2

4

5

7

64

1

8

Inicio

v5, 6

Cola2

101 3

2

4

5

7

64

1

8

Inicio

Cola2

101 3

2

4

5

7

64

1

8

Inicio

Cola2

101 3

2

4

5

7

64

1

8

Inicio

Cola2

1

2

64

1

Inicio

Costo 16

Ejemplo 2

v0()

v4()

v5()

v1()

v3()

v2()

2428

1112

15

20

13

()

()

()

()

()

()

()

Cola

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

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

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

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

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

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