¿Cuándo son las listas o matrices de adyacencia la mejor opción?

Me dijeron que usaríamos una lista si el gráfico es escaso y una matriz si el gráfico es denso . Para mí, es solo una definición cruda. No veo mucho más allá. ¿Puedes aclarar cuándo sería la elección natural hacer?

¡Gracias por adelantado!

En primer lugar, tenga en cuenta que disperso significa que tiene muy pocos bordes, y denso significa muchos bordes, o un gráfico casi completo. En un gráfico completo tiene aristas, donde n es el número de nodos.$n(n-1)/2$$n$

Ahora, cuando usamos representación matricial, asignamos matriz para almacenar información de conectividad de nodo, por ejemplo, M [ i ] [ j ] = $n\times n$$M[i][j] = 1$ si hay un borde entre los nodos y j , de lo contrario M [ i ] [ j ] = 0 . Pero si usamos la lista de adyacencia, entonces tenemos una matriz de nodos y cada nodo apunta a su lista de adyacencia que contiene SOLO sus nodos vecinos .$i$$j$$M[i][j] = 0$

Ahora, si un gráfico es escaso y usamos representación matricial, la mayoría de las celdas de la matriz permanecen sin usar, lo que conduce al desperdicio de memoria. Por lo tanto, generalmente no usamos representación matricial para gráficos dispersos. Preferimos la lista de adyacencia.

Pero si el gráfico es denso, entonces el número de aristas está cerca de (el completo) , o n 2 si el gráfico está dirigido con bucles automáticos. Entonces no hay ninguna ventaja de usar la lista de adyacencia sobre la matriz.$n(n-1)/2$$n^2$

En términos de complejidad espacial
Matriz de adyacencia: Lista de adyacencia: O ( n + m ) donde n es el número de nodos, m es el número de aristas.$O(n^2)$
$O(n + m)$
$n$$m$

Cuando el gráfico es un árbol no dirigido,
matriz de adyacencia: Lista de adyacencia: $O(n^2)$
es O ( n ) (mejor que n 2 )$O(n + n)$$O(n)$$n^2$

Cuando se dirige el gráfico, completo, con bucles automáticos y
matriz de adyacencia: Lista de adyacencia:$O(n^2)$
es O ( n 2 ) (sin diferencia)$O(n + n^2)$$O(n^2)$

Y finalmente, cuando implementa utilizando matriz, verificar si hay un borde entre dos nodos toma veces, mientras que con una lista de adyacencia, puede tomar tiempo lineal en n .$O(1)$$n$

Para responder proporcionando una analogía simple. Si tuviera que almacenar 6 onzas de agua, ¿lo haría (generalmente hablando) con un recipiente de 5 galones o una taza de 8 onzas?

Ahora, volviendo a su pregunta ... Si la mayoría de su matriz está vacía, ¿por qué usarla? Simplemente enumere cada valor en su lugar. Sin embargo, si su lista es realmente larga, ¿por qué no usar una matriz para condensarla?

El razonamiento detrás de list vs matrix realmente es así de simple en este caso.

PD: ¡una lista es realmente una matriz de una sola columna! (tratando de mostrarle cuán arbitraria es una decisión / escenario)

Considere una gráfica con nodos y E bordes. Ignorando los términos de orden inferior, una matriz de bits para un gráfico usa N 2 bits sin importar cuántos bordes haya.$N$$E$$N^2$

¿Cuántos bits necesitas realmente?

Suponiendo que los bordes son independientes, el número de gráficos con nodos y E bordes es ( N $N$$E$${N^2 \choose E}$$\log_2 {N^2 \choose E}$ .

$E \le \frac{N^2}{2}$ , es decir, que la mitad o menos de los bordes están presentes. Si este no es el caso, podemos almacenar el conjunto de "no bordes" en su lugar.

$E = \frac{N^2}{2}$$\log_2{N^2 \choose E} = N^2 + o(N^2)$$E \ll N^2$

$\log_2 N$$2E$ identificadores de nodo , es decir, una matriz de pares de índices de nodo.

$p = \frac{E}{N^2}$$- \log_2{p(1-p)}$. For $p \approx \frac{1}{2}$, the entropy is 2 (i.e. two bits per edge in the optimal representation), and the graph is dense. If the entropy is significantly greater than 2, and in particular if it's close to the size of a pointer, the graph is sparse.