|
En la implementación del algoritmo de Kruskal en [[lenguaje de programación Java| Java]], se hizo uso de una [[estructura de datos]] adicional llamada [[grafo]] y adicionalmente se implementó una interfaz gráfica.
===Estructura Grafo===
====Clase Enlace====
Creamos un clase llamada enlace
La clase enlace se utiliza para hacer refencia al nodo terminal y al peso de un arco.
<source lang="java">
public class Enlace
{
private String destino;
private double peso;
public Enlace(String desti, double peso1)
{
destino = desti;
peso = peso1;
}
public Enlace(String desti)
{
destino = desti;
peso = -1;
}
public void modificar(double peso1)
{
peso = peso1;
}
public String getDestino()
{
return destino;
}
public double getPeso()
{
return peso;
}
}
</source>
====Clase Nodo====
Hace referencia a un nodo del grafo, guardando un nombre y una serie de enlaces a otros nodos.
<source lang="java">
import java.util.ArrayList;
import javax.swing.JOptionPane;
public class Nodo
{
private String nombre;
private ArrayList<Enlace> enlaces;
private int enlacesExistentes;
public ArrayList<Enlace> getEnlaces()
{
return enlaces;
}
public Nodo(String newName)
{
nombre = newName;
enlacesExistentes = -1;
enlaces = new ArrayList<Enlace>();
}
public int getEnlacesExistentes()
{
return enlacesExistentes;
}
public String getNombre()
{
return nombre;
}
public void agregarEnlace(String enlazar,double peso)
{
if (enlacesExistentes == -1)
{
enlaces.add(new Enlace(enlazar,peso));
enlacesExistentes++;
}
else
{
int posicion;
posicion = existeEnlace(enlazar);
if (posicion == -1)
{
enlaces.add(new Enlace(enlazar,peso));
enlacesExistentes++;
}
}
}
public int existeEnlace(String enlazar)
{
for (int i = 0; i < enlaces.size(); i++)
{
Enlace miEnlace;
miEnlace = enlaces.get(i);
if (miEnlace.getDestino().equals(enlazar))
return i;
}
return -1;
}
public double enlacePosicion(int posi)
{
Enlace miEnlace;
miEnlace = enlaces.get(posi);
return miEnlace.getPeso();
}
public String NodoPosicion(int posi)
{
Enlace miEnlace;
miEnlace = enlaces.get(posi);
return miEnlace.getDestino();
}
boolean eliminarEnlace(int posicion)
{
if (posicion >= 0 && posicion <= enlaces.size())
{
enlaces.remove(posicion);
enlacesExistentes--;
return true;
}
else
JOptionPane.showMessageDialog(null, "No hay enlace en la posicion " + posicion);
return false;
}
}
</source>
====Clase Arco====
Guarda la referencia del nodo inicial, nodo terminal y peso de un determinado arco del grafo.
<source lang="java">
public class Arco
{
private String inicial;
private String terminal;
private float peso;
public Arco(String ini, String ter, float pes)
{
inicial = ini;
terminal = ter;
peso = pes;
}
public float getPeso()
{
return peso;
}
public void setPeso(float peso)
{
this.peso = peso;
}
public String getInicial()
{
return inicial;
}
public void setInicial(String inicial)
{
this.inicial = inicial;
}
public String getTerminal()
{
return terminal;
}
public void setTerminal(String terminal)
{
this.terminal = terminal;
}
public String toString()
{
return "(" + inicial + ", " + terminal + ", " + peso + ")";
}
}
</source>
====Clase Grafo====
Representa la estructura grafo, compuesta por nodos y arcos.
<source lang="java">
import java.util.Hashtable;
import java.util.ArrayList;
public class Grafo
{
ArrayList <String>nombres;
ArrayList <Arco>aristas;
Hashtable <String,Nodo> nodos;
public Grafo()
{
nombres=new ArrayList<String>();
nodos=new Hashtable <String,Nodo>();
aristas=new ArrayList <Arco>();
}
public void ingresarNodo(String nombre)
{
nombres.add(nombre);
nodos.put(nombre,new Nodo(nombre));
}
public void adicionarEnlace(String nodoInicial,String nodoTerminal,float peso)
{
Arco nuevo=new Arco(nodoInicial,nodoTerminal,peso);
int i=buscarIndice(nuevo.getPeso());
if(i==-1)
aristas.add(nuevo);
else
aristas.add(i,nuevo);
nodos.get(nodoInicial).agregarEnlace(nodoTerminal,peso);
nodos.get(nodoTerminal).agregarEnlace(nodoInicial,peso);
}
public boolean busarArista(Arco arco)
{
for(int i=0;i<aristas.size();i++)
{
Arco otro=aristas.get(i);
if(arco.getInicial().equals(otro.getInicial())&&arco.getTerminal().equals(otro.getTerminal())&&arco.getPeso()==otro.getPeso())
{
aristas.remove(otro);
return true;
}
}
return false;
}
public int buscarIndice(float peso)
{
for(int i=0;i<aristas.size();i++)
{
if(peso<aristas.get(i).getPeso())
return i;
}
return -1;
}
public Hashtable getNodos()
{
return nodos;
}
public void setNodos(Hashtable<String,Nodo > muchos)
{
nodos=muchos;
}
public ArrayList<String> getNombres()
{
return nombres;
}
public Nodo getNodo(String nombre)
{
return (Nodo)nodos.get(nombre);
}
public ArrayList<Arco> getAristas() {
return aristas;
}
public void setAristas(ArrayList<Arco> aristas) {
this.aristas = aristas;
}
public void setNombres(ArrayList<String> nombres) {
this.nombres = nombres;
}
}
</source>
===Interfaz Gráfica===
| 