Algoritmo de árbol de expansión de Prim

El algoritmo de Prim para encontrar el árbol de expansión de costo mínimo (como el algoritmo de Kruskal) utiliza el enfoque codicioso. El algoritmo de Prim comparte una similitud con elshortest path first algoritmos.

El algoritmo de Prim, en contraste con el algoritmo de Kruskal, trata los nodos como un solo árbol y sigue agregando nuevos nodos al árbol de expansión desde el gráfico dado.

Para contrastar con el algoritmo de Kruskal y entender mejor el algoritmo de Prim, usaremos el mismo ejemplo:

Paso 1: eliminar todos los bucles y bordes paralelos

Elimine todos los bucles y bordes paralelos del gráfico dado. En caso de bordes paralelos, mantenga el que tenga el menor costo asociado y elimine todos los demás.

Paso 2: elija cualquier nodo arbitrario como nodo raíz

En este caso, elegimos Snodo como el nodo raíz del árbol de expansión de Prim. Este nodo se elige arbitrariamente, por lo que cualquier nodo puede ser el nodo raíz. Uno puede preguntarse por qué cualquier video puede ser un nodo raíz. Entonces, la respuesta es que en el árbol de expansión se incluyen todos los nodos de un gráfico y, como está conectado, debe haber al menos un borde, que lo unirá al resto del árbol.

Paso 3: verifique los bordes salientes y seleccione el que tenga menos costo

Después de elegir el nodo raíz S, vemos que S, A y S, C son dos aristas con peso 7 y 8, respectivamente. Elegimos el borde S, A ya que es menor que el otro.

Ahora, el árbol S-7-A se trata como un nodo y verificamos todos los bordes que salen de él. Seleccionamos el que tiene el menor costo y lo incluimos en el árbol.

Después de este paso, se forma el árbol S-7-A-3-C. Ahora lo trataremos de nuevo como un nodo y volveremos a comprobar todos los bordes. Sin embargo, elegiremos solo la ventaja de menor costo. En este caso, C-3-D es el nuevo borde, que es menor que el costo de otros bordes 8, 6, 4, etc.

Después de agregar nodo Dpara el árbol de expansión, ahora tenemos dos aristas que salen de él con el mismo costo, es decir, D-2-T y D-2-B. Por lo tanto, podemos agregar cualquiera. Pero el siguiente paso volverá a producir el borde 2 como el menor costo. Por lo tanto, estamos mostrando un árbol de expansión con ambos bordes incluidos.

Podemos encontrar que el árbol de expansión de salida del mismo gráfico utilizando dos algoritmos diferentes es el mismo.