Comparacion de implementacion de grafos

¿Que es un grafo?

Un grafo se define como la representación gráfica de diversos nodos también llamados vértices, los cuales se conectan mediante aristas o arcos.  Hablamos de un arco cuando la conexión seda desde un nodo a hacia un nodo b pero no recíprocamente, una arista es una conexión desde un nodo a hacia un nodo b, y la misma de b hacia a; Mediante esto se pueden clasificar 2 tipos de grafos dirigidos (cuando las conexiones entre nodos son arcos) y no dirigidos (cuando las conexiones entre nodos son mediante aristas).

Formas de implementación

Forma estática

Matriz de adyacencia

Para implementar un grafo de forma estática utilizamos una matriz de n*n en la que n es la cantidad de nodos que existen en el grafo y se asocia cada fila y cada columna a cada nodo en el grafo, los elementos que se asocian de la matriz se indican si hay un relación entre nodos o no, siendo 1 cuando hay relación y 0 cuando no hay relación.

Ejemplo:

Forma dinámica

Lista de adyacencias

Para implementar un grafo de forma dinámica se utiliza una serie de listas, en la que a cada nodo se les asocia una lista en las cuales se almacenaran las relaciones entre nodos que estas contengan.

Ejemplo:

Para implementar esto se tiene en cuenta el manejo de las operaciones para manejo de listas.