representación de los grafos
Un grafo Dirigido o No-Dirigido se puede representar mediante:
Matriz de Adyacencia:
La Matriz Adyacente A de un Grafo G=(V,E) tiene V*V elementos y se define como:
primera explicación por video
el dibujo de aquí abajo:
VENTAJA:
Se puede determinar en un tiempo fijo y constante si un enlace(arco) pertenece o no al grafo.
DESVENTAJAS:
Se requiere un almacenamiento |v|*|v|. Es decir O(n2).
Lista de Adyacencia:
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.
video de lista adyacente
en este dibujo se refleja las listas adyacentes:
VENTAJAS:
La lista de adyacencia requiere un espacio proporcional a la suma del número de vértices más el número de enlaces(arcos). Hace buen uso de la memoria.
DESVENTAJAS:
La representación con lista de adyacencia es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que pueden haber O(n) vértices en la lista de adyacencia. Para el vértice i.
Arreglos para la Lista de Adyacencia:
Se utilizan los arreglos para implementar la Lista de Adyacencia:
un video que explica los arreglos en la lista
jonathan cofre 