Structures de données pour le stockage des graphes: un examen de l'existant et deux "presque nouveaux"

Bonjour à tous.

Dans cette note, j'ai décidé d'énumérer les principales structures de données utilisées pour stocker des graphiques en informatique et de parler également de quelques autres structures qui se sont cristallisées par moi-même.

Commençons donc. Mais pas depuis le tout début - je pense ce qu'est un graphique et ce qu'il est (orienté, non orienté, pondéré, non pondéré, avec plusieurs bords et boucles ou sans eux), nous le savons tous déjà.

Alors allons-y. Quelles sont les options pour les structures de données pour le "stockage graphique" que nous avons.

1. Structures de données matricielles

1.1 Matrice d'adjacence. La matrice d'adjacence est une matrice où les en-têtes de ligne et de colonne correspondent aux numéros des sommets du graphique, et la valeur de chacun de ses éléments a (i, j) est déterminée par la présence ou l'absence d'arêtes entre les sommets i et j (il est clair qu'une telle matrice pour un graphique non orienté sera symétrique, eh bien, ou vous pouvez convenir que nous stockons toutes les valeurs uniquement au-dessus de la diagonale principale). Pour les graphiques non pondérés, a (i, j) peut être spécifié par le nombre d'arêtes de i à j (s'il n'y en a pas, alors a (i, j) = 0), et pour les courbes pondérées, par le poids (poids total) des arêtes mentionnées.

1.2 La matrice d'incidence. Dans ce cas, notre graphique est également stocké dans un tableau, dans lequel, en règle générale, les numéros de ligne correspondent aux numéros de ses sommets, et les numéros de colonne correspondent à des bords prénumérotés. Si le sommet et le bord sont incidents l'un à l'autre, alors une valeur non nulle est écrite dans la cellule correspondante (pour les graphiques non orientés, 1 est écrit dans le cas de l'incidence du sommet et du bord, pour les graphiques orientés "1" si le bord "quitte" le sommet et "-1" si c'est le cas). il «entre» (on s'en souvient assez facilement, car le signe moins semble également être «inclus» dans le nombre «-1»)). Pour les graphiques pondérés, encore une fois, au lieu de 1 et -1, vous pouvez spécifier le poids total de l'arête.

2. Structures de données d'énumération

2.1 liste d'adjacence. Eh bien, tout semble simple. En général, chaque sommet d'un graphe peut être associé à n'importe quelle structure d'énumération (liste, vecteur, tableau, ...), dans laquelle les nombres de tous les sommets adjacents à celui-ci seront stockés. Pour les graphes orientés, nous ne listerons que les sommets dans lesquels il y a une arête "dirigée" de l'attribut vertex. Pour les graphiques pondérés, l'implémentation sera plus complexe.

2.2 Liste des côtes. Structure de données assez populaire. La liste des arêtes, comme nous le dit Captain Evidence, est en fait une liste des arêtes du graphique, chacune étant définie par un sommet initial, un sommet final (pour les graphiques non orientés, l'ordre n'est pas important ici, bien que différentes règles puissent être utilisées pour l'unification, par exemple, spécifiez les sommets dans l'ordre croissant) et le poids (uniquement pour les graphiques pondérés).

À propos des listes de matrices répertoriées ci-dessus, vous pouvez voir (par exemple, ici ) plus en détail.

2.3 Tableau d'adjacence. Pas la structure la plus courante. À la base, il s'agit d'une forme de «regroupement» de listes d'adjacence dans une structure d'énumération (tableau, vecteur). Les n premiers éléments (par le nombre de sommets de graphe) d'un tel tableau contiennent des indices de début du même tableau, à partir desquels tous les sommets adjacents à celui-ci sont écrits dans une rangée.

Ici, j'ai trouvé l'explication la plus compréhensible (pour moi): ejuo.livejournal.com/4518.html

3. Vecteur d'adjacence et réseau d'adjacence associatif

