Saltar al contenido

Modelo por capas

Dos arrays

CSR (compressed sparse row, fila dispersa comprimida) pone todas las listas una detrás de otra en un solo array, vecinos, y guarda en otro array, inicio, dónde empieza la lista de cada vértice:

El mismo grafo dirigido (0→1, 0→2, 1→2, 2→0, 2→3) en CSR:

El grafo dirigido de cuatro vérticesGrafo dirigido con aristas 0→1, 0→2, 1→2, 2→0 y 2→3. El vértice 3 no tiene aristas de salida. La posición en la figura no es información.0123
El grafo dirigido: 0→1, 0→2, 1→2, 2→0 y 2→3.
Los arrays inicio y vecinosinicio tiene cinco posiciones: 0, 2, 3, 5 y 5. vecinos tiene cinco: 1, 2, 2, 0 y 3. Cada valor de inicio es una flecha hacia la posición de vecinos donde empieza la lista de ese vértice: el vértice 0 empieza en la 0, el 1 en la 2, el 2 en la 3, y el 3 y la posición final de inicio apuntan al final del array, la posición 5, porque el vértice 3 no tiene vecinos.iniciovecinos00213253541021220334vértice 0vértice 1vértice 2finvértice 3: vacío (empieza y termina en 5)
Cada flecha va de inicio[u] a la posición de vecinos donde empieza la lista de u. La lista de u termina donde empieza la del siguiente. Los dos últimos valores de inicio son 5: el vértice 3 no tiene vecinos.

Los vecinos de u son vecinos[inicio[u]] hasta vecinos[inicio[u + 1] − 1]. inicio tiene V + 1 posiciones, para que el último vértice también sepa dónde termina. El vértice 3 no tiene vecinos: inicio[3] = inicio[4] = 5.

Con inicio = [0, 3, 3, 4, 6] y vecinos = [2, 3, 1, 0, 1, 2], un grafo dirigido de 4 vértices, ¿qué vecinos tienen los vértices 1 y 3?