Lista de adyacencia y representación matricial del gráfico

Aunque se ven diferentes, todos tipos de graficas se puede representar de manera similar. Generalmente existen dos tipos de representación gráfica:

  1. Matriz de adyacencia
  2. Lista de adyacencia

Lista de adyacencia

La lista de adyacencia consta de listas vinculadas. Cada vértice se considera un índice de matriz y cada elemento representa una lista vinculada. Estas listas enlazadas contienen los vértices que tienen aristas con el vértice índice.

A continuación se muestra un ejemplo de una lista de adyacencia:

Lista de adyacencia

Digamos que un gráfico contiene V número de vértices y E número de aristas.

Generalmente, el espacio complexla ciudad será O(V + E).

Comunicaciones espaciales en el peor de los casosplexla ciudad será O(V2) si el gráfico dado es el gráfico completo

Matriz de adyacencia

La matriz de adyacencia se compone de una matriz 2D. Gráfico que tiene un número V de vértices, el tamaño de la matriz será VxV.

Decir, matrix[i][j] = 5. Significa que hay un borde entre los nodos i y j donde el peso es 5.

Veamos lo siguientewing Gráfico y su matriz de Adyacencia:

Matriz de adyacencia

Creamos el Matriz 2D usando estos pasos:

Paso 1) El vértice A tiene un borde directo con B y el peso es 5. Entonces, la celda en la fila A y la columna B se llenarán con 5. El resto de las celdas en la fila A se llenarán con cero.

Paso 2) Los vértices B tienen un borde directo con C y el peso es 4. Entonces, la celda en la fila B y la columna C se llenarán con 4. Las celdas restantes en la fila B se llenarán con cero ya que B no tiene un borde saliente hacia ningún otros nodos.

Paso 3) Los vértices C no tienen aristas directas con ningún otro vértice. Entonces, la fila C se llenará con ceros.

Paso 4) El vértice D tiene una arista dirigida con A y C.

  • Aquí, la celda de la fila D y la columna A tendrá un valor de 7. Las celdas de la fila D y la columna C tendrán un valor de 2.
  • El resto de las celdas de la fila D se rellenarán con ceros.

Paso 5) Los vértices E tienen un borde dirigido con B y D. La celda de la fila E y la columna B tendrán un valor de 6. Las celdas de la fila E y la columna D tendrán un valor de 3. El resto de las celdas de la fila D serán lleno de ceros.

Aquí hay algunos puntos a tener en cuenta:

  • El gráfico no tiene bucles automáticos cuando la diagonal primaria de la matriz de adyacencia es 0.
  • El Gráfico es un gráfico dirigido si los índices (a,b) y (b,a) no tienen el mismo valor. De lo contrario, el gráfico es un gráfico dirigido.
  • El gráfico será un gráfico ponderado si el valor de las celdas es superior a 1.

Hay algún problema con la matriz de adyacencia ya que requiere espacios al cuadrado. Aquí, almacenamos los bordes que no están conectados. Estos bordes asignan espacio en la memoria.

Por ejemplo, si tenemos un gráfico con 100 nodos, entonces se necesitan 10 mil celdas para almacenarlo en el RAM. Con menos aristas en el gráfico, asignar una memoria tan grande puede ser un desperdicio. Entonces, la comunicación espacialplexidad utilizando la matriz de Adyacencia será O(N2), donde N significa el número de nodos en el gráfico.