Cela s'est produit de sorte que l'auteur de ces lignes, n'étant pas un programmeur professionnel, mais traitant périodiquement de graphiques, s'occupait le plus souvent de listes d'arêtes. En effet, il est pratique que le graphe comporte plusieurs boucles et arêtes. Et maintenant, dans le développement des listes classiques d'arêtes, je propose de prêter attention à leur «développement / ramification / modification / mutation», à savoir: le vecteur d'adjacence et le tableau associatif d'adjacence.

3.1 Vecteur d'adjacence

Cas (A1): nombre non pondéré

Nous appellerons le vecteur d'adjacence pour un graphe non pondéré un ensemble ordonné d'un nombre pair d'entiers (a [2i], a [2i + 1], ..., où i est numéroté c 0), dans lequel chaque paire de nombres a [2i], a [2i +1] définit le bord du graphe entre les sommets a [2i] et a [2i + 1], respectivement.
Ce format d'enregistrement ne contient aucune information indiquant si le graphique est orienté (les deux options sont possibles). Lors de l'utilisation du format digraph, on suppose que le bord est dirigé d'un [2i] vers un [2i + 1]. Ci-après: pour les graphiques non orientés, si nécessaire, les exigences relatives à l'ordre d'enregistrement des sommets peuvent être appliquées (par exemple, de sorte que le sommet avec la valeur la plus basse du nombre qui lui est attribué passe en premier).

En C ++, il est conseillé de spécifier le vecteur d'adjacence en utilisant std :: vector, à partir duquel le nom de cette structure de données a été choisi.

Cas (a2): graphique non pondéré, poids de bord entiers

Par analogie avec le cas (a1), nous appelons le vecteur d'adjacence pour un graphe pondéré avec des poids de bord entiers un ensemble ordonné (tableau dynamique) de nombres (a [3i], a [3i + 1], a [3i + 2], ..., où i est numérotée c 0), où chaque "triplet" des nombres a [3i], a [3i + 1], a [3i + 2] définit le bord du graphique entre les sommets sous les nombres a [3i] et a [3i + 1], respectivement, et la valeur de [3i + 2] est le poids de cette arête. Un tel graphique peut également être orienté ou non.

Cas (b): graphique non pondéré, poids de bord non entiers

Comme les éléments hétérogènes ne peuvent pas être stockés dans un seul tableau (vecteur), l'implémentation suivante est possible, par exemple. Le graphique est stocké dans une paire de vecteurs, dans lesquels le premier vecteur est le vecteur d'adjacence du graphique sans indiquer de poids, et le deuxième vecteur contient les poids correspondants (une implémentation possible pour C ++ est: std :: pair <std :: vector, std :: vector>). Ainsi, pour une arête définie par une paire de sommets sous les indices 2i, 2i + 1 du premier vecteur, le poids sera égal à l'élément sous l'indice i du deuxième vecteur.

Eh bien, pourquoi est-ce nécessaire?

Eh bien, pour l'auteur de ces lignes pour résoudre un certain nombre de problèmes, cela semblait très utile. Eh bien, d'un point de vue formel, il y aura de tels avantages:

• Le vecteur d'adjacence, comme toute autre structure "énumérative", est suffisamment compact, prend moins de mémoire que la matrice d'adjacence (pour les graphiques clairsemés), est relativement facile à implémenter.
• Les sommets du graphique, en principe, peuvent être marqués par des nombres négatifs. Du coup, une telle «perversion» s'impose également.
• Les graphiques peuvent contenir plusieurs arêtes et plusieurs boucles, avec des pondérations différentes (positives, négatives, voire nulles). Il n'y a aucune restriction ici.
• Et les côtes peuvent avoir des propriétés différentes - mais à ce sujet, voir le paragraphe 4.

Cependant, je dois admettre que cette «listot» n'implique pas un accès rapide à la côte. Et ici, le tableau d'adjacence associative se dépêche d'aider, dont - ci-dessous.

3.2 Tableau d'adjacence associative

Donc, si pour nous l'accès à un bord particulier, son poids et d'autres propriétés sont critiques et que les besoins en mémoire ne permettent pas l'utilisation d'une matrice d'adjacence, alors réfléchissons à la façon dont vous pouvez changer le vecteur d'adjacence pour résoudre ce problème. Ainsi, la clé est le bord du graphique, qui peut être défini comme une paire ordonnée d'entiers. À quoi ça ressemble? Serait-ce une clé dans un tableau associatif? Et si oui, pourquoi ne mettons-nous pas cela en œuvre? Ayons un tel tableau associatif, où chaque clé - une paire ordonnée d'entiers - sera associée à une valeur - un entier ou un nombre réel qui spécifie le poids du bord. En C ++, il est conseillé d'implémenter cette structure sur la base du conteneur std :: map (std :: map <std :: pair <int, int>, int> ou std :: map <std :: pair <int, int>, double>) ou std :: multimap si plusieurs arêtes sont supposées. Eh bien, et ici nous avons une structure pour stocker des graphiques, qui prend moins de mémoire que les structures «matricielles», peut définir des graphiques avec plusieurs boucles et arêtes et même sans exigences strictes pour la non-négativité des nombres de sommets (je ne sais pas qui en a besoin, mais quand même).

4. Les structures de données sont au moins «inondées», mais quelque chose manque

Et la vérité est: lors de la résolution d'un certain nombre de problèmes, nous devrons peut-être attribuer certains attributs aux bords du graphique et, en conséquence, les stocker. S'il est possible de réduire sans ambiguïté ces caractéristiques en nombres entiers, il est possible de stocker de tels «graphiques avec des caractéristiques supplémentaires» en utilisant des versions étendues du vecteur de contiguïté et du tableau de contiguïté associatif.

Donc, ayons un graphe non pondéré, pour chaque arête dont il faut stocker, par exemple, 2 signes supplémentaires spécifiés par des entiers. Dans ce cas, il est possible de spécifier son vecteur d'adjacence comme un ensemble ordonné non pas de «paires», mais de «quatuors» d'entiers (a [2i], a [2i + 1], a [2i + 2], a [2i + 3] .. .), où un [2i + 2] et un [2i + 3] détermineront les caractéristiques du bord correspondant. Pour un graphique avec des poids de bord entiers, l'ordre est généralement similaire (la seule différence est que les signes suivent le poids du bord et sont donnés par les éléments a [2i + 3] et a [2i + 4], et le bord lui-même sera spécifié pas 4, mais 5 numéros ordonnés). Et pour un graphique avec des poids de bord non entiers, les attributs peuvent être écrits dans sa composante non pondérée.

Lorsque vous utilisez un tableau de contiguïté associatif pour les graphiques avec des poids de bord entiers, il est possible de spécifier non pas un nombre individuel, mais un tableau (vecteur) de nombres qui spécifient, en plus du poids du bord, tous ses autres attributs nécessaires. En même temps, l'inconvénient pour le cas des poids non entiers sera la nécessité de spécifier un caractère avec un nombre à virgule flottante (oui, c'est un inconvénient, mais s'il n'y a pas tellement de tels signes, et si vous ne les définissez pas trop "délicat" double, alors ce ne sera peut-être rien) . Et donc, en C ++, les tableaux d'adjacence associative étendue peuvent être définis comme suit: std :: map <std :: pair <int, int>, std :: vector> ou std :: map <std :: pair <int, int>, std :: vector, avec la première valeur dans "vector-value-by-key" est le poids du bord, puis les désignations numériques de ses caractéristiques sont localisées.

Références:

À propos des graphiques et algorithmes en général:

1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithmes: construction et analyse, 2e édition: Per. de l'anglais - M.: Williams Publishing House, 2011.
2. Harari Frank. Théorie des graphes. M .: Mir, 1973.
Le rapport de l'auteur sur ces mêmes vecteurs et tableau associatif d'adjacence:
3. Chernoukhov S.A. Vecteur d'adjacence et tableau d'adjacence associatif comme moyens de représenter et de stocker des graphiques / SA Chernouhov. Vecteur d'adjacence et carte d'adjacence comme structures de données pour représenter un graphique // Collection d'articles de la conférence internationale scientifique et pratique "Problèmes de mise en œuvre des résultats de développements innovants et moyens de les résoudre" (Saratov, 14 septembre 2019). - Sterlitamak: AMI, 2019, p. 65-69
Sources Internet utiles sur le sujet:
4.prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html