4.3.2. Árboles de expansión.

Algoritmo de Kruskal

• Ejemplo. Mostrar la ejecución del algoritmo de Kruskal.

• Necesidades del algoritmo:
  • Las aristas deben ser ordenadas, según el coste.
  • Necesitamos operaciones para saber si dos nodos están en la misma componente conexa y para unir componentes.

• Relación dos nodos pertenecen a una componente conexa: es una relación binaria de equivalencia ? podemos usar la estructura de representación para relaciones de equivalencia (con operaciones Inicia, Encuentra y Unión).

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

1

4

2

3

5

6

5

1

6

5

5

6

6

2

4

3

1

4

2

3

5

6

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