¿Que es un Grafo?
Un grafo es una estructura de datos, específicamente es un tipo abstracto de datos (TAD), que consiste en un grupo de nodos a los cuales también le podemos llamar vértices y un grupo de aristas que establecen relaciones entre las vértices. El concepto de grafo TAD tiene su origen directamente del concepto matemático de grafo.
Se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E las aristas. Un grafo, G, es definido como un par ordenado, G = (V, E), donde V es un conjunto n finito de vértices u, v, wque pertenecen a V y E es un conjunto m de aristas que consta de dos elementos de V.
- GRAFO DIRIGIDO:
- GRAFO NO DIRIGIDO:
Un Grafo no Dirigido se diferencia de un Grafo Dirigido debido a que cada arista en E es un par no ordenado de vértices. Si (v,w) es una arista no dirigida è(v,w) = (w,v).
MATRIZ ADYACENTE
La Matriz Adyacente A de un Grafo G=(V,E) tiene V*V elementos y se define como:
LISTA ADYACENTE
La lista de adyacencia para un vértice v es una lista enlazada de todos los vértices w adyacentes a v. Un grafo puede ser representado por |v| listas de adyacencias, una para cada vértice.
ARREGLOS PARA LA LISTA DE ADYACENCIA
Se utilizan los arreglos para implementar la Lista de Adyacencia: