Algoritmo en Java

Implementacin del Algoritmo de Kruskal en Java

1

Implementacin del Algoritmo de Kruskal en JavaEl algoritmo de Kruskal es un algoritmo de la teora de grafos que busca encontrar un rbol recubridor mnimo de un grafo dado. Aqu encontraremos una implementacin en Java incluyendo una interfaz grfica.

Descripcin del ProblemaEl algoritmo de kruskal, es un algoritmo voraz utilizado en la teora de grafos, con el fin de encontrar un rbol recubridor mnimo 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 son ordenados 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 T se transfiere a T y se borra de L. Paso 3. Si L es no vaco, volver al paso 2, de lo contrario PARAR.

LimitacionesLas nicas limitaciones que se presentan con el problema de la implementacin del algoritmo de Kruskal es la creacin 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 aux=terminal.getEnlaces(); if(aux.size()==0) return false; if(terminal.existeEnlace(aVerificar.getInicial())!=-1) return true; for(int i=0;i enlaces; private int enlacesExistentes; public ArrayList getEnlaces() { return enlaces; } public Nodo(String newName) { nombre = newName; enlacesExistentes = -1; enlaces = new ArrayList(); } 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));

3

Implementacin del Algoritmo de Kruskal en Java 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 = -45 && grado = -90 && grado < -45) control = new Point((inicial.x 50, (inicial.y + terminal.y) / 2 - 10); }

13

+

terminal.x) / 2 -

+

terminal.x) / 2 +

+

terminal.x) / 2 -

+

terminal.x) / 2 -

Point tempInicial = new Point(inicial.x + 5, inicial.y + 5), tempFinal = new Point(terminal.x + 5, terminal.y + 5); QuadCurve2D.Double quad = new QuadCurve2D.Double(); quad.setCurve(tempInicial, control, tempFinal); g.setColor(aux); g.drawString(peso + "", control.x, control.y);

Implementacin del Algoritmo de Kruskal en Java g.setColor(color); g.draw(quad); break; } } public Point getUbicacion() { return ubicacionExt; } public int getTipo() { return tipo; } public Arco getArista() { return arista; } public void setArista(Arco arista) { this.arista = arista; } public void getColor() { color = new Color(0, 128, 128); aux = Color.RED; } public void setColor(Color color) { if (color.equals(new Color(0, 128, 128))) aux = Color.RED; else aux = Color.BLUE; this.color = color; } }

14


15

Paquete PrincipalClase AlgoritmoKruskal //Implementacin del Algoritmo voraz de Kruskal. import java.util.ArrayList; public class AlgoritmoKruskal { @SuppressWarnings("unchecked") public Grafo aplicarKruskal(Grafo grafo) { Grafo rbol=new Grafo(); ArrayList nodos=grafo.getNombres(); for(int j=0;j L=(ArrayList)grafo.getAristas().clone(); Arco pro=L.get(0); rbol.adicionarEnlace(pro.getInicial(), pro.getTerminal(), pro.getPeso()); L.remove(pro); while(L.size()!=0) { pro=L.get(0); if(HayCiclo(rbol, pro,rbol.getNodo(pro.getTerminal()) , pro.getTerminal())==false) rbol.adicionarEnlace(pro.getInicial(), pro.getTerminal(), pro.getPeso()); L.remove(pro); } return rbol; } public boolean HayCiclo(Grafo g,Arco aVerificar,Nodo terminal,String N) { ArrayList aux=terminal.getEnlaces();


16

