Aplicaciones

Estructura de Datos: Grafos

Un Grafo no es mas que un conjunto de nodos o vértices que se encuentran relacionados con unas aristas. Ademas los vértices tienen un valor y en ocasiones las aristas también y se le conoce como el costo.

Representación Gráfica de un Grafo

Como se puede ver los puntos son los nodos o vértices, y las lineas son las aristas, en el caso de la imagen es la representación gráfica de un grafo dirigido ya que las aristas tienen un único sentido, ya que de A a D se puede ir pero de D a A no. Si el grafo fuera no dirigido se podría ya que las aristas no tienen dirección.

Aplicación

La teoría de Grafos se aplica hoy en día en muchos campos, tales como en Internet, ya que cada computador es un vértice y la conexión entre ellos son las aristas, ademas se usa para hallar la ruta mas corta en empresas de transporte, y en muchas otras áreas.

Imágenes

Código

Clase Principal

package Clases;

import java.awt.BorderLayout;

import java.awt.event.ActionEvent;

import java.awt.event.ActionListener;

import java.util.Vector;

import javax.swing.*;

public class Principal extends JApplet{

PanelDibujo pd;

int max=0;

JTextField valor;

public void init(){

pd=new PanelDibujo();

add(pd);

JPanel pdatos=new JPanel();

JButton agregar=new JButton("Agregar Nodo");

agregar.addActionListener(new ActionListener(){

@Override

public void actionPerformed(ActionEvent e) {

if(max<10){

try{

Grafo gf=new Grafo(""+Integer.parseInt(valor.getText()));

pd.getVgrafos().add(gf);

pd.repaint();

repaint();

max++;

}catch(NumberFormatException ne){

JOptionPane.showMessageDialog(null, "Digite un numero valido");

}

}

}

});

valor=new JTextField(5);

pdatos.add(new JLabel("Valor Vertice" +

""));

pdatos.add(valor);

pdatos.add(agregar);

add(pdatos,BorderLayout.SOUTH);

}

}

Clase PanelDibujo

package Clases;

import java.awt.BasicStroke;

import java.awt.Color;

import java.awt.Graphics;

import java.awt.Graphics2D;

import java.util.Vector;

import javax.swing.*;

public class PanelDibujo extends JPanel {

int x=150;

int y=150;

int ancho=30;

int alto=30;

public Vector<Integer> xvs;

public Vector<Integer> yvs;

public Vector<Grafo> vgrafos;

int indice=0;

public PanelDibujo(){

vgrafos=new Vector();

xvs=new Vector<Integer>();

yvs=new Vector<Integer>();

setDoubleBuffered(true);

}

public void paintComponent(Graphics grafico){

super.paintComponents(grafico);

Graphics2D g=(Graphics2D)grafico;

if(vgrafos.size()!=0){

g.setColor(Color.WHITE);

g.fillRect(0, 0, getWidth(), getHeight());

g.setColor(Color.BLACK);

int radio = 100;

float angulo = 360/10;

angulo = (float) Math.toRadians(angulo);

for(int i=indice;i<vgrafos.size();i++){

int xv=(int)(x+radio*Math.cos(i * angulo));

int yv=(int) (y- radio * Math.sin(i * angulo));

xvs.add(xv);

yvs.add(yv);

indice++;

}

}

for(int i=0;i<vgrafos.size();i++){

for(int j=0;j<vgrafos.size();j++){

g.setStroke(new BasicStroke(2));

g.setColor(Color.BLACK);

g.drawLine(xvs.get(i)+15,yvs.get(i)+15,xvs.get(j)+15,yvs.get(j)+15);

g.setColor(Color.WHITE);

g.fillOval(xvs.get(i), yvs.get(i), ancho, alto);

g.setColor(Color.BLACK);

g.drawOval(xvs.get(i),yvs.get(i), ancho, alto);

g.drawString(""+vgrafos.get(i).obtenerDato(), xvs.get(i)+((ancho/2)-3), yvs.get(i)+((alto/2)+3));

g.setColor(Color.WHITE);

g.fillOval(xvs.get(j), yvs.get(j), ancho, alto);

g.setColor(Color.BLACK);

g.drawOval(xvs.get(j),yvs.get(j), ancho, alto);

g.drawString(""+vgrafos.get(j).obtenerDato(), xvs.get(j)+((ancho/2)-3), yvs.get(j)+((alto/2)+3));

}

}

}

public Vector<Grafo> getVgrafos() {

return vgrafos;

}

public void setVgrafos(Vector<Grafo> vgrafos) {

this.vgrafos = vgrafos;

}

}

Clase Grafo

package Clases;

import java.util.Vector;

public class Grafo {

private String dato;

public Grafo(String s){

dato=s;

}

public String obtenerDato(){

return dato;

}

}

La clase Grafo solo es para almacenar el valor de cada grafo, ademas así es mas orientada a objetos y facilita la programación.

La clase PanelDibujo es la que se encargar de dibujar los vértices o nodos y de pintar las lineas que vendrían a hacer las aristas. Ademas dibuja el valor del vértice. En esta clase hay una parte del código que es pura matemática, esto lo que hace es hacer que el grafo pinte los nodos en forma circular y así hacer que se vea mas limpia a la vista la gráfica. 

Lo que hacemos es primero calcular el angulo de separación entre nodos, por eso 360 lo divido entre 10, ya que este es el máximo de vértices a dibujar. Y luego en el para el angulo se va multiplicando por i, para poder ir moviéndose y así dibujar correctamente el grafo.

La clase Principal es la encargada de crear el campo de texto para colocar el valor del vértice a insertar y de crear el botón que va ir añadiendo vértices al grafo.