Estaba resolviendo alguna pregunta en el gráfico. Requiere almacenar el peso de N nodos (N <= 50000). No puedo usar la matriz para almacenar el peso del gráfico (ya que no se pueden asignar 50000x50000). ¿Conoces alguna otra forma? Gracias.

0
Tapesh 28 ene. 2016 a las 11:23

3 respuestas

No puede asignar una matriz con un tamaño de órdenes 10 ^ 9 como memoria estática. Deberías usar malloc en su lugar. Mejor aún, puede usar lista de adyacencia para almacenar el gráfico.

-1
Saumya Singh 28 ene. 2016 a las 09:13

Generalmente, hay dos formas de representar gráficos. Como dijiste, el primero es usar una matriz de adyacencia. Las ventajas son que puede ver fácilmente si dos nodos i y j están conectados. La desventaja es la complejidad del espacio ( O (V²) donde V es el número de vértices).

La otra es la lista de adyacencia: para cada vértice, almacena una lista de adyacencia que contiene cada borde que sale de ese vértice. Obviamente, la complejidad espacial es O (V + E) donde V es el número de vértices y E el número de aristas.

Tenga en cuenta que puede almacenar los bordes en mapas de adyacencia en lugar de listas. Digamos que le da a cada borde una clave entera única. Si su gráfico es escaso, una std::unordered_map encajaría bien ya que las probabilidades de colisiones serán bajas. Esto le otorga un promedio de O (1) complejidad de búsqueda e inserción para un borde determinado.

Si su gráfico puede tener una gran cantidad de bordes, utilice un std::map normal que se base en árboles negros rojos. Entonces tendrá una complejidad logarítmica tanto para insertar como para buscar un nodo.

Aquí hay un código de muestra:

struct Edge {
    int weight;
    int start, end;
}
struct Vertex {
    int key;
    std::unordered_map<int, Edge> adjacency_map;
}
struct Graph {
    std::vector<Edge> edges;
}
0
Rerito 28 ene. 2016 a las 09:18

Si dos nodos no pueden tener varios bordes entre ellos:

Primero, piense en algún sistema para dar a cada borde existente un número único.
P.ej. para N nodos y números de nodo entre 0 y N-1, un borde entre el nodo A y el nodo B podría simplemente tener A*N+B (por ejemplo, en una variable uint64_t)

Luego haga un std::map de bordes, con el número calculado como clave y el peso como valor. La mayoría de las operaciones tienen tiempo logarítmico, que no es tan bueno como el de la matriz 2D, pero sigue siendo bueno, y necesita mucha menos memoria.

0
deviantfan 28 ene. 2016 a las 08:34