Quando as listas ou matrizes de adjacência são a melhor escolha?

Disseram-me que usaríamos uma lista se o gráfico for escasso e uma matriz se o gráfico for denso . Para mim, é apenas uma definição bruta. Não vejo muito além disso. Você pode esclarecer quando seria a escolha natural a fazer?

Desde já, obrigado!

Antes de tudo, observe que esparso significa que você tem muito poucas arestas e denso significa muitas arestas, ou gráfico quase completo. Em um gráfico completo, você tem arestas, em que n é o número de nós.$n(n-1)/2$$n$

Agora, quando usamos representação matricial que alocar matriz de armazenamento de informações nó-conectividade, por exemplo, M [ i ] [ j ] = 1 se houver borda entre os nós i e j , caso contrário, M [ i ] [ j ] = 0 . Mas se usarmos a lista de adjacência, teremos uma matriz de nós e cada nó apontará para sua lista de adjacência contendo SOMENTE os nós vizinhos .$n\times n$$M[i][j] = 1$$i$$j$$M[i][j] = 0$

Agora, se um gráfico é escasso e usamos a representação matricial, a maioria das células da matriz permanece sem uso, o que leva ao desperdício de memória. Portanto, geralmente não usamos representação matricial para gráficos esparsos. Preferimos lista de adjacência.

Mas se o gráfico é densa, em seguida, o número de arestas é perto de (a completa) , ou para n 2 , se o gráfico está dirigida com auto-loops. Então não há vantagem em usar a lista de adjacência sobre a matriz.$n(n-1)/2$$n^2$

Em termos de complexidade do espaço
Matriz de adjacência: Lista de adjacências: O ( n + m ) onde n é o número de nós, m é o número de arestas.$O(n^2)$
$O(n + m)$
$n$$m$

Quando o gráfico é uma árvore não direcionada,
matriz de adjacência: Lista de adjacências: O ( n + n ) é O ( n ) (melhor que n 2 )$O(n^2)$
$O(n + n)$$O(n)$$n^2$

Quando o gráfico é direcionado, completo, com auto-loops,
matriz de adjacência: Lista de adjacências: O ( n + n 2 ) é O ( n 2 ) (sem diferença)$O(n^2)$
$O(n + n^2)$$O(n^2)$

E, finalmente, quando você implementa usando matriz, verificar se existe uma aresta entre dois nós leva vezes, enquanto que com uma lista de adjacências, pode levar tempo linear em n .$O(1)$$n$

Para responder, fornecendo uma analogia simples. Se você tivesse que armazenar 6 onças de água, você (em geral) faria isso com um contêiner de 5 galões ou um copo de 8 onças?

Agora, voltando à sua pergunta. Se a maioria da sua matriz está vazia, por que usá-la? Apenas liste cada valor. No entanto, se sua lista é realmente longa, por que não usar apenas uma matriz para condensá-la?

O raciocínio por trás da lista versus matriz é realmente simples neste caso.

PS uma lista é realmente apenas uma matriz de coluna única !!! (tentando mostrar o quão arbitrária é uma decisão / cenário)

Considere um gráfico com nós e arestas E. Ignorando termos de ordem inferior, uma matriz de bits para um gráfico usa N 2 bits, não importando quantas arestas existem.$N$$E$$N^2$

Quantos bits você realmente precisa?

Supondo que as arestas sejam independentes, o número de gráficos com nós e E arestas é ( N $N$$E$ . O número mínimo de bits necessário para armazenar este subconjunto élog${N^2 \choose E}$$\log_2 {N^2 \choose E}$

Assumiremos sem perda de generalidade que $E \le \frac{N^2}{2}$

Se ,log2$E = \frac{N^2}{2}$, portanto a representação da matriz é assintoticamente ideal. SeE$\log_2{N^2 \choose E} = N^2 + o(N^2)$$E \ll N^2$

$\log_2 N$$2E$

$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.