Estructuras de datos generales (grafos)

Los grafos son bases de datos generales que tienen un amplio rango de aplicaciones. Junta entidades físicas y conceptuales.

Se componen de:

• Vértices, nodos o puntos: que se encargan de representar cada una de las entidades.

• Arcos o líneas: representan relaciones entre nodos.

Un grafo puede ser dirigido. En este caso las líneas se encargan de apuntar desde un nodo a otro específico, y en caso que se quiera recorrer el grafo solo se puede hacer en esa específica dirección, se representa con la línea apuntando con una flecha al nodo que sigue. Si el grafo no está dirigido a puede recorrer en cualquiera de las dos direcciones, se puede representar como una línea sin flechas o con la línea teniendo una flecha en cada punta.

Cuando las aristas tiene un valor que denota la magnitud asociada a la relación se les llama aristas con peso. Cuando el grafo tiene aristas con peso al grado se le llama grado con peso.

En un grado indirecto:

Indegree: es el número de colas adyacentes a v.

Outdegree: es el número de cabezas adyacentes a v.

Un camino es un conjunto de nodos que forman un camino de Vo a Vn, los cuales pueden ser el mismo. Un ciclo ocurre cuándo él grafo empieza y termina en el mismo nodo. Cuando el grafo no tiene ciclos se le llama DAG.

Una lista de adyacencia es una lista enlazada donde cada elemento representa un nodo del grado. Cada nodo contiene una lista de enlaces con otros nodos.

Problema del camino más corto con un solo vértice (Algoritmo Dijkstra)

Problema de camino más corto entre todos los vértices (Algoritmo de Floyd)