Lista de adyacencia en C ++

En esta publicación, utilizaremos la lista de adyacencia para describir cómo se representa un gráfico. Se emplean con frecuencia tres técnicas para ilustrar el gráfico:

1. Lista de adyacencia
2. Matriz de adyacencia
3. Una matriz de incidencia

El tema principal de este artículo será la lista de adyacencia. Primero tratemos de entender qué es realmente un gráfico antes de que nos metamos para entender mejor esta idea.

¿Qué es un gráfico??

Un gráfico tiene un número fijo de nodos o vértices. Y cada nodo está conectado por una línea, que llamamos un borde. El borde es para la comunicación entre dos vértices o nodos. Por ejemplo, en el gráfico anterior, vemos seis vértices o nodos (0, 1, 2, 3, 4 y 5). Desde el vértice o el nodo 0, podemos movernos fácilmente a Vértice 1 y 3 porque hay una conexión directa entre ellos. Pero no hay una conexión directa entre el vértice o el nodo 0 y 4.

Los gráficos se utilizan en muchas aplicaciones de la vida real para resolver problemas de red. Por ejemplo, en Facebook, el perfil del usuario es un nodo o vértice, y los amigos del usuario en la lista son nodos o vértices más diferentes que tienen conexiones directas entre ellos.

Tipos de gráficos

Hay principalmente dos tipos de gráficos, gráficos no dirigidos y gráficos dirigidos, ambos se describen en las siguientes secciones:

Gráfico no dirigido

El gráfico no dirigido es muy famoso porque es un gráfico bidireccional. Por ejemplo, a continuación hay un ejemplo de un gráfico no dirigido:

Gráfico no dirigido

En el gráfico no dirigido, podemos movernos a cualquier vértice. Por ejemplo, si hay una conexión entre los nodos A y B, entonces también podemos movernos de B a un.

Gráfico dirigido

En un gráfico dirigido, los bordes tienen bordes de dirección. Entonces, estos bordes de flecha nos dirán cómo podemos movernos en el gráfico de un vértice a otro vértice, pero solo en algunas condiciones. Por ejemplo, si hay un borde dirigido entre los nodos A y B, entonces podemos movernos rápidamente del vértice A a B, pero no de regreso de B a A, si no hay un borde dirigido de B a A a A.

Gráfico dirigido

Lista de adyacencia

La lista de adyacencia es una lista de matrices donde el tamaño de la matriz es igual al número de nodos presentes en el gráfico. Y cada nodo también tiene una subarray que representa su conectividad a otros nodos o vértices. Vamos a discutir las listas de adyacencia de ambos tipos de gráficos (no dirigidos y dirigidos).

Lista de adyacencia de gráficos no dirigidos

En el gráfico no dirigido anterior, podemos ver seis vértices (0, 1, 2, 3, 4, 5). Entonces, tenemos una variedad de seis vértices. Y cada vértice individual más tiene su propia lista vinculada o lista de adyacencia, como se muestra en la lista de adyacencia anterior. Podemos ver que el vértice 0 apunta al vértice 4 y al vértice 3.

Pero, como hemos explicado antes, un gráfico no dirigido puede moverse en ambas direcciones. Hay un borde entre los nodos 0 y 4 y una conexión directa entre 0 a 4. Pero debido al gráfico no dirigido, también hay una conexión entre 4 y 0. Es por eso que si observa la lista de adyacencia anterior, el Vértice 4 también apunta al Vértice 0. Lo mismo también es cierto en el caso del vértice 3. La lista de adyacencia del vértice 3 también apunta al vértice 0.

Lista de adyacencia del gráfico dirigido

La imagen de arriba es un gráfico dirigido, y en el lado derecho está su lista de adyacencia. En esta lista de adyacencia, podemos ver un borde directo del nodo 1 al nodo 2 pero no del nodo 2 al 1. Entonces, solo podemos movernos en una dirección, es decir, de 1 a 2. Lo mismo también está en la lista de adyacencias. No podemos ver ningún enlace del vértice 2 a 1 en la lista de adyacencia de 2.

Matriz de adyacencia

