tda - Hacer una lista de adyacencia en C++ para un gráfico dirigido

lista de adyacencia python

Question

Hola a todos :) Hoy estoy perfeccionando mis habilidades en teoría de grafos y estructuras de datos. Decidí hacer un pequeño proyecto en C ++ porque ha pasado un tiempo desde que trabajé en C ++.

Quiero hacer una lista de adyacencia para un gráfico dirigido. En otras palabras, algo que se ve así:

0-->1-->3
1-->2
2-->4
3-->
4-->

Esto sería un gráfico dirigido con V0 (vértice 0) que tiene un borde a V1 y V3, V1 tiene un borde a V2, y V2 tiene un borde a V4, como este:

V0----->V1---->V2---->V4
 |
 |
 v
 V3 

Sé que para hacer esto, necesitaré crear una lista de adyacencia en C ++. Una lista de adyacencia es básicamente una matriz de listas enlazadas . De acuerdo, veamos un código pseudo C ++:

#include <stdio>
#include <iostream>
using namespace std;

struct graph{
//The graph is essentially an array of the adjList struct.  
node* List[];

};

struct adjList{
//A simple linked list which can contain an int at each node in the list.

};

struct node {
int vertex;
node* next;
};

int main() {
//insert cool graph theory sorting algorithm here
}

Como puede ver, este pseudocódigo está actualmente lejos de la marca. Y eso es lo que quería algo de ayuda: los punteros y las estructuras en C ++ nunca han sido mi fuerte. En primer lugar, esto cuida de los vértices que señala un vértice, pero ¿qué pasa con el vértice mismo? ¿Cómo puedo seguir ese vértice? Cuando recorro la matriz, no me servirá de nada saber solo a qué vértices se apunta, en lugar de saber qué puntos tienen para ellos. El primer elemento en cada lista probablemente sea ese vértice, y luego los elementos posteriores son los vértices a los que apunta. Pero entonces, ¿cómo puedo acceder a este primer elemento de la lista en mi programa principal? (lo siento si esto es intrincado o confuso, me gustaría volver a expresarlo).

Me gustaría poder recorrer esta lista de adyacencia para hacer algunas cosas interesantes con gráficos. Por ejemplo, para implementar algunos algoritmos de teoría de gráficos (géneros, caminos más cortos, etc.) usando la representación de la lista de adyacencia.

(Además, tenía una pregunta sobre la lista de adyacencia. ¿Qué es diferente a solo usar una lista de matrices? ¿Por qué no puedo simplemente tener una lista con una matriz en cada elemento de la lista?)

Answer 1

Este puede no ser un enfoque muy general, pero es así como manejo la lista de adyacencia en la mayoría de los casos. C ++ tiene una biblioteca STL que admite una estructura de datos para la lista vinculada nombrada como list .

Supongamos que tiene N nodos en el gráfico, cree una lista vinculada para cada nodo.

list graph[N];

Ahora la graph[i] representa los vecinos del nodo i. Para cada ventaja i a j, haz

graph[i].push_back(j);

La mejor comodidad es no manejar punteros así como errores de fallas de segmentación.

Para más referencia http://www.cplusplus.com/reference/list/list/

Answer 2

Le sugiero que agregue en la estructura del nodo, la Lista de adyacencia Y defina la estructura del gráfico como Lista de nodos en lugar de Lista de listas de adyacencia :)

struct node {
    int vertex;
    node* next;
    adjList m_neighbors;
};
struct graph{
    //List of nodes
};

Answer 3

Puede usar un vector en un nodo, como una lista de adyacencia.

class node {
  int value;
  vector<node*> neighbors;
 };

Si el gráfico se conoce en tiempo de compilación, puede usar una matriz , pero es "un poco" más difícil. Si conoce el tamaño del gráfico (en tiempo de compilación), puede hacer algo como eso.

template<unsigned int N>
class graph {
  array<node, N> nodes;
 }

Para agregar un vecino, haz algo como eso (no olvides numerar desde cero):

nodes[i].neighbors.push_back(nodes+j); //or &nodes[j]

Por supuesto, puede hacer una lista de adyacencia sin puntero y trabajar "arriba" de una tabla. Que tiene vector<int> en el nodo y empuja el número de vecinos. Con ambas representaciones del gráfico, puede realizar todos los algoritmos que usan la lista de adyacencia.

Y finalmente, podría agregar. Algunos usan una lista en lugar de un vector, porque la eliminación está en O (1) vez. Error. Para la mayoría de los algoritmos, el orden en la lista de adyacencia no es importante. Entonces puedes borrar cualquier elemento del vector en O (1) vez. Simplemente cambie el último elemento, pop_back es O (1) complejidad. Algo como eso:

if(i != number_of_last_element_in_list) //neighbors.size() - 1
 swap(neighbors[i], neighbor.back());
