domingo, 5 de febrero de 2012

Teoria de grafos. Imprementacion de un grafo, recorrido en profundidad y anchura.





(Al final de la pagina codigo para descargar).

También te puede interesar "Implementacion en Java del Algoritmo de Dijkstra", "Aplicacion de mapas, usando grafos y Dijkstra"

Definicion de grafos: Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas). (Por Wikipedia).

-----------------------------------------------------------------------------
Existen muchas forma de representar grafos, la mas comun es usar circulos para los nodos y lineas para las aristas.
La que use para modelar y luego implemetar el grafo consiste en un arreglo de nodos, los cuales pueden apuntar a otros nodos dentro del mismo arreglo asi:


Podemos interpretarlo de la siguiente forma:
[A] tiene como adyancentes a [B],
[C],[F]
[B] tiene como adyancentes a [A],[F]
[C] tiene como adyancentes a [A],[D]
[D] tiene como adyancentes a [C]
[F] tiene como adyancentes a [A],[B]
-----------------------------------------------------------------------------

Recorrido o búsqueda en profundidad (en inglés DFS o Depth First Search): es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.
(Por Wikipedia).

Búsqueda en anchura (en inglés BFS - Breadth First Search): es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.
(Por Wikipedia).

------------------------------------------------------------------------------------------
Algorito de profundiad por Wikipedia

DFS_Visitar(nodo u)
 estado[u] ← VISITADO
 tiempo ← tiempo + 1
 d[u] ← tiempo
 PARA CADA v ∈ Vecinos[u] HACER
 SI estado[v] = NO_VISITADO ENTONCES
 padre[v] ← u
 DFS_Visitar(v)
 estado[u] ← TERMINADO
 tiempo ← tiempo + 1
 f[u] ← tiempo
Algorito de anchura por Wikipedia

 BFS(grafo G, nodo_fuente s)
{
// recorremos todos los vértices del grafo inicializándolos a NO_VISITADO,
// distancia INFINITA y padre de cada nodo NULL
for u ∈ V[G] do
{
estado[u] = NO_VISITADO;
distancia[u] = INFINITO; /* distancia infinita si el nodo no es alcanzable */
padre[u] = NULL;
}
estado[s] = VISITADO;
distancia[s] = 0;
Encolar(Q, s);
while !vacia(Q) do
{
// extraemos el nodo u de la cola Q y exploramos todos sus nodos adyacentes
u = extraer(Q);
for v ∈ adyacencia[u] do
{
if estado[v] == NO_VISITADO then
{
estado[v] = VISITADO;
distancia[v] = distancia[u] + 1;
padre[v] = u;
Encolar(Q, v);
}
}
}
}

Hosting

Particularmente puedo comentarles que el recorrido en profundidad consiste en:

1: Tener un nodo inicio.
2: Adjuntarlo a la pila.
3: Verificar si la pila esta vacia, mientras no este vacia...
4: Tomo un nodo de la pila (en el caso de la pila el ultimo que se ingresó) y lo marco como visitado.
5: Proceso el nodo que tome del paso 4
(El proceso puede ser por ej: imprimirlo).
6: Adjunto a la pila los nodos adyacente del nodo tomado en el paso 4.
7: Regreso al paso 3, hasta que la pila este vacia.

Asi implemente el metodo.

Algorito de profundiad por Rey Salcedo

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);
                }
            }
        }
    }

Para el caso del recorrido en anchura, es analogo, solo tienes que remplazar la pila por una cola (tener en cuenta que en la cola el primero en entrar es el primero en salir).

Tomemos el grafo del dibujo como ejemplo:

Lo contruimos de la siguiente forma:
----------------------------------------------

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

}

----------------------------------------------




Bueno y ya para terminar, corremos los algoritmo de Recorrido que nos arroga la siguiente 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,
----------------------------------------------
Donde lo que esta en conchete es el contenido en la pila, y lo que esta afuera es lo que sale de la pila.
Para descargar codigo fuente, clic aqui.



También te puede interesar "Implementacion en Java del Algoritmo de Dijkstra"



Comenta acerca del código.




12 comentarios:

  1. Muchas gracias por el codigo,me acavas de aclarar una duda de una tarea... saludos. ADN G1

    ResponderEliminar
  2. No he puesto a correr el codigo, pero hechandole un vistazo está muy claro y bien hecho, felicidades y gracias por compartirlo.
    Salu2

    ResponderEliminar
  3. gracias, si tienen dudas o sugerencias, no ducen en hacérmelas saber.

    ResponderEliminar
  4. podrias explicarme bien el codigo? porque no entiendo prque queda de esa manera: [A]A,
    [B]
    [BC]
    [BCF]B,C,
    [FD]F,D,

    ResponderEliminar
  5. En este caso, la respuesta es A,B,C,F,D que es lo que ha salido de la pila, por estar segun veo aplicando el recorrido en amplitud

    ResponderEliminar
  6. la parecer esta muy bien me acabas de salvar bro, necesitaba quitarme algunas dudas sobre esto

    ResponderEliminar
  7. amigo el codigo no me corre, me dice k uso una version de jdk incorrecta

    ResponderEliminar
  8. interesante aporte y buen ejemplo, saludos y agradesco tu post.

    ResponderEliminar
  9. Buen aporte!!
    De casualidad, no tienes por ahi tambien un arbol B+ tambien es bastante dificil de implementar..

    saludos!!

    ResponderEliminar
  10. como harias un programa con grafo para calcular la distancia de un punto a otro!!!???? necesito ayuda

    ResponderEliminar
    Respuestas
    1. Hola william creo que no has visto ésta entrada

      http://usandojava.blogspot.com/2012/05/implementacion-en-java-del-algoritmo-de.html

      Allí hay código que de seguro te va a servir para hacer lo que quieres, mira el código he intenta, si tienes dudas me comentas.

      Eliminar

Entrada destacada

Matriz de adyacencia para un grafo

"La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias."; aunque pa...