Grafos

Los grafos son estructuras de datos generales que tienen un rango grande de aplicaciones.

Un nodo de un grafo, a diferencia de un nodo de un árbol, si puede tener varios padres.Un grafo agrupa cantidades físicas y conceptuales, un grafo está compuesto de:

• Vértices-Nodos-Puntos
• Aristas-Arcos-Líneas

Un grafo es denotado como G = {V,A}, con V y A conjuntos.

Un grafo puede ser:

• Dirigido: presenta lineas con direcciones para marcar rutas.
• No Dirigido: presentan lineas sin dirección, donde puede viajar en ambas direcciones.

Una arista puede tener un peso asociado que se relaciona con el costo de traslado entre ambos nodo. En los grafos no dirigidos el peso de un nodo es la cantidad de aristas que conectan con el.

Cuando tenemos un grafo dirigido, sus nodos tendrán un grado de input y output, este es la cantidad de aristas que entran al nodo y la cantidad de aristas que salen desde ese nodo, respectivamente.

Una ruta P es un conjunto de vértices que conforman el camino hacia un vértice.

P = (v0, v1, v2, ... , vN)

Si los vértices entre v0 y vN son diferentes, se tiene una ruta simple.

Un ciclo es una ruta simple que inicia y termina en el mismo lugar,con vértices diferentes a lo largo de la ruta, no importa si v0 es igual a vn pero dentro de la ruta no se puede repetir, esto para considerarla simple.

DAG: Es un gráfico acíclico, no posee ciclos.

Grafo conectado : cuando existe una ruta hacia cualquier nodo, no tiene que ser directo; mientras haya alguna manera de llegar a cualquier nodo.

Si un grafo es conectado y además es dirigido, tenemos un grafo fuertemente conectado

Existen dos formas de representar grafos:

Listas de Adyacencias:

Se pone una lista vertical con todos los nodos del grafo y junto a cada elemento de la lista o nodo del grafo, se le añaden nuevos nodos como si fuera una lista enlazada,de esta manera podemos saber con que otros nodos tenía relaciones.

Matriz de Adyacencias:

Si es no dirigido se pone un 1 si entre ambos nodos si hay conexión, caso contrario se pone 0. Si es dirigido y posee pesos se hace lo mismo, únicamente que en vez de poner 1 se ponen los pesos, los 0 se mantienen.

Breadth-First

Utiliza una cola FIFO, el primero que entró es el primero que visito.

Depth First

Es de tipo LIFO, y trabaja con pila, ultimo que entro primero en salir.