Quand les listes ou matrices d'adjacence sont-elles le meilleur choix?

On m'a dit que nous utiliserions une liste si le graphique est clairsemé et une matrice si le graphique est dense . Pour moi, c'est juste une définition brute. Je ne vois pas grand-chose au-delà. Pouvez-vous préciser quand serait-ce le choix naturel à faire?

Merci d'avance!

graphs data-structures lists adjacency-matrix user21312
la source

Connexe: stackoverflow.com/a/2218331/5746050 et stackoverflow.com/a/5419933/5746050

ryan

Ce n'est pas une définition, principalement parce qu'il n'y a pas de définition unique de "clairsemé" et "dense". En outre, il existe d'autres considérations, par exemple les aspects du graphique auxquels vous accédez à quelle fréquence.

Raphael

@Raphael Pouvez-vous entrer dans plus de détails sur les autres considérations?

user21312

@ user21312, une grande différence est l'itérabilité vs l'accès aux bords. Si vous avez souvent besoin d'itérer sur les bords, la liste adj pourrait être plus utile. Si vous devez souvent déterminer si un bord existe ou accéder à son poids (ou à d'autres informations), la matrice peut être meilleure.

ryan

Pour votre objectif, nous pourrions probablement négliger la définition de «clairsemé» et «dense». Modélisez simplement la complexité temporelle de l'opération matricielle que vous souhaitez utiliser pour chaque type de structure de données et voyez où se trouve le «point de rupture de la densité». Je pense que le deuxième lien de @ryan essaie de faire quelque chose de similaire

Apiwat Chantawibul

Réponses:

Tout d'abord, notez que clairsemé signifie que vous avez très peu d'arêtes, et dense signifie plusieurs arêtes, ou un graphique presque complet. Dans un graphique complet, vous avez arêtes, où est le nombre de nœuds. $n(n-1)/2$ $n$

Maintenant, lorsque nous utilisons la représentation matricielle, nous allouons matrice pour stocker les informations de connectivité des nœuds, par exemple, s'il y a un bord entre les nœuds et , sinon . Mais si nous utilisons la liste d'adjacence, nous avons alors un tableau de nœuds et chaque nœud pointe vers sa liste d'adjacence contenant UNIQUEMENT ses nœuds voisins . $n\times n$ $M[i][j] = 1$ $i$ $j$ $M[i][j] = 0$

Maintenant, si un graphe est clairsemé et que nous utilisons une représentation matricielle, la plupart des cellules matricielles restent inutilisées, ce qui entraîne un gaspillage de mémoire. Ainsi, nous n'utilisons généralement pas de représentation matricielle pour les graphiques clairsemés. Nous préférons la liste d'adjacence.

Mais si le graphe est dense alors le nombre d'arêtes est proche de (le complet) , ou de si le graphe est dirigé avec des auto-boucles. Il n'y a alors aucun avantage à utiliser la liste d'adjacence sur la matrice. $n(n-1)/2$ $n^2$

En termes de complexité d'espace
Matrice d'adjacence: Liste d'adjacence: où est le nombre de nœuds, est le nombre d'arêtes. $O(n^2)$
$O(n + m)$
$n$ $m$

Lorsque le graphique est un arbre non orienté, alors
Matrice d'adjacence: Liste d'adjacence: est (mieux que ) $O(n^2)$
$O(n + n)$ $O(n)$ $n^2$

Lorsque le graphique est dirigé, complet, avec auto-boucles puis
matrice d'adjacence: Liste d'adjacence: est (pas de différence) $O(n^2)$
$O(n + n^2)$ $O(n^2)$

Et enfin, lorsque vous implémentez en utilisant la matrice, vérifier s'il y a un bord entre deux nœuds prend fois, alors qu'avec une liste d'adjacence, cela peut prendre un temps linéaire en . $O(1)$ $n$

fade2black
la source

"alors qu'avec une liste de contiguïté, cela peut prendre un temps linéaire" - Étant donné que votre liste de contiguïté manque (probablement) de tout ordre naturel, pourquoi s'agit-il d'une liste au lieu d'un ensemble de hachage?

Kevin

@Kevin Ensuite, il serait appelé "hachage d'adjacence" au lieu de "liste". Aussi possible, pourquoi pas? Mais si vous faites simplement DFS ou BFS, ou une autre procédure qui analyse systématiquement tous les nœuds, quel est l'avantage d'utiliser le hachage sur la liste? Dans tous les cas, vous inspecteriez tous les nœuds adjacents.

fade2black

J'ajouterais que dans le cas non pondéré non orienté , pour un graphe presque complet, il pourrait être plus faisable de stocker son complément, c'est-à-dire un graphe clairsemé. Une matrice est donc utile quand environ la moitié des bords sont présents.

M. Winter

Pour répondre en fournissant une analogie simple. Si vous deviez stocker 6 onces d'eau, le feriez-vous (en général) avec un récipient de 5 gallons ou une tasse de 8 onces?

Maintenant, revenons à votre question. Si la majorité de votre matrice est vide, alors pourquoi l'utiliser? Inscrivez simplement chaque valeur à la place. Cependant, si votre liste est vraiment longue, pourquoi ne pas simplement utiliser une matrice pour la condenser?

Le raisonnement derrière la liste vs la matrice est vraiment aussi simple dans ce cas.

PS une liste est vraiment juste une matrice à une seule colonne !!! (en essayant de vous montrer à quel point cette décision / scénario est arbitraire)

Charles
la source

Considérons un graphique avec nœuds et arêtes. En ignorant les termes d'ordre bas, une matrice de bits pour un graphe utilise bits quel que soit le nombre de fronts. $N$ $E$ $N^2$

De combien de bits avez-vous réellement besoin?

En supposant que les arêtes sont indépendantes, le nombre de graphiques avec nœuds et arêtes est $N$ $E$ ${N^2 \choose E}$ $\log_2 {N^2 \choose E}$

$E \le \frac{N^2}{2}$

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

\log_{2} (\binom{N^{2}}{E})

$\log_2 {N^2 \choose E}$

= \log_{2} \frac{(N^{2})!}{E! (N^{2} - E)!}

$= \log_2 \frac {(N^2)!} {E! (N^2 - E)!}$

= 2 E \log_{2} N + O (low order terms)

$= 2E \log_2 N + O(\hbox{low order terms})$

If you consider that $\log_2 N$ is the size of an integer which can represent a node index, the optimal representation is an array of $2E$ node ids, that is, an array of pairs of node indexes.

Having said that, a good measure of sparsity is the entropy, which is also the number of bits per edge of the optimal representation. If $p = \frac{E}{N^2}$ is the probability that an edge is present, the entropy is $- \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.

Pseudonym
la source