Grafos

Es una estructura de datos que consiste en un conjunto de nodos y un conjunto de arcos que establecen relaciones entre los nodos. Cada arco en un grafo se especifica por medio de un par de nodos.

Exploración de grafos
A la hora de explorar un grafo, nos encontramos con dos métodos distintos. Ambos conducen al mismo destino (la exploración de todos los vértices o hasta que se encuentra uno determinado), si bien el orden en que éstos son "visitados" decide radicalmente el tiempo de ejecución de un algoritmo, como se verá posteriormente.
En primer lugar, una forma sencilla de recorrer los vértices es mediante una función recursiva, lo que se denomina búsqueda en profundidad. La sustitución de la recursión (cuya base es la estructura de datos pila) por una cola nos proporciona el segundo método de búsqueda o recorrido, la búsqueda en amplitud o anchura.


Tipos de Grafos

Grafos Bi-direccionales
El mas simple de los grafos en donde cada arco apunta exactamente a dos nodos.

Grafos unidireccional
Cada arco apunta a un solo nodo.

Cada nodo puede apuntar a otro nodo a través de otro arco.

Grafos de Peso
En este grafo introducimos un nuevo nivel de complejidad al introducir un peso al arco que conecta los nodos.
Imaginémonos los vuelos entre aeropuertos de cierta línea aérea.

La distancia entre cada ciudad, es el peso del arco que conecta los nodos.


Implementación de Grafos

Tablas adyacentes
Siempre son cuadradas. Expresan la intersecciones de nodos ligados.

Tablas de Dirección
Está relacionado con la tabla adyacente. Este método asume que hay un número limitado de direcciones a las cuales se puede ir desde un nodo en particular.

Grafos Bi-Direccionales
La forma más simple de realizar esto sería de tener dos estructuras, un nodo y un arco. Tendríamos un arreglo o lista de nodos y un arreglo o lista de arcos.

Para encontrar si un nodo está apuntando a otro tendríamos que buscar a través de todos los nodos para encontrar la conexión. Podríamos arreglar este problema adjuntando una lista de punteros a arcos.

Grafos Uni-Direccionales
Este es el método más común y más flexible. La estructura es igual una clase nodo y una clase arco. Pero la estructura grafo tendrá una lista o arreglo de nodos no de arcos. El arco simplemente será un puntero a otro nodo.

Recorrer un grafo
Hay dos maneras de las cuales podemos recorrer un grafo:

• Recorrer por profundidad primero


• Recorrer por anchura primero

La diferencia de recorrer un grafo y un árbol es que en el árbol empezamos en la raíz en un grafo empezamos donde sea.
Procesamos todos los nodos que están accesibles desde un nodo en particular o paramos cuando encontramos un nodo específico.

Búsqueda profundidad primero
Esta búsqueda es casi exactamente igual a la búsqueda pre-orden de un árbol.





El pseudocódigo es asi:
DepthFirst( Node )
Process( Node )
Mark( Node )
For Every Child of Node
If NotMarked( Child )
DepthFirst( Child )
End If
End For
End Function

búsqueda de ancho primero
Mientras la búsqueda de profundidad procesaba todos los nodos de una rama la búsqueda de ancho procesa solo los elementos por su distancia al nodo original.
Se buscan todos los nodos a un paso del nodo después todos los nodos a dos pasos del nodo después tres pasos y sucesivamente.


Notemos como los nodos conectados al 0 se procesan primero. Después los nodos conectados al 1 y después todos conectados al 2 etc Esta es una búsqueda que va hacia afuera.

El pseudocódigo es asi:
BreadthFirst( Node )
Queue.Enqueue( Node )
Mark( Node )
While( Queue.IsNotEmpty )
Process( Queue.Front )
For Each Child of Queue.Front
if NotMarked( Child )
Queue.Enqueue( Child )
Mark( Child )
end if
end For
Queue.Dequeue()
End While
End Function
[+/-]Leer más....