grafos y arboles en java

Grafos. Conceptos fundamentales

Un grafo G es un par G = (V, E), donde V es un conjunto finito (vértices,

nodos) y E es un multiconjunto de pares no ordenados de vértices, denotados

por {x, y}, que se denominan lados, aristas, etc. En este caso decimos que x

y y son extremos de {x, y}. Denotamos V (G) por el conjunto de vértices del

grafo G y por E(G) el conjunto de lados del grafo G. Además ν(G) y ε(G)

denotan el número de vértices y el número de aristas de G respectivamente.

Puesto que E es un multiconjunto es posible que existen pares repetidos,

en este caso G tiene lados múltiples. También es posible que algún par no

ordenado de E tenga el mismo vértice repetido, en este caso decimos que

el lado es un lazo (loop) o bucle . Cuando existen lados múltiples y/o lazos

decimos que G es un multigrafo. Si no hay lados múltiples ni lazos decimos

que es un grafo simple. Un digrafo G es un par G = (V, E) donde V es un

conjunto de vértices y E es un multiconjunto de pares ordenados. Los lados

se denotan por pares ordenados, (u, v) denota el lado dirigido que tiene como

vértice inicial a u y como vértice terminal a v.

A continuación damos unas definiciones que provienen del libro de Matemá-

ticas Discreta y sus aplicaciones de Rosen [2]. Se deja al lector comparar las

diferentes definiciones

Definicion de Arbol

Un arbol es un conjunto finito de 0 o mas nodos v1,v2,...,vn tales que:

1- existe un nodo el cual se distingue de los demas, al mismo lo vamos llamar raiz

2- los demas elementos del conjuntos quedan particionados en m>=0 conjuntos disjuntos T1,T2,...,TN los cuales son arboles.

los elementos T1,T2,...,TN son llamados subarboles. Vemos aqui la naturaleza recursiva de la estructura arbol, puesto que definimos arbol en termino de arboles.

-El grado interior del nodo raiz es nulo, esto quiere decir que no
existen ramificaciones de entrada hacia el.

-Los nodos que tienen grado exterior=0 se dicen que son nodos hojas de un arbol.

-Se dice que un arbol esta en niveles, los cuales estan determinados
por la longuitud de la trayectoria desde la raiz hacia dicho nodo.


-El peso de un arbol esta determinado por el numero de nodos hojas
-La altura de un arbol es 1 mas el el mayor nivel de nodos
-Un conjunto de arboles enraizados se dice que forman un bosque.

 Arboles Binarios

Un arbol binario es un caso especial de arboles generales.
Es un conjunto finito de 0 nodos, o mas que tienen un subconjunto
disjunto de 2 nodos, uno denominado subarbol derecho y otro
subarbol izquierdo.


[+] convertir Arboles Generales a Arboles binarios

Esto se realiza obviamente porque es mas facil
representar arboles binarios que arboles generales, debido
a que la cantidad de apuntadores predecibles son 2:
subarbol derecho y subarbol izquierdo.

El algoritmo que permite realizar esta operacion de
conversion, o transformacion es el siguiente:

1- insertar aristas uniendo los nodos hermanos y eliminar
aquellas aristas que unen a los nodos hijos con su padre,
excepto el de mas a la izquierda.

2- girar este arbol aproximadamente unos 45º para distinguir
los subarboles derecho e izquierdo.


Representacion de un arbol

Un arbol se lo puede representar mediante la implementacion dinamica de memoria, esto es utilizando listas encadenadas o ligadas.

cada nodo va a tener la siguiente configuacion:

|PI|INFO|PD|

donde PI: apunta hacia el nodo izquierdo (subarbol izquierdo) de ese nodo
INFO: es el campo donde se almacena la informacion
PD: apunta hacia el nodo derecho (subarbol derecho)de ese nodo.

CLASE NODO

public class Nodo {

    private Nodo pd;
    private Object dato;
    private Nodo pi;

    public Nodo(Object dato){
        this.dato=dato;
        pd=null;
        pi=null;
    }

public Object getDato() {return dato;}

public void setDato(Object dato) {this.dato = dato;}

public Nodo getPd() {return pd;}

public void setPd(Nodo pd) {this.pd = pd;}

public Nodo getPi() {return pi;}

public void setPi(Nodo pi) {this.pi = pi;}

}

CLASE ARBOL

public class Arbol {

     private Nodo Raiz;

     public Arbol(){ Raiz=null;}

     // insertar(Raiz, Raiz, x)


      public boolean arbolVacio(){return Raiz == null;}


      public void insertar(Nodo ant, Nodo p, Nodo x){

         if (p != null){
             if (Integer.parseInt(x.getDato().toString()) >                 Integer.parseInt(p.getDato().toString())) {
                   insertar(p, p.getPd(), x);
                }else{
                   insertar(p, p.getPi(), x);
                }
            }else{
               if (arbolVacio()){
                     Raiz = x;
               }else{
                  if (Integer.parseInt(x.getDato().toString()) >  Integer.parseInt(ant.getDato().toString())) {
                    ant.setPd(x);
                  }else {
                     ant.setPi(x);
                  }
               }
            }
}

public void imprimir(Nodo p){

if(p != null){
       imprimir(p.getPi());
       System.out.print(p.getDato()+"; ");
       imprimir(p.getPd());
}
}

public Nodo getRaiz() {
   return Raiz;
}
public void setRaiz(Nodo raiz) {
    Raiz = raiz;
}


public void eliminar(Nodo ant, Nodo p){
   if(esNodoHoja(p)){
         eliminarNodoHoja(ant, p);
   }else{
        if (esNodoCon2SubArboles(p)){
              eliminarNodoCon2SubArboles(ant, p);
        }else{
           eliminarNodoCon1SubArnol(ant, p);
        }
    }
}

public void eliminarNodoHoja(Nodo ant, Nodo p){
if (Raiz != p){
   if(ant.getPd() == p){
          ant.setPd(null);
   }else{
         ant.setPi(null);
   }
}else{
   Raiz = null;
}
}



public void eliminarNodoCon1SubArnol(Nodo ant, Nodo p){
if (Raiz == p){
     if(p.getPd() != null){
         Raiz = Raiz.getPd();
     }else{
         Raiz = Raiz.getPi();
     }
}else{
     if ( ant.getPd() == p){
           if(p.getPd() != null){
                ant.setPd(p.getPd());
           }else{
               ant.setPd(p.getPi());
           }
    }else{
        if(p.getPd() != null){
            ant.setPi(p.getPd());
        }else{
           ant.setPi(p.getPi());
    }
}
}
}


public boolean esNodoHoja(Nodo p){return (p.getPi() == null && p.getPd() == null);}

public boolean esNodoCon2SubArboles(Nodo p){return (p.getPi() != null && p.getPd() != null);}

CLASE ARBOL APLICACION

mport java.io.*;


import java.io.InputStreamReader;

public class ArbolAplicacion {

       Arbol miArbol;
       BufferedReader entrada;


      public ArbolAplicacion(){
             miArbol = new Arbol();
             entrada = new BufferedReader(new InputStreamReader(System.in));
       }


       public void generar()throws Exception{
           // Nodo p = miArbol.getRaiz();
           char op='s';
           while(op !='n' && op!='N'){

           System.out.println(" Ingrese elemento");

           Object elem = entrada.readLine();
           Nodo x = new Nodo(elem);

           miArbol.insertar(miArbol.getRaiz(), miArbol.getRaiz(), x);

           System.out.println(" Continuar enter/ n");
           String opcion=entrada.readLine();
           opcion=opcion.equals("")?"a":opcion;
            op = opcion.charAt(0);

        }
     }

       public void eliminarNodo()throws Exception{
            // Nodo p = miArbol.getRaiz();
            char op='s';
            while(op !='n' && op!='N'){

            System.out.println(" Ingrese elemento");

            Object elem = entrada.readLine();
            Nodo x=new Nodo(elem);
            // Buscar
           buscarEnElArbol(miArbol.getRaiz(), miArbol.getRaiz(), x);



           System.out.println(" Continuar enter/ n");
           String opcion=entrada.readLine();
           opcion=opcion.equals("")?"a":opcion;
            op = opcion.charAt(0);

          }
        }

public void buscarEnElArbol(Nodo ant, Nodo p, Nodo x){
   if(p!=null){
if(Integer.parseInt(x.getDato().toString())==Integer.parseInt(p.getDato().toString())){
miArbol.eliminar(ant, p);
}else{
if(Integer.parseInt(x.getDato().toString())>Integer.parseInt(p.getDato().toString())){
buscarEnElArbol(p,p.getPd(),x);
}else{
buscarEnElArbol(p,p.getPi(),x);
}
}
}

}

public void imprimirArbol(){
System.out.println("=====================");
System.out.println("Elementos del arbol");
miArbol.imprimir(miArbol.getRaiz()) ;
System.out.println("");
System.out.println("=====================");}

public void mostrarOpciones(){
System.out.println("=================");
System.out.println(" Opciones de Arbol");
System.out.println("1- Generar");
System.out.println("2- Eliminar");
System.out.println("3- Imprimir");
System.out.println("Ingrese su opciones:"); }

public void menu()throws Exception{
int op = 9;
do{
switch (op) {

case 1: generar(); break;
case 2: eliminarNodo(); break;
case 3: imprimirArbol(); break;}
mostrarOpciones();
String opc = entrada.readLine();
opc = opc.equals("")?"9":opc;
op=Integer.parseInt(opc);
}while(op!=0);
}

public static void main(String[] args)throws Exception {
ArbolAplicacion mi=new ArbolAplicacion();
mi.menu();
}}

CLASE PRINCIPAL

public class Principal {


public static void main(String[] args) throws Exception {

ArbolAplicacion miA=new ArbolAplicacion();
miA.menu();

}}

COLAS EN JAVA Y PROYECTOSDE AUTOS CHUTOS EN JAVA

COLAS.- EN LAS COLAS LOS ELEMENTOS PRIMEROS EN ENTRAR SON LOS ELEMENTOS PRIMEROS EN SALIR.

EJEMPLO

CLASE NODO

public class Nodo {

   //Atributos del la clase nodo

   Object Dato;

   Nodo Sig;

   //Constructor del nodo para crear un objeto

   public Nodo(Object Valor){

   Dato=Valor;

   Sig=null;

   }

   //Constructor del nodo para crear un objeto del siguiente nodo

   public Nodo(Object Valor,Nodo Sign){

   Dato=Valor;

   Sig=Sign;

   }

}

CLASE COLA

public class Cola extends Lista{

    //Atributo de nombre de la lista

    String Nombre;

    //Constructor argumento de la clase Cola

    public Cola(String n){

    Nombre=n;

    }

    //Asignacion de nombre a la clase cola

    public Cola(){

    this("Cola");

    }

   //Metodo para ingresar datos a la cola

    public void Colar(Object Elem){

    Iposterio(Elem);

    }

    //Metodo para mostar los datos de la clase cola

    public void MostrarC(){

    Nodo Actual=Pri;

    if(ListaVacia()){

    System.out.println("La "+Nombre+" esta vacia");

    }

    else{

    System.out.println("La "+Nombre+": ");

    while(Actual!=null){

    System.out.println("|"+Actual.Dato+"||");

    Actual=Actual.Sig;

    }

    System.out.println();

    }

    }

    //Metodo para eliminar los datos de la clase Cola

    public void DColar(){

    Efrente();

    }

}

PROYECTO AUTOS CHUTOS

EN ESTE PROYECTO TRATA DE REGISTRAR TODA AQUELLAS MOBILIDADES SIN SU DOCUMENTACION.

TRATA DE REGISTRAR AQUELLOS VEHICULOS QUE TENGAN REGISTRADOS TODOS SUS DATOS CORRESPONDIENTES.CASO CONTRARIO AQUELLOS VEHICULOS QUE NO HAIGAN COMPLETADO SU REGISTRO CORRESPONDIENTE SERAN DEPURADOS DEL SISTEMA.TAMBIEN CALCULA  EL IMPUESTO A PAGAR POR SU ANTIGÜEDAD DE LOS VEHICULOS.

POR EJEMPLO:

1  -    5 AÑOS  30% DEL COSTO DEL VEHICULO

6  -   10 AÑOS 35% DEL COSTO DEL VEHICULO

10-   11 AÑOS 50% DEL COSTO DEL VEHICULO

ESTE PROYECTO ESTA BASADO AL USO DE FORMULARIOS O APLICACIONES EN JAVA MEDIANTE BOTONES,ETIQUETAS,CAJAS DE 

TEXTO Y CAJA DE TEXTO TIPO LISTA.

EJEMPLO DE LA APLICACION:

CLASE NODO:

public class Nodo {

   