La matriz se usa en este método para representar los detalles de los vértices gráficos. El tamaño de la matriz depende del número de vértices en el gráfico. Por ejemplo, si algún gráfico tiene 5 vértices, entonces el tamaño de la matriz será de 5 x 5. En esto, la fila y la columna son los vértices mismos. La representación de la matriz de la lista de adyacencia usa 1 o 0 para llenar la matriz. El valor de 1 representa una ruta del vértice de fila al vértice de columna, pero el valor de 0 no representa la ruta entre el vértice de la fila y el vértice de la columna.

Lista de adyacencia de matriz gráfica no dirigida

En la lista de adyacencia de la matriz anterior, podemos ver que A a E es el valor 0 porque no hay camino entre ellos. Entonces, llenamos ese valor con 0. Pero hay una ruta desde el vértice B hasta A, y llenamos ese valor con 1.

Lista de adyacencia de matriz de gráficos dirigidos

En la lista de adyacencia de la matriz dirigida anteriormente, podemos ver que A a D es el valor 0 porque no hay camino de A a D, pero existe una ruta de D a A, por lo que llenamos ese valor con 1.

Matriz de incidencia

La matriz se usa en este método para representar los detalles de los vértices gráficos. El tamaño de la matriz depende del número de vértices y bordes totales en el gráfico. Por ejemplo, si algún gráfico tiene 5 vértices y 7 bordes, entonces el tamaño de la matriz será de 5 x 7. Los bordes representarán las columnas, y los vértices estarán en el lado de la fila. La representación de matriz de la lista de adyacencia utiliza 0, 1 o -1 para llenar los valores de la matriz.

El valor de 1 representa una ruta saliente desde el vértice de fila hasta el vértice de la columna, pero el valor de 0 no representa la ruta entre el vértice de la fila y el vértice de la columna. El valor de -1 representa una ruta entrante al borde del vértice de la columna.

Gráfico dirigido

Lista de adyacencia de gráfico dirigido

Código C ++ para la lista de adyacencia del gráfico dirigido

#incluir
usando el espacio de nombres STD;
// Sintaxis para crear nodo
nodo

valor int;
Nodo* siguiente;
;
// Esto almacenará los detalles del borde del gráfico (fuente y destino)
struct graphedge
INT Fuente, destino;
;
clase GraphadJacencyList
// Crear un nuevo nodo para la lista de adyacencia
Nodo* getNeighBourvertex (int Destination, nodo* head_node)
Nodo* new_node = nuevo nodo;
new_node-> valor = destino;
new_node-> next = head_node;
return new_node;

