Aplicaciones De Grafos En La Computación

Aplicaciones de grafos y arboles en la computación
Definición de grafo:
Desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto es oportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre loindica es la representación (para nuestro caso) gráfica de los datos de una situación particular, ejemplo:
 
 Los datos contienen, en algunos casos, relaciones entre ellos que no es necesariamente jerárquica. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas como se ve en la figura anterior (más adelante se presentaran grafos con estructuras dedatos); la estructura de datos que refleja esta relación recibe el nombre de grafo.
Se suelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellos son “elemento”, “ítem”, “asociación de ítems”, “registro”, “nodo” y “objeto”. El nombre que se utiliza depende del tipo de estructura, el contexto en que usamos esa estructura y quien la utiliza.
BÚSQUEDA ENGRAFOS  
Para efectuar una búsqueda de los vértices de un grafo, se pueden emplear dos estrategias diferentes:
 Búsqueda en profundidad  (BEP): Se comienza en cualquier vértice y en cada paso se avanza a un nuevo vértice adyacente siempre que se pueda. Cuando todos los adyacentes a X hayan sido visitados, se retrocede al vértice desde el que se alcanzó X y se prosigue. Así se consigue etiquetar(visitar) todos los vértices de la componente conexa en que se encuentre el vértice inicial.
Esta técnica se utiliza cuando necesitamos encontrar respuesta a un problema sobre un grafo sin condiciones de optimización.
La idea en general de la búsqueda en profundidad comenzando en un nodo A es la siguiente:
Primero examinamos el nodo inicial A. Luego examinamos cada nodo N de un camino P que comienceen A; a sea, procesamos un vecino de A, luego un vecino de un vecino de A y así sucesivamente, hasta llegar a un punto muerto o final del camino P, y de aquí volvemos atrás por Phasta que podamos continuar por otro camino P´ y así sucesivamente.
Este algoritmo es similar al del recorrido inorden de un árbol binario, y también a la forma en que se debe pasar a través de un laberinto. Observe que sehace uso una pila en lugar de una cola, y este es el detalle fundamental que hace la diferencia para realizar la búsqueda en profundidad.
 
Algoritmo para la búsqueda en profundidad:
Este algoritmo realiza la búsqueda en profundidad el grafo G comenzando en un nodo A.
1.     Inicializar todos los nodos al estado de preparado (ESTADO=1)
2.     Meter el nodo inicial A en la pila y cambiar su estado aestado de espera (ESTADO=2).
3.     Repetir los pasos 4 y 5 hasta que la pila este vacia.
4.          Sacar el nodo N en la cima de la pila. Procesar el nodo N y cambiar su
estado al de procesado (ESTADO=3).
5.          Meter en la pila todos los vecinos de N que estén en estado de
preparados (ESTADO=1) y cambiar su estado a estado de espera
(ESTADO=2).
     [ fin de bucle del paso 3 ]6.     Salir.

Búsqueda en anchura  (BEA): A diferencia con la BEP ahora se visitan todos los vecinos de un vértice antes de pasar al siguiente. Por tanto no hay necesidad de retroceder. Una vez etiquetados todos los vecinos de un vértice X, se continúa con el primer vértice alcanzado después de Xen la búsqueda.
Esta técnica se utiliza para resolver problemas en los que se pide hallar una solución óptima entrevarias.
En general la búsqueda en anchura comenzando de un nodo de partida A es la siguiente:
Primero examinamos el nodo de partida A.
Luego examinamos todos los vecinos de A. Luego examinamos todos los vecinos de los vecinos de A y así sucesivamente. Con el uso de una cola, garantizamos que ningún nodo sea procesado más de una vez y usando un campo ESTADO que nos indica el estado actual de...