4.3.2. Árboles de expansión.

Algoritmo de Prim

• Resultados del algoritmo:

  • Árbol de expansión: las aristas serán los pares (i, MAS_CERCANO[i]), para i= 2, ..., n.
  • Costo del árbol de expansión: Suma de los MENOR_COSTO[i], para i= 2, ..., n (antes de asignarles un valor grande).

• Ejemplo. Mostrar la ejecución del algoritmo de Prim para el siguiente grafo no dirigido.

1

4

2

3

5

6

5

1

6

5

5

6

6

2

4

3

• ¿Cuál es el orden de complejidad del algoritmo?

1

4

2

3

5

6

1

5

2

4

3

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica