Pasos del árbol de expansión mínimo en la estructura de datos

La idea básica del algoritmo de Prim es tomar cualquier vértice v en el gráfico como la raíz del árbol de expansión y luego agregar un nuevo vértice w al árbol de expansión. Debe haber un borde entre el vértice w agregado y el vértice v en el árbol de expansión, y el peso de este borde es el más pequeño entre los bordes que conectan los vértices v y w. Continúe agregando vértices al árbol de expansión hasta que el árbol de expansión contenga n-1 vértices.

Algoritmo de Kruskal

La idea básica del algoritmo de Kruskal es que para minimizar la suma de los pesos de las aristas en el árbol de expansión, el peso de cada arista en el El árbol de expansión debe ser lo más pequeño posible.

Método específico: primero construya un subgrafo SG que contenga solo n vértices y luego comience desde el borde con el peso más pequeño. Si agregar este borde no formará un ciclo en SG, agregue este borde a SG. y así sucesivamente hasta que se agreguen n-1 bordes.