ÁRBOLES Y GRAFOS

ÁRBOLES:

Los árboles son muy efectivos cuando tenemos grandes cantidades de información y lo queremos buscar o almacenar.  Un árbol es una estructura no lineal compuesta por nodos que están enlazados por medio de ramas.

Los nodos contienen la información, mientras que las ramas son las que establecen una relación entre estos nodos.

EJEMPLO: 

CLASE ARBOL BINARIO ORDENADO

package arbol;

    public class ArbolBinarioOrdenado {
    class Nodo
      {
        int info;
        Nodo izq, der;
      }
      Nodo raiz;

      public ArbolBinarioOrdenado() {
          raiz=null;
      }
      
      public void insertar (int info)
      {
          Nodo nuevo;
          nuevo = new Nodo ();
          nuevo.info = info;
          nuevo.izq = null;
          nuevo.der = null;
          if (raiz == null)
              raiz = nuevo;
          else
          {
              Nodo anterior = null, reco;
              reco = raiz;
              while (reco != null)
              {
                  anterior = reco;
                  if (info < reco.info)
                      reco = reco.izq;
                  else
                      reco = reco.der;
              }
              if (info < anterior.info)
                  anterior.izq = nuevo;
              else
                  anterior.der = nuevo;
          }
      }


      private void imprimirPre (Nodo reco)
      {
          if (reco != null)
          {
              System.out.print(reco.info + " ");
              imprimirPre (reco.izq);
              imprimirPre (reco.der);
          }
      }

      public void imprimirPre ()
      {
          imprimirPre (raiz);
          System.out.println();
      }

      private void imprimirEntre (Nodo reco)
      {
          if (reco != null)
          {    
              imprimirEntre (reco.izq);
              System.out.print(reco.info + " ");
              imprimirEntre (reco.der);
          }
      }

      public void imprimirEntre ()
      {
          imprimirEntre (raiz);
          System.out.println();
      }


      private void imprimirPost (Nodo reco)
      {
          if (reco != null)
          {
              imprimirPost (reco.izq);
              imprimirPost (reco.der);
              System.out.print(reco.info + " ");
          }
      }


      public void imprimirPost ()
      {
          imprimirPost (raiz);
          System.out.println();
      }

}

CLASE PRINCIPAL

package arbol;

public class Arbol {

    public static void main (String [] ar)
      {
          ArbolBinarioOrdenado abo = new ArbolBinarioOrdenado ();
          abo.insertar (100);
          abo.insertar (50);
          abo.insertar (25);
          abo.insertar (75);
          abo.insertar (150);
          System.out.println ("Impresion preorden: ");
          abo.imprimirPre ();
          System.out.println ("Impresion entreorden: ");
          abo.imprimirEntre ();
          System.out.println ("Impresion postorden: ");
          abo.imprimirPost ();        
      }      
    
}

Salida: 

***************************************************************************************************************************************************************************************************************************************************

GRAFOS: 

Los grafos son un conjunto de nodos o vértices que se encuentran relacionados con unas aristas. Además los nodos tienen un valor y ciertas veces las aristas también. y se conoce como el costo. 

Los grafos se aplican en muchos campos, tales como en Internet,  representando los nodos como un computador y la conexión entre ellos son las aristas, además se usa para hallar la ruta mas corta , como en el uso de GPS, para llegar por el camino más rápido. 

EJEMPLO 

public void recorrerProfundidadI(Nodo nodoInicio){
        if(nodoInicio != null){
            pila.addNodo(nodoInicio);
            while(pila.size() > 0){
                Nodo nodoVisitado = pila.getNodo();
                if(nodoVisitado.visitado == false){
                    nodoVisitado.visitado = true;
                    System.out.print(nodoVisitado.getDato()+",");                
                    llenarPilaNodosAdyacentes(nodoVisitado);
                }
            }
        }
    }

public static void llenandoGrafo(){
 grafo = new Grafo();
 
 // creamos los nodos del grafo.
 grafo.adjuntarNodo(new Nodo("A"));
 grafo.adjuntarNodo(new Nodo("B"));      
 grafo.adjuntarNodo(new Nodo("C"));
 grafo.adjuntarNodo(new Nodo("D"));
 grafo.adjuntarNodo(new Nodo("F"));
       
 grafo.crearEnlaces("A","B");// de A hacia B
 grafo.crearEnlaces("B","A");// de B hacia A
 /*
  * Lo anterior lo hacemos por ser un grafo no dirigido...
  * En caso de ser un grafo con peso esto no estaria muy bien que digamos
 */
     
 grafo.crearEnlaces("A","C");
 grafo.crearEnlaces("C","A");
        
 grafo.crearEnlaces("A","F");
 grafo.crearEnlaces("F","A");
        
//grafo.crearEnlaces("B","A");//Esta enlace ya existe
//grafo.crearEnlaces("A","B");//Esta enlace ya existe
        
 grafo.crearEnlaces("B","F");
 grafo.crearEnlaces("F","B");
        
//grafo.crearEnlaces("C","A");//Esta enlace ya existe
//grafo.crearEnlaces("A","C");//Esta enlace ya existe
        
 grafo.crearEnlaces("C","D");
 grafo.crearEnlaces("D","C");
        
//grafo.crearEnlaces("D","C");//Esta enlace ya existe
//grafo.crearEnlaces("C","D");//Esta enlace ya existe
        
//grafo.crearEnlaces("F","A");//Esta enlace ya existe
//grafo.crearEnlaces("A","F");//Esta enlace ya existe
        
//grafo.crearEnlaces("F","B");//Esta enlace ya existe
//grafo.crearEnlaces("B","F");//Esta enlace ya existe

}

SALIDA: 

----------------------------------------------
Recorrido en profundidad
[A]A,
[B]
[BC]
[BCF]F,C,
[BD]D,B,
----------------------------------------------
Recorrido en Amplitud
[A]A,
[B]
[BC]
[BCF]B,C,
[FD]F,D,
----------------------------------------------

FUENTES: 

http://www.javaya.com.ar/detalleconcepto.php?codigo=127&inicio=40

http://www.myjavazone.com/2010/12/estructura-de-datos-grafos.html

http://usandojava.blogspot.com/2012/02/escribiendo-y-leyendo-en-un-archivo-de.html