    //miembros de acceso del paquete; lista puede accseder a ellos directamento

    Object datos;//los datos para este nodo

    Nodo sig;//referencia al siguiente nodo de la lista

   

    //el constructor crea un objeto Nodo que hace referencia al objeto

    Nodo(Object objeto){

        this(objeto, null);

    }

    Nodo(Object intElemento, Nodo nodo){

        datos = intElemento;

        sig = nodo;

    }

    Object obtenerObject(){

        return datos;

    }

    Nodo obtenerSiguiente(){

        return sig;

    }

   

    }

    

CLASE LISTA:

public class Lista {

       

    private Nodo pri;

    private Nodo ult;

    private String nombre;

       

    public Lista(){

        this("lista");

    }

    public Lista(String NLista){

        nombre = NLista;

        pri = ult = null;

    }

    public boolean estaVacia(){

        return pri == null;

    }

    public void insertarAlFrente(Object intElemento){

       

        if(estaVacia())

            pri = ult = new Nodo(intElemento);

        else

            pri = new Nodo(intElemento, pri);

    }

    public void InsertarPosterior(Object intElemento){

       

        if(estaVacia())

            pri = ult = new Nodo(intElemento);

        else

            ult= ult.sig = new Nodo(intElemento);

    }

    public Object eliminarDelFrente() throws CasoListavacia{

        if(estaVacia())

           

            throw new CasoListavacia(nombre);

           

        Object elementoEliminado = pri.datos;

       

        if(pri == ult)

            pri = ult = null;

        else

            pri = pri.sig;

        return elementoEliminado;

    }

    public Object eliminarDelFinal() throws CasoListavacia{

       

        if(estaVacia())

           

            throw new CasoListavacia(nombre);

           

        Object AeliminarElemento = ult.datos;

           

        if(pri == ult)

            pri = ult = null;

        else{

            Nodo actual = pri;

           

            

        while(actual.sig != ult)

            actual = actual.sig;

       

        ult = actual;

        actual.sig = null;

        }

       return AeliminarElemento;

    }

   

    public void imprimir(){

       

        if(estaVacia()){

            System.out.printf("%s Vacia\n", nombre);

        return;

    }

        System.out.printf("La %s es: ", nombre);

        Nodo actual = pri;

       

        while(actual != null){

            System.out.printf("%s ", actual.datos);

            actual = actual.sig;

        }

        System.out.println("\n");

    }

        public class CasoListavacia extends RuntimeException{

       

         public CasoListavacia(){

            this("lista");

        }

         public CasoListavacia(String nombre){

             super(nombre + "Esta Vacia");

         }

        

    }

}

CLASE PROPIETARIO

public class Propietario {

     String Nombre;

     String Direccion;

     int Ci;

    public Propietario(){

        Nombre = Direccion = "";   Ci = 0;

    }

    public Propietario(String n, String d, int c){

        Nombre =n; Direccion = d; Ci = c;

    }

    public void setNombre(String n){Nombre =n;}

    public void setDireccion(String d){Direccion = d;}

    public void setCi(int c){Ci = c;}

    public String getNombre(){return Nombre;}

    public String getDireccion(){return Direccion;}

    public int getCi(){return Ci;}

    public String GetDatos(){

        return "Nombre: "+ Nombre + "\nDireccion: " + Direccion + "\nCI: "+ Ci;

    }

}

CLASE MOTORIZADO

class Motorizado extends Propietario{

     String Tipo;//referencia a que es el vehiculo si es motocicletas o autos

     String chasis;// numero entero

     String motor;//numero entero

     int modelo;//año de fabricacion del vehiculo

     String color;

     double costo;//pago anual

     int antiguedad;

   

    public Motorizado(){

        super("","",0);

        Tipo = color =chasis = motor = "";

         antiguedad =modelo=0;

        costo = 0.0;

        //super();

    }

