Árbol De Expansión Minima

UNIVERSIDAD DE GUADALAJARA

CENTRO UNIVERSITARIO DE CIENCIAS EXACTAS E INGENIERIAS

ANALISIS Y DISENO DE ALGORITMOS

ARBOL DE EXPANSION MINIMA

NOMBRE: BERRONES GARCIA, S. ORLANDO
CODIGO:301202456
SECCION: D03
FECHA: 24 DE NOVIEMBRE DE 2012
ARBOL DE EXPANSION MINIMA

Análisis breve del orden del algoritmo (Algoritmo de Kruskal)
El algoritmo de Kruskal es un algoritmo de la teoríade grafos que busca encontrar un árbol recubridor mínimo de un grafo dado. Aquí encontraremos una implementación en Java incluyendo una interfaz gráfica.

Descripción del Problema

El algoritmode kruskal, es un algoritmo voraz utilizado en la teoría de grafos, con el fin de encontrar un árbol recubridor mínimo de un grafo conexo y ponderado.

El algoritmo de kruskal consiste en:
Paso 0:Iniciar el árbol T con n nodos y sin arcos
T=({1, 2, …n},ø)
Paso 1: Con los arcos de G crear una lista L de arcos, en orden ascendente de peso. Los arcos con el mismo peso sonordenados arbitrariamente.
Paso 2. Seleccionar el arco (i,j) que esté al comienzo de L. Si éste forma un circuito en T no se transfiere a T y se borra de L y se repite el paso 2. Si no forma circuito en Tse transfiere a T y se borra de L.
Paso 3. Si L es no vacío, volver al paso 2, de lo contrario PARAR.

Limitaciones

Las únicas limitaciones que se presentan con el problema de laimplementación del algoritmo de Kruskal es la creación de un algoritmo adicional que nos compruebe que al adicionar una arista al grafo no nos haga un ciclo.

El algoritmo implementado es el siguiente:public boolean HayCiclo(Grafo g,Arco aVerificar,Nodo terminal,String N)
{
ArrayList<Enlace> aux=terminal.getEnlaces();

if(aux.size()==0)
return false;if(terminal.existeEnlace(aVerificar.getInicial())!=-1)
return true;

for(int i=0;i<aux.size();i++)
{
Enlace nodo=aux.get(i);...