// almacenará el número total de nodos en un gráfico
int number_of_nodes;
público:
Nodo ** head_node;
GraphadJacenceList (Graphedge Graphedges [], int num, int number_of_nodes)
// Asignación de memoria dinámica
head_node = nuevo nodo*[number_of_nodes] ();
this-> number_of_nodes = number_of_nodes;
// Inicializar el nodo de cabeza para cada borde del gráfico
para (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullPtr;

para (int k = 0; k < num; k++)
int fuente = Graphedges [k].fuente;
Int Destination = Graphedges [k].destino;
Nodo* new_node = getNeighBourvertex (destino, head_node [fuente]);
head_node [fuente] = new_node;


~ GraphadJacenceList ()
para (int k = 0; k < number_of_nodes; k++)
eliminar [] head_node [k];

eliminar [] head_node;

;
void display (nodo* displayPtr)
while (displayptr != nullPtr)
cout << " adjacency list -> " << displayptr->valor;
DisplayPtr = displayPtr-> Next;

cout << endl;

int main ()
Graphedge Graphedges [] =
// Estos son valores x e y que representan un borde de x a y
0, 1, 1, 2, 2, 0, 2, 1, 3, 2, 4, 1, 3, 4
;
// Número total de nodos de 0 a 5, por lo que los nodos totales son 6
int number_of_nodes = 6;
// Este método calculará el número de bordes en el gráfico
int num_edges = sizeof (Graphedges)/sizeof (Graphedges [0]);
// Crear el gráfico
GraphadJacencyList Graph (Graphedges, num_edges, number_of_nodes);
// Muestra la lista de adyacencia del gráfico
para (int k = 0; k < number_of_nodes; k++)
cout << k;
visualización (gráfico.head_node [k]);

regresar 0;

Producción:

0 Lista de adyacencia -> 1
1 lista de adyacencia -> 2
2 Lista de adyacencia -> 1 Lista de adyacencias -> 0
3 Lista de adyacencia -> 4 Lista de adyacencias -> 2
4 Lista de adyacencia -> 1
5

Gráfico dirigido con bordes de peso

Lista de adyacencia de gráfico dirigido

Código C ++ para la lista de adyacencia del gráfico dirigido con peso

#incluir
usando el espacio de nombres STD;
// Sintaxis para crear nodo
nodo de estructura
valor int, costo;
Nodo* siguiente;
;
// Esto almacenará los detalles del borde del gráfico (fuente y destino)
struct graphedge
INT Fuente, destino, peso borde;
;
clase GraphadJacencyList
// Crear un nuevo nodo para la lista de adyacencia
Nodo* getNeighBourvertex (INT Destino, int EdgeWeight,
Nodo* head_node)
Nodo* new_node = nuevo nodo;
new_node-> valor = destino;
new_node-> cost = EdgeWeight;
new_node-> next = head_node;
return new_node;

// almacenará el número total de nodos en un gráfico
int number_of_nodes;
público:
Nodo ** head_node;
GraphadJacenceList (Graphedge Graphedges [], int num, int number_of_nodes)
// Asignación de memoria dinámica
head_node = nuevo nodo*[number_of_nodes] ();
this-> number_of_nodes = number_of_nodes;
// Inicializar el nodo de cabeza para cada borde del gráfico
para (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullPtr;

para (int k = 0; k < num; k++)
int fuente = Graphedges [k].fuente;
Int Destination = Graphedges [k].destino;
int EdgeWeight = Graphedges [k].peso borde;
Nodo* new_node = getNeighBourvertex (destino, peso borde,
head_node [fuente]);
head_node [fuente] = new_node;


GraphadJacencyList ()
para (int k = 0; k < number_of_nodes; k++)
eliminar [] head_node [k];

eliminar [] head_node;

;
void display (nodo* displayPtr, int k)
while (displayptr != nullPtr)
cout << "(" << k << ", " <<
DisplayPtr-> Value << ", " << displayptr->costo << ") ";
DisplayPtr = displayPtr-> Next;

cout << endl;

int main ()
Graphedge Graphedges [] =
// (x, y, z) => Estos son valores x e y que representan un borde
// de x a y con peso w
0, 1, 4, 1, 2, 6, 2, 0, 3, 2, 1, 5, 3, 4, 8,
4, 1, 1, 3, 2, 7
;
// Número total de nodos de 0 a 5, por lo que los nodos totales son 6
int number_of_nodes = 6;
// Este método calculará el número de bordes en el gráfico
int num_edges = sizeof (Graphedges)/sizeof (Graphedges [0]);
// Crear el gráfico
GraphadJacencyList Graph (Graphedges, num_edges, number_of_nodes);
// Muestra la lista de adyacencia del gráfico
para (int k = 0; k < number_of_nodes; k++)
cout << k;
visualización (gráfico.head_node [k], k);

regresar 0;

Producción:

0 (0, 1, 4)
1 (1, 2, 6)
2 (2, 1, 5) (2, 0, 3)
3 (3, 2, 7) (3, 4, 8)
4 (4, 1, 1)
5

Conclusión

En este artículo, hemos visto diferentes métodos para representar el gráfico. También hemos visto la matriz de incidencia, que también es un método para representar la matriz de gráficos. A continuación, discutimos otros métodos de programación de C ++ para representar la lista de adyacencia (gráficos dirigidos y ponderados). También hemos estudiado gráficos dirigidos y no dirigidos. También llegamos a saber que un gráfico no dirigido es fácil de manejar en comparación con un gráfico dirigido porque un gráfico no dirigido es un gráfico bidireccional. Después de todo, no depende de la dirección del borde como el gráfico dirigido.