Esta página se tradujo automáticamente con la API de traducción de Google Cloud.
Algunas páginas se pueden leer mejor en su totalidad.
En informática, un árbol de expansión mínimo (MST) o árbol de expansión de peso mínimo es un subconjunto de los bordes de un gráfico ponderado no dirigido que conecta todos los vértices, sin ningún ciclo y con el peso de borde total mínimo posible.
Hay muchas aplicaciones para los árboles de expansión mínimos. Por ejemplo, en una red de carreteras o líneas de comunicación, se puede utilizar un árbol de expansión mínimo para encontrar la forma más económica de conectar todos los nodos entre sí. Otro ejemplo es el análisis de conglomerados, donde se puede usar un árbol de expansión mínimo para encontrar grupos de objetos similares.
El algoritmo de Kruskal es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico ponderado conectado. Comienza con los bordes con los pesos más pequeños y agrega bordes hasta llegar a un árbol.
El algoritmo funciona de la siguiente manera:
Ordene los bordes por peso de menor a mayor.
Comience con el borde con el menor peso. Si el borde no crea un ciclo, agréguelo al árbol.
Repita el paso 2 hasta que no haya más bordes para agregar.
La complejidad temporal del algoritmo de Kruskal es O(E log V), donde E es el número de aristas y V es el número de vértices.
El algoritmo de Prim es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico ponderado conectado. Comienza con un vértice y agrega los bordes más baratos hasta llegar a un árbol.
El algoritmo funciona de la siguiente manera:
Comienza con un vértice.
Encuentra la arista más barata del vértice a otro vértice.
Agregue el borde al árbol.
Repita el paso 2 hasta que no haya más bordes para agregar.
La complejidad temporal del algoritmo de Prim es O(E log V), donde E es el número de aristas y V es el número de vértices.
La siguiente es una implementación de JavaScript del algoritmo de Kruskal.
function kruskals(edges) {
// sort edges by weight
edges.sort((a, b) => a.weight - b.weight);
// make a set for each vertex
const sets = [];
for (let i = 0; i < edges.length; i++) {
sets.push(new Set([i]));
}
// list of edges in the MST
const mst = [];
// for each edge, check if it creates a cycle
for (const edge of edges) {
const [u, v] = edge.vertices;
// if the edge doesn't create a cycle, add it to the MST
if (!sets[u].has(v)) {
mst.push(edge);
// union the two sets
const setU = sets[u];
const setV = sets[v];
for (const vertex of setV) {
setU.add(vertex);
sets[vertex] = setU;
}
}
}
return mst;
}
Use el algoritmo de Kruskal para encontrar el árbol de expansión mínimo para el siguiente gráfico:
Use el algoritmo de Prim para encontrar el árbol de expansión mínimo para el siguiente gráfico:
El árbol de expansión mínimo para el gráfico se muestra a continuación. El peso total del árbol es 9.
El árbol de expansión mínimo para el gráfico se muestra a continuación. El peso total del árbol es 10.