    Motorizado( String N, String D, int C,String t, String ch, String mo, int m, String co, double cos, int an) {

        super(N,D,C);

        Tipo = t; chasis = ch; motor =mo; modelo = m; color =co; costo = cos; antiguedad = an;   

    }

    public void setTipo(String t){Tipo = t;}

    public void setChasis(String ch){chasis = ch;}

    public void setMotor(String mo){motor = mo;}

    public void setModelo(int m){modelo = m;}

    public void setColor(String co){color = co;}

    public void setCosto(double cos){costo = cos;}

    public void setCosto(int an){antiguedad = an;}

   

    public String getTipo(){return Tipo;}

    public String getChasis(){return chasis;}

    public String getMotor(){return motor;}

    public int getModelo(){return modelo;}

    public String getColor(){return color;}

    public double getCosto(){return costo;}

    public int getAntiguedad(){return antiguedad;}

   

    public double Coste(double costo, int an){

        if(an <= 5){

            return (costo*0.30);

        }else if(an >=6 && an <=10){

            return (costo * 0.35);

        }else

            return (costo * 0.50);

    }

    public String GetDatosVehiculo(){

        return super.GetDatos() +"\nTipo: "+Tipo+"\nChasis: "+chasis+"\nMotor: "+motor+"\nModelo: "+modelo+"\nColor: "+

                color+"\nCosto: "+costo+"\nAntiguedad: "+antiguedad+"\n\nCLIENTE:\n" ;

    }

}

COMO ESTE PROYECTO FUE CREADO EN FOMULARIOS EN JAVA UTILIZAREMOS BOTONES, ETIQUETAS DE TEXTO,CAJAS DE TEXTO Y LISTAS DE TEXTOS.

BOTON REGISTRAR

//este boton registra los datos que introducimos como tambien depura si falta alguno de ellos

private void BTNGUARDARActionPerformed(java.awt.event.ActionEvent evt) {                                          

    String pro = TXTPROPIETARIO.getText();

    String di = TXTDIRECCION.getText();

    int ci = Integer.parseInt(TXTCI.getText());

    String nch = TXTNUCHASIS.getText();

    String nmo = TXTNUMOTOR.getText();

    int mod = Integer.parseInt(TXTMODELO.getText());

    double cos = Double.parseDouble(TXTCOSTO.getText());

     String col = TXTCOLOR.getText();

     int ant  = Integer.parseInt(TXTANTIGUEDAD.getText());

     String tipo = cbxtipo.getText();

     Lista reg = new Lista("REGISTRO");

     Motorizado Obj =(new Motorizado(pro,di,ci,tipo,nch,nmo,mod,col,cos,ant) );

        TXTLISTA.append(Obj.GetDatosVehiculo());

     if (!pro.equals("") && !di.equals("") && ci!=0 && !nch.equals("") &&

             !nmo.equals("") && mod!=0 && cos!=0.0 && !col.equals("") && ant!=0 && !tipo.equals("")){

         TXTACEPTADOS.append(Obj.GetDatosVehiculo()+"TOTAL A PAGAR: "+Obj.Coste(cos, ant)+"\n");

     }

 else

     DEPURADOS.append(Obj.GetDatosVehiculo()+"TOTAL A PAGAR: "+Obj.Coste(cos, ant)+"\n");

    }       

BOTON BORRAR

private void BTNBORRARActionPerformed(java.awt.event.ActionEvent evt) {                                         

String limpiar = "";

TXTPROPIETARIO.setText(limpiar);

TXTDIRECCION.setText(limpiar);

TXTCI.setText(limpiar);

TXTNUCHASIS.setText(limpiar);

TXTNUMOTOR.setText(limpiar);

TXTCOLOR.setText(limpiar);

TXTCOSTO.setText(limpiar);

TXTANTIGUEDAD.setText(limpiar);

TXTMODELO.setText(limpiar);

cbxtipo.setText(limpiar);

        // TODO add your handling code here:

    } 

BOTON SALIR

//este boton termina la ejecucion de nuestro proyecto

private void BTNSALIRActionPerformed(java.awt.event.ActionEvent evt) {                                        

        System.exit(0);

        // TODO add your handling code here:

    }    

NUESTRO PROGRAMA SE MOSTRARA DE ESTA MANERA: