Bonjour.
Dans cette note, j'ai décidé de lister les principales structures de données utilisées pour stocker des graphiques en informatique, et je parlerai également de quelques autres structures de ce type qui, d'une manière ou d'une autre, se sont « cristallisées » pour moi.
Alors, commençons. Mais pas depuis le tout début - je pense que nous savons tous déjà ce qu'est un graphique et ce qu'il est (orienté, non orienté, pondéré, non pondéré, avec ou sans plusieurs arêtes et boucles).
Alors allons-y. De quelles options disposons-nous en matière de structures de données pour le « stockage graphique » ?
1. Structures de données matricielles
1.1 Matrice de contiguïté. La matrice de contiguïté est une matrice où les en-têtes de lignes et de colonnes correspondent aux numéros des sommets du graphe, 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 que pour un graphe non orienté, une telle matrice sera symétrique, ou nous pouvons 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 défini par le nombre d'arêtes de i à j (s'il n'y en a pas, alors a(i,j)= 0), et pour les graphiques pondérés, également par le poids (poids total) des bords mentionnés.
1.2 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 colonnes correspondent aux arêtes pré-numérotées. Si un sommet et une arête sont incidents l'un par rapport à l'autre, alors une valeur non nulle est écrite dans la cellule correspondante (pour les graphes non orientés, 1 est écrit si le sommet et l'arête sont incidents, pour les graphes orientés - « 1 » si l'arête "sort" du sommet et "-1" s'il y "inclut" (c'est assez facile à retenir, 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 du bord.
2. Structures de données d'énumération
2.1 Liste de contiguïté. Eh bien, tout semble simple ici. Chaque sommet du graphe peut, en général, être associé à n'importe quelle structure d'énumération (liste, vecteur, tableau, ...), qui stockera les numéros de tous les sommets adjacents à celui donné. Pour les graphes orientés, nous ajouterons à une telle liste uniquement les sommets vers lesquels il y a une arête « dirigée » à partir d'un sommet caractéristique. Pour les graphiques pondérés, la mise en œuvre sera plus complexe.
2.2 Liste des côtes. Une structure de données assez populaire. La liste des arêtes, comme nous le dit Captain Obviousness, est en fait une liste d'arêtes du graphe, dont chacune est spécifiée par le sommet de départ, le sommet de fin (pour les graphes non orientés, l'ordre n'est pas important ici, bien que pour l'unification vous pouvez utilisez diverses règles, par exemple, spécifiant les sommets par ordre croissant) et le poids (pour les graphiques pondérés uniquement).
Vous pouvez consulter les listes matricielles répertoriées ci-dessus plus en détail (et avec des illustrations), par exemple : .
2.3 Tableau de contiguïté. Ce n'est pas la structure la plus courante. À la base, il s’agit d’une forme de « regroupement » de listes de contiguïté dans une seule structure d’énumération (tableau, vecteur). Les n premiers éléments (selon le nombre de sommets du graphe) d'un tel tableau contiennent les indices de départ du même tableau, à partir desquels tous les sommets adjacents à celui donné sont écrits dans une rangée.
Ici, j'ai trouvé l'explication la plus compréhensible (pour moi):
3. Vecteur de contiguïté et tableau de contiguïté associative
Il s'est avéré que l'auteur de ces lignes, n'étant pas un programmeur professionnel, mais qui s'occupait périodiquement de graphiques, traitait le plus souvent de listes d'arêtes. En effet, cela est pratique si le graphique comporte plusieurs boucles et arêtes. Ainsi, dans le développement des listes classiques d'arêtes, je propose de prêter attention à leur « développement/branche/modification/mutation », à savoir : le vecteur d'adjacence et le tableau d'adjacence associatif.
3.1 Vecteur de contiguïté
Cas (a1) : graphique non pondéré
Nous appellerons un 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 est a[2i], a[2i+1 ] spécifie une arête de graphe entre les sommets a[2i] et a[2i+1], respectivement.
Ce format d'enregistrement ne contient pas d'informations indiquant si le graphique est orienté (les deux options sont possibles). Lors de l'utilisation du format digraphique, l'arête est considérée comme étant dirigée de a[2i] vers a[2i+1]. Ici et ci-dessous : pour les graphiques non orientés, si nécessaire, des exigences concernant l'ordre d'enregistrement des sommets peuvent être appliquées (par exemple, que le sommet avec la valeur la plus faible du nombre qui lui est attribué vienne en premier).
En C++, il est conseillé de spécifier un vecteur d'adjacence à l'aide de std::vector, d'où le nom de cette structure de données.
Cas (a2) : graphique non pondéré, les poids des bords sont entiers
Par analogie avec le cas (a1), nous appelons le vecteur de contiguïté 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é c 0), où chaque « triplet » de nombres a[3i], a[3i+1], a[3i+2] spécifie une arête du graphe entre les sommets numérotés a[3i] et a[3i+1], respectivement, et la valeur a [3i+2] est le poids de cette arête. Un tel graphe peut également être orienté ou non.
Cas (b) : graphique non pondéré, poids de bord non entiers
Puisqu'il est impossible de stocker des éléments hétérogènes dans un seul tableau (vecteur), par exemple, l'implémentation suivante est possible. Le graphique est stocké dans une paire de vecteurs, dans lesquels le premier vecteur est le vecteur de contiguïté du graphique sans spécifier les poids, et le deuxième vecteur contient les poids correspondants (implémentation possible pour C++ : std::pair ). 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, l’auteur de ces lignes l’a trouvé très utile pour résoudre un certain nombre de problèmes. Eh bien, d'un point de vue formel, il y aura les avantages suivants :
- Le vecteur de contiguïté, comme toute autre structure « énumérative », est assez compact, occupe moins de mémoire que la matrice de contiguïté (pour les graphes clairsemés) et est relativement facile à mettre en œuvre.
- En principe, les sommets du graphique peuvent également être marqués par des nombres négatifs. Et si une telle « perversion » était nécessaire ?
- Les graphiques peuvent contenir plusieurs arêtes et plusieurs boucles, avec des poids différents (positifs, négatifs, voire nuls). Il n'y a aucune restriction ici.
- Vous pouvez également attribuer différentes propriétés aux arêtes - mais pour en savoir plus, voir la section 4.
Il faut cependant admettre que cette « liste » n'implique pas un accès rapide au bord. Et ici, le tableau de contiguïté associative vient à la rescousse, dont il est question ci-dessous.
3.2 Tableau de contiguïté associative
Ainsi, si l'accès à un bord spécifique, son poids et d'autres propriétés est critique pour nous et que les besoins en mémoire ne nous permettent pas d'utiliser la matrice de contiguïté, réfléchissons à la manière dont nous pouvons modifier le vecteur de contiguïté pour résoudre ce problème. Ainsi, la clé est une arête du graphique, qui peut être spécifiée comme une paire ordonnée d’entiers. A quoi ça ressemble ? N'est-ce pas une clé dans un tableau associatif ? Et si oui, pourquoi ne pas le mettre en œuvre ? Disons un 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 de l'arête. En C++, il est conseillé d'implémenter cette structure basée sur le conteneur std::map (std::map , int> ou std::map , double>), ou std::multimap si plusieurs arêtes sont attendues. Eh bien, 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 n'a même pas d'exigences strictes concernant 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 pleines, mais il manque quelque chose
Et c’est vrai : lors de la résolution d’un certain nombre de problèmes, nous devrons peut-être attribuer certaines caractéristiques aux bords du graphique et, par conséquent, les stocker. S'il est possible de réduire sans ambiguïté ces caractéristiques à des nombres entiers, alors 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.
Disons donc un graphe non pondéré, pour chaque arête dont il faut stocker, par exemple, 2 caractéristiques supplémentaires spécifiées par des entiers. Dans ce cas, il est possible de définir 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ù a[2i+2] et a[2i+3] détermineront les caractéristiques du bord correspondant. Pour un graphe avec poids entiers des arêtes, l'ordre est généralement similaire (la seule différence sera que les attributs suivront le poids de l'arête et seront spécifiés par les éléments a[2i+3] et a[2i+4] , et le bord lui-même sera spécifié non pas 4, mais 5 nombres ordonnés). Et pour un graphique avec des poids de bord non entiers, les caractéristiques peuvent être écrites dans son composant non pondéré.
Lors de l'utilisation d'un tableau de contiguïté associatif pour des graphiques avec des poids de bord entiers, il est possible de spécifier comme valeur non pas un seul nombre, mais un tableau (vecteur) de nombres qui spécifient, en plus du poids d'un bord, tous ses autres éléments nécessaires. caractéristiques. Dans le même temps, un inconvénient dans le cas de poids non entiers sera la nécessité de spécifier un signe avec un nombre à virgule flottante (oui, c'est un inconvénient, mais s'il n'y a pas autant de signes de ce type, et si vous ne le faites pas ne les mettez pas trop « délicats » en double, alors ce n'est peut-être rien) . Cela signifie qu'en C++, les tableaux de contiguïté associative étendue peuvent être définis comme suit : std::map , std :: vector> ou std :: map , std::vector, dans lequel la première valeur du « vecteur clé-valeur » sera le poids du bord, puis se trouvent les désignations numériques de ses caractéristiques.
Littérature
À propos des graphiques et des algorithmes en général :
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithmes : construction et analyse, 2e édition : Trans. de l'anglais – M. : Maison d’édition Williams, 2011.
2. Harari Frank. La théorie des graphes. M. : Mir, 1973.
Le rapport de l'auteur sur ces mêmes tableaux vectoriels et associatifs de contiguïtés :
3. Tchernoukhov S.A. Vecteur de contiguïté et tableau de contiguïté associatif comme moyens de représenter et de stocker des graphiques / SA Chernouhov. Vecteur de contiguïté et carte de contiguïté comme structures de données pour représenter un graphique // Recueil d'articles de la Conférence scientifique et pratique internationale « Problèmes de mise en œuvre des résultats des développements innovants et moyens de les résoudre » (Saratov, 14.09.2019 septembre 2019). – Sterlitamak : AMI, 65, p. 69-XNUMX
Sources en ligne utiles sur le sujet :
4.
5.
Source: habr.com