DAA - Árbol de expansión
UNA spanning tree es un subconjunto de un gráfico no dirigido que tiene todos los vértices conectados por un número mínimo de aristas.
Si todos los vértices están conectados en un gráfico, entonces existe al menos un árbol de expansión. En un gráfico, puede haber más de un árbol de expansión.
Propiedades
- Un árbol de expansión no tiene ningún ciclo.
- Se puede llegar a cualquier vértice desde cualquier otro vértice.
Ejemplo
En el siguiente gráfico, los bordes resaltados forman un árbol de expansión.
Árbol de expansión mínimo
UNA Minimum Spanning Tree (MST)es un subconjunto de aristas de un grafo no dirigido ponderado conectado que conecta todos los vértices con el peso de arista total mínimo posible. Para derivar un MST, se puede utilizar el algoritmo de Prim o el algoritmo de Kruskal. Por lo tanto, discutiremos el algoritmo de Prim en este capítulo.
Como hemos comentado, un gráfico puede tener más de un árbol de expansión. Si hayn número de vértices, el árbol de expansión debería tener n - 1número de aristas. En este contexto, si cada borde del gráfico está asociado con un peso y existe más de un árbol de expansión, necesitamos encontrar el árbol de expansión mínimo del gráfico.
Además, si existen bordes ponderados duplicados, el gráfico puede tener varios árboles de expansión mínimos.
En el gráfico anterior, mostramos un árbol de expansión, aunque no es el árbol de expansión mínimo. El costo de este árbol de expansión es (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.
Usaremos el algoritmo de Prim para encontrar el árbol de expansión mínimo.
Algoritmo de Prim
El algoritmo de Prim es un enfoque codicioso para encontrar el árbol de expansión mínimo. En este algoritmo, para formar un MST podemos partir de un vértice arbitrario.
Algorithm: MST-Prim’s (G, w, r)
for each u є G.V
u.key = ∞
u.∏ = NIL
r.key = 0
Q = G.V
while Q ≠ Ф
u = Extract-Min (Q)
for each v є G.adj[u]
if each v є Q and w(u, v) < v.key
v.∏ = u
v.key = w(u, v)La función Extract-Min devuelve el vértice con un coste de borde mínimo. Esta función funciona en min-heap.
Ejemplo
Usando el algoritmo de Prim, podemos comenzar desde cualquier vértice, comencemos desde el vértice 1.
Vértice 3 está conectado al vértice 1 con un costo de borde mínimo, por lo tanto, borde (1, 2) se agrega al árbol de expansión.
Siguiente, borde (2, 3) se considera que este es el mínimo entre los bordes {(1, 2), (2, 3), (3, 4), (3, 7)}.
En el siguiente paso, obtenemos ventaja (3, 4) y (2, 4)con costo mínimo. Borde(3, 4) se selecciona al azar.
De manera similar, los bordes (4, 5), (5, 7), (7, 8), (6, 8) y (6, 9)están seleccionados. Como se visitan todos los vértices, ahora el algoritmo se detiene.
El costo del árbol de expansión es (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. No hay más árbol de expansión en este gráfico con un costo menor que 23.
