Algoritmos De Prolog

ALGORITMO DE KRUSKAL

La idea básica consiste en elegir sucesivamente las aristas de mínimo peso sin formar ciclos.
Paso 1. Se elige la arista de mínimo peso e y se considera S={e}.
Paso 2. Sea e’ la arista de mínimo peso tal que e’ÏS y S+e' es un grafo acíclico. Se hace S=S+e'.
Paso 3. Si S tiene n-1 aristas, el algoritmo termina. En caso contrario se vuelve al paso 2.

El coste delprimer paso, ordenación de las aristas según su peso, es O(qlogq), es decir, O(qlogn). En el segundo paso se debe detectar si la arista elegida forma un ciclo con las previamente elegidas.
Basta tener marcada la componente conexa a que pertenece cada vértice (inicialmente habrá n componentes, una por vértice).
Si se elige una arista con extremos de la misma etiqueta se está formando un ciclo y sitienen distinta etiqueta no hay ciclo y la elección es correcta. En este caso se deben actualizar las etiquetas para mantener siempre una por cada componente conexa. El coste total de este paso es O(q) por la comprobación de la corrección más O(n2) por las actualizaciones, pues en el peor caso en cada uno de los n pasos se deben actualizar las etiquetas de los n vértices. La complejidad totaldel algoritmo de Kruskal es por tanto O(n2+qlogn)

CÓDIGO: (c++)
// Declaraciones en el archivo .h
int cn; //cantidad de nodos
vector< vector > ady; //matriz de adyacencia

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

for(int i = 0; i < cn; i++){
arbol[i] = vector (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;
for(int i = 0; i < cn; i++)
for(int j = 0; j < cn;j++)
if(min > adyacencia[i][j] && pertenece[i] != pertenece[j]){
min = adyacencia[i][j];
nodoA = i;
nodoB = j;
}

// Si los nodos no pertenecen al mismo arbol agrego el arco al arbol minimo.
if(pertenece[nodoA] != pertenece[nodoB]){
arbol[nodoA][nodoB] = min;arbol[nodoB][nodoA] = min;

// Todos los nodos del arbol del nodoB ahora pertenecen al arbol del nodoA.
int temp = pertenece[nodoB];
pertenece[nodoB] = pertenece[nodoA];
for(int k = 0; k < cn; k++)
if(pertenece[k] == temp)
pertenece[k] = pertenece[nodoA];arcos++;
}
}
return arbol;
}

EJEMPLO:
La respuesta sería:











ALGORITMO DE PRIM

La idea básica consiste en añadir, en cada paso, una arista de peso mínimo a un árbol previamente construido. Más explícitamente:
Paso 1. Se elige un vértice u de G y se considera el árbol S={u}
Paso 2. Se considera la arista e de mínimo peso que une un vértice de Sy un vértice que no es de S, y se hace S=S+e
Paso 3. Si el nº de aristas de T es n-1 el algoritmo termina. En caso contrario se vuelve al paso 2

Análisis de la complejidad
·Primera aproximación
En el paso 2, si S tiene k vértices hay n-k vértices en V-S. Por tanto, necesitamos hallar la arista de mínimo peso entre k(n-k) aristas. Como k(n-k)d)
{ table [n1].distance = d;table [n1].predecessor = n0;
queue.enqueue (
new Association (new Int (d), v1));
}
}
}
}
Graph result = new GraphAsLists (n);
for (int v = 0; v < n; ++v)
result.addVertex (v);
for (int v = 0; v < n; ++v)
if (v != s)...