if(aux.size()==0) return false; if(terminal.existeEnlace(aVerificar.getInicial())!=-1) return true; for(int i=0;i puntos; ArrayList aristas; static JFrame frame; JButton aplicar,nuevo,recuperar; Container contenedor; JRadioButton radioNodo, radioArista, radioMod; JLabel ayuda, titulo; ButtonGroup grupo; JComboBox comboOpcionesRecta,ayudaCombo; JScrollPane panel; public JTextArea area; String ayudaNod,ayudaAri,ayudaMod,ayudaRes,ayudaNue,ayudaApl; Punto pun[]; public Lienzo lienzo; Grafo grafo; int j,i; int x,y; private int contador = 0; public Ventana() { frame = new JFrame(); contenedor=frame.getContentPane(); Font font=new Font("Verdana",Font.BOLD,11); Font font1=new Font("Verdana",Font.PLAIN,12); grafo=new Grafo(); lienzo = new Lienzo(); lienzo.setBounds(0, 0, 600, 600); lienzo.setBorder(BorderFactory.createBevelBorder(1)); lienzo.setCursor(Cursor.getPredefinedCursor(Cursor.CROSSHAIR_CURSOR)); pun = new Punto[2]; pun[0]=null; pun[1]=null; puntos = new ArrayList(); aristas = new ArrayList();

17


18

area=new JTextArea(); area.setFont(font1); panel=new JScrollPane(area); panel.setBounds(660, 270, 280, 250); titulo=new JLabel("Dibuje su grafo:"); titulo.setFont(font); titulo.setBounds(610, 20, 130, 20); ayuda=new JLabel("Ayuda:"); ayuda.setBounds(610, 200, 100, 20); ayuda.setFont(font); comboOpcionesRecta = new JComboBox(); comboOpcionesRecta.addItem("Arista"); comboOpcionesRecta.addItem("Arista Bucle"); comboOpcionesRecta.addItem("Arista Curva"); comboOpcionesRecta.setFont(font); ayudaCombo=new JComboBox(); ayudaCombo.addItem(">Como hacer un Nodo"); ayudaCombo.addItem(">Como hacer una Arista"); ayudaCombo.addItem(">Como modificar un Grafo"); ayudaCombo.addItem(">Boton 'Nuevo'"); ayudaCombo.addItem(">Boton 'Aplicar'"); ayudaCombo.addItem(">Boton'Reset'"); ayudaCombo.setFont(font); ayudaCombo.setSelectedIndex(-1); radioNodo = new JRadioButton("Crear Nodo"); radioArista = new JRadioButton("Crear Arista"); radioMod = new JRadioButton("Modificar"); radioArista.setFont(font); radioMod.setFont(font); radioNodo.setFont(font); grupo = new ButtonGroup(); grupo.add(radioNodo); grupo.add(radioArista); grupo.add(radioMod); radioNodo.setSelected(true); radioNodo.setBounds(680, 60, 120, 20); radioArista.setBounds(680, 110, 130, 20); radioMod.setBounds(820, 60, 100, 20);

Implementacin del Algoritmo de Kruskal en Java aplicar=new JButton("Aplicar"); aplicar.setBounds(670,160, 80, 20); aplicar.setFont(font); nuevo=new JButton("Nuevo"); nuevo.setBounds(760,160, 80, 20); nuevo.setFont(font); recuperar=new JButton("Reset"); recuperar.setBounds(850,160, 80, 20); recuperar.setFont(font); comboOpcionesRecta.setBounds(815, 110, 100, 20); ayudaCombo.setBounds(710,240,175,20); ayudaNod = "\nCOMO CREAR UN NODO!!!\n\n" + "1. Seleccione el RadioButton \"Crear Nodo\".\n" + "2. Haga doble click sobre el area de Dibujo.\n" + "3. Inserte el nombre del Nodo.\n" + "4. Haga click en Aceptar."; ayudaAri = "\nCOMO CREAR UNA ARISTA!!!\n\n" + "1. Seleccione el RadioButton \"Crear Arista\".\n" + "2. Seleccione el Tipo de arista que desee\n \"Arista\", \"Arista Curva\", o \"Arista Bucle\".\n" + "3. Haga click sobre el nodo que desea sea el\n nodo inicial.\n" + "4. Mantega presionado el boton del mouse\n y arrastrelo hasta el nodo terminal.\n" + "5. Suelte el boton del mouse e ingrese\n el peso de la Arista.\n" + "6. Haga click en Aceptar."; ayudaMod = "\nCOMO MODIFICAR EL GRAFO!!!\n\n" + "1. Seleccione el RadioButton \"Modificar\".\n" + "2. Haga click sobre un Nodo\n" + "3. Mantega presionado el botn del mouse \n y arrastrelo para darle una nueva\n posicin al nodo.\n" + "4. Suelte el botn del mouse."; ayudaRes = "\nBOTON RESET!!!\n\n" + " Este botn permite recuperar el estado \n" + " del Grafo antes de aplicar el Algoritmo de \n" + " Kruskal.\n"; ayudaApl = "\nBOTON APLICAR!!!\n\n" + " Este botn permite Aplicar el Algoritmo de\n" + " Kruskal al Grafo dibujado por el Usuario."; ayudaNue = "\nBOTON NUEVO!!!\n\n" + " Limpia el area de Dibujo para crear un\n" + " nuevo Grafo y poder aplicar nuevamente\n" + " el Algoritmo de Kruskal.\n"; contenedor.setLayout(null); contenedor.add(comboOpcionesRecta); contenedor.add(radioMod); contenedor.add(radioArista); contenedor.add(radioNodo); contenedor.add(ayudaCombo); contenedor.add(lienzo);

19

Implementacin del Algoritmo de Kruskal en Java contenedor.add(aplicar); contenedor.add(panel); contenedor.add(nuevo); contenedor.add(recuperar); contenedor.add(ayuda); contenedor.add(titulo); frame.setFont(font); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.setLayout(null); frame.setSize(1000, 600); frame.setLocation(10, 20); frame.setTitle("GrafoMatic Displayer"); frame.setVisible(true); lienzo.addMouseListener(this); lienzo.addMouseMotionListener(this); aplicar.addActionListener(this); nuevo.addActionListener(this); recuperar.addActionListener(this); radioNodo.addItemListener(this); radioArista.addItemListener(this); radioMod.addItemListener(this); ayudaCombo.addItemListener(this); } public void mouseClicked(MouseEvent evento) { if (evento.getClickCount() == 2&&radioNodo.isSelected()==true) { String nombre = "hay"; do { try { nombre = JOptionPane.showInputDialog(null,"Ingrese la Etiqueta del Nodo"); nombre.length(); } catch(NullPointerException e) { return; }

20

Implementacin del Algoritmo de Kruskal en Java if(grafo.getNombres().contains(nombre)||nombre==null) { JOptionPane.showMessageDialog(null,"La Etiqueta es incorrecta, recuerde que no debe haber otra igual","Ingrese de nuevo la Etiqueta",JOptionPane.ERROR_MESSAGE ); nombre="hay"; } } while(nombre=="hay"); Punto punto = new Punto((int) evento.getPoint().getX() - 5, (int) evento.getPoint().getY() - 5, nombre); grafo.ingresarNodo(nombre); punto.pintarPunto(lienzo.getGraphics()); puntos.add(punto); lienzo.setPuntos(puntos); } } public void actionPerformed(ActionEvent e) { if(e.getSource()==aplicar) { AlgoritmoKruskal nuevo=new AlgoritmoKruskal(); Grafo kruskal= new Grafo(); kruskal=nuevo.aplicarKruskal(grafo); lienzo.cambiarGrafo(kruskal); } if(e.getSource()==nuevo) { grafo=new Grafo(); lienzo.getAristas().clear(); lienzo.getPuntos().clear(); lienzo.getNeo().clear(); aristas.clear(); lienzo.punto=false; lienzo.repaint(); } if(e.getSource()==recuperar) { for(int i=0;i=0 para todo n, se concluye inmediatamente que t pertenece a O (n-1)n

Conclusiones El algoritmo de kruskal es sencillo de implementar con las herramientas adecuadas. El algoritmo de kruskal, al momento de implementarlo en algn lenguaje de programacin, no es tan ptimo con respecto a otros algoritmos que cumplen el mismo objetivo, como el de Prim, debido que al momento de implementarlo se tiene la limitante de disear un algoritmo adicional que encuentre ciclos que en este caso no es el ms ptimo. Al momento de implementar el algoritmo es ms ptimo ordenar a medida que el usuario ingresa aristas que ordenar despus de terminado el grafo. Tambin sera bueno aadir las aristas en una cola de prioridad, ya que se evita igualmente la bsqueda de la arista menor.


29

Enlaces externos Animacin del algoritmo de Kruskal [3] Creacin y solucin de laberintos por los algoritmos de Kruskal y Prim [4] Otra Animacin (incluye cdigo en JAVA) [5]

Referencias[1] [2] [3] [4] [5] http:/ / java. sun. com/ javase/ downloads/ index_jdk5. jsp http:/ / www. geocities. com/ chungara/ configurar. html http:/ / students. ceid. upatras. gr/ ~papagel/ project/ kruskal. htm http:/ / www. cut-the-knot. org/ Curriculum/ Games/ Mazes. shtml http:/ / www-b2. is. tokushima-u. ac. jp/ ~ikeda/ suuri/ kruskal/ Kruskal. shtml

Fuentes y contribuyentes del artculo

30

Fuentes y contribuyentes del artculoImplementacin del Algoritmo de Kruskal en Java Fuente: http://es.wikibooks.org/w/index.php?oldid=175810 Contribuyentes: Muro de Aguas, 4 ediciones annimas

Fuentes de imagen, Licencias y contribuyentesImagen:GrafoKruskal1.PNG Fuente: http://es.wikibooks.org/w/index.php?title=Archivo:GrafoKruskal1.PNG Licencia: Public Domain Contribuyentes: Hectorhuol, Santosga Imagen:GrafoKruskal2.PNG Fuente: http://es.wikibooks.org/w/index.php?title=Archivo:GrafoKruskal2.PNG Licencia: Public Domain Contribuyentes: Hectorhuol, Santosga

LicenciaCreative Commons Attribution-Share Alike 3.0 Unported //creativecommons.org/licenses/by-sa/3.0/

Documents

Algoritmo en Java