Algoritmo De Kruskal

Algoritmo de Kruskal
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbolexpandido mínimo para cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.

Un ejemplo de árbol expandido mínimo. Cada punto representa un vértice, el cual puede ser un árbol por sí mismo. Se usa el Algoritmo para buscar las distancias más cortas (árbol expandido) que conectan todos los puntos o vértices.
Funciona de la siguiente manera:
* se crea un bosque B(un conjunto de árboles), donde cada vértice del grafo es un árbol separado
* se crea un conjunto C que contenga a todas las aristas del grafo
* mientras C es no vacío
* eliminar una arista de peso mínimo de C
* si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
* en caso contrario, se desecha la arista
Alacabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.
Este algoritmo fue publicado por primera vez en Proceedings of the American Mathematical Society, pp. 48–50 en 1956, y fue escrito por Joseph Kruskal.
Contenido * 1 Pseudocódigo * 2 Código en C++ * 3 Complejidad del algoritmo * 4 Demostración de la corrección * 5 Ejemplo *6 Referencias * 7 Enlaces externos |
Pseudocódigo
1 function Kruskal(G)
2 for each vertex v in G do
3 Define an elementary cluster C(v) ← {v}.
4 Initialize a priority queue Q to contain all edges in G, using the weights as keys.
5 Define a tree T ← Ø //T will ultimately contain theedges of the MST
6 // n es el número total de vértices
7 while T has fewer than n-1 edges do
8 // edge u, v is the minimum weighted route from/to v
9 (u,v) ← Q.removeMin()
10 // previene ciclos en T. suma u, v solo si T no contiene una arista que una u y v.
11// Nótese que el cluster contiene más de un vértice si una arista une un par de
12 // vértices que han sido añadidos al árbol.
13 Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
14 if C(v) ≠ C(u) then
15 Add edge (v,u) to T.
16 Merge C(v) and C(u) intoone cluster, that is, union C(v) and C(u).
17 return tree T
Código en C++
// Declaraciones en el archivo .h
int cn; //cantidad de nodos
vector< vector<int> > ady; //matriz de adyacencia

// Devuelve la matriz de adyacencia del arbol minimo.
vector<vector<int> > Grafo :: kruskal(){
vector< vector<int> > adyacencia = this->ady;
vector< vector<int> > arbol(cn);
vector<int> pertenece(cn); // indica a que arbol pertenece el nodo

for(int i = 0; i < cn; i++){
arbol[i] =vector<int> (cn, INF);
pertenece[i] = i;
}

int nodoA;
int nodoB;
int arcos = 1;
while(arcos < cn){
// Encontrar el arco minimo que no forma ciclo y guardar los nodos y la distancia.
int min = INF;...