neighbors.pop_back();

Ejemplo específico (tienes vector en nodo, C ++ 11 (!)):

//creation of nodes, as previously
constexpr unsigned int N = 3;
array<node,N> nodes; //or array<node, 3> nodes;
//creating edge (adding neighbors), in the constructor, or somewhere
nodes[0].neighbors = {&nodes[1]};
nodes[1].neighbors = {&nodes[0], &nodes[1]};
//adding runtime, i,j from user, eg. i = 2, j = 0
nodes[i].neighbors.push_back(&nodes[j]); //nodes[2].neighbors = {&nodes[0]};

Creo que está claro. Desde 0 puede ir a 1 , de 1 a 0 y a sí mismo, y (como en por ejemplo) de 2 a 0 . Es un gráfico dirigido. Si no desea dirigir, debe agregar a las direcciones de ambos nodos vecinos. Puede usar números en lugar de punteros. vector<unsigned int> en el class node y empujando hacia atrás los números, sin direcciones.

Como sabemos, no necesita utilizar punteros. Aquí hay un ejemplo de eso también.

Cuando el número de vértices puede cambiar, puede usar un vector de nodos ( vector<node> ) en lugar de una matriz, y simplemente cambiar el tamaño . El resto permanece sin cambios. Por ejemplo:

vector<node> nodes(n); //you have n nodes
nodes.emplace_back(); //you added new node, or .resize(n+1)
//here is place to runtime graph generate
//as previously, i,j from user, but now you have ''vector<unsigned int>'' in node
nodes[i].neighbors.push_back(j);

¡Pero no puedes borrar un nodo, esto infringe la numeración! Si desea borrar algo, debe usar list ( list<node*> ) de punteros. De lo contrario, debe mantener vértices inexistentes. Aquí, el orden importa!

En cuanto a la línea nodes.emplace_back(); //adding node nodes.emplace_back(); //adding node , es seguro con un gráfico sin punteros. Si desea utilizar punteros, predominantemente no debería cambiar el tamaño del gráfico. Puede cambiar accidentalmente la dirección de algunos nodos, mientras agrega el vértice, cuando el vector se copiará en un lugar nuevo (sin espacio).

Una forma de manejarlo es usar la reserva , ¡aunque debe conocer el tamaño máximo del gráfico! Pero, de hecho, le recomiendo que no use el vector para mantener los vértices cuando usa punteros. Si no conoce la implementación, más segura podría ser la administración de la memoria automática (punteros inteligentes, por ejemplo, shared_ptr o simplemente nueva ).

node* const graph = new node[size]; //<-- It is your graph.
//Here no address change accidentally.

¡Usar el vector como lista de adyacencia siempre está bien ! No hay posibilidad de cambiar la dirección del nodo.

Answer 4

Recomendaría el enfoque más general y simple de usar vectores y pares: #include #include

typedef std::pair<int, int> ii; /* the first int is for the data, and the second is for the weight of the Edge - Mostly usable for Dijkstra */
typedef std::vector<ii> vii;
typedef std::vector <vii> WeightedAdjList; /* Usable for Dijkstra -for example */
typedef std::vector<vi> AdjList; /*use this one for DFS/BFS */

O estilo de alias (> = C ++ 11):

using ii = std::pair<int,int>;
using vii = std::vector<ii>;
using vi = std::vector<int>;
using WeightedAdjList = std::vector<vii>;
using AdjList = std::vector<vi>;

Desde aquí: usando vectores y pares (de la respuesta de Tejas)

Para obtener información adicional, puede consultar un muy buen resumen de topcoder: Encienda C ++ con STL

Answer 5

Mi enfoque sería usar un mapa hash para almacenar la lista de nodos en el gráfico

class Graph {
private:
  unordered_map<uint64_t, Node> nodeList;
  ...
}

El mapa toma la ID del nodo como clave y el nodo como valor. De esta forma, podría buscar un nodo en el gráfico en tiempo constante.

El nodo contiene la lista de adyacencia, en este caso como un vector c ++ 11. También podría ser una lista vinculada, aunque para este caso de uso no vería una diferencia en la eficiencia. Tal vez la lista sería mejor si desea mantenerlo ordenado de alguna manera.

class Node{
    uint64_t id;     // Node ID
    vector<uint64_t> adjList;  
...
}

Con este enfoque, debe pasar por la lista de adyacencia y luego buscar el mapa en la ID para obtener el nodo.

Como alternativa, podría tener un vector de punteros a los nodos vecinos en sí. Eso le daría acceso directo a los nodos vecinos, pero luego no podría usar un mapa para mantener todos sus nodos en el gráfico, y perdería la posibilidad de buscar entradas fácilmente en su gráfico.

Como puede ver, hay muchas decisiones de compromiso que debe tomar al implementar un gráfico, todo depende de sus casos de uso.