Qu’est-ce que la structure des données graphiques ?

UN Graphique est une structure de données non linéaire composée de sommets et d'arêtes. Les sommets sont parfois également appelés nœuds et les arêtes sont des lignes ou des arcs qui relient deux nœuds quelconques du graphique. Plus formellement, un graphe est composé d'un ensemble de sommets ( DANS ) et un ensemble d'arêtes ( ET ). Le graphique est noté G(V,E) .

Représentations du graphique

Voici les deux manières les plus courantes de représenter un graphique :

1. Matrice de contiguïté
2. Liste de contiguïté

Matrice de contiguïté

Une matrice de contiguïté est une manière de représenter un graphique comme une matrice de booléens (0 et 1).

Supposons qu'il y ait n sommets dans le graphique Alors, créez une matrice 2D adjMat[n][n] ayant une dimension n x n.

liste comparable

• S'il y a une arête depuis le sommet je à j , marque adjMat[i][j] comme 1 .
• S'il n'y a pas d'arête depuis le sommet je à j , marque adjMat[i][j] comme 0 .

Représentation du graphique non orienté vers la matrice de contiguïté :

La figure ci-dessous montre un graphique non orienté. Initialement, la matrice entière est initialisée à 0 . S'il y a une arête de la source à la destination, nous insérons 1 dans les deux cas ( adjMat[destination] et adjMat [ destination]) parce que nous pouvons aller dans les deux sens.

chaîne inversée java

Graphique non orienté vers la matrice de contiguïté

Représentation du graphique dirigé vers la matrice de contiguïté :

La figure ci-dessous montre un graphique orienté. Initialement, la matrice entière est initialisée à 0 . S'il y a une arête de la source à la destination, nous insérons 1 pour ce particulier adjMat[destination] .

Graphique dirigé vers la matrice de contiguïté

Liste de contiguïté

Un tableau de listes est utilisé pour stocker les arêtes entre deux sommets. La taille du tableau est égale au nombre de sommets (c'est-à-dire n) . Chaque index de ce tableau représente un sommet spécifique du graphique. L'entrée à l'index i du tableau contient une liste chaînée contenant les sommets adjacents au sommet je .

Supposons qu'il y ait n sommets dans le graphique Alors, créez un tableau de liste de taille n comme adjListe[n].

• adjList[0] aura tous les nœuds connectés (voisin) au sommet 0 .
• adjList[1] aura tous les nœuds connectés (voisin) au sommet 1 et ainsi de suite.

Représentation du graphique non orienté vers la liste de contiguïté :

Le graphe non orienté ci-dessous a 3 sommets. Ainsi, un tableau de liste sera créé de taille 3, où chaque index représente les sommets. Désormais, le sommet 0 a deux voisins (c'est-à-dire 1 et 2). Alors, insérez les sommets 1 et 2 aux indices 0 du tableau. De même, pour le sommet 1, il a deux voisins (c'est-à-dire 2 et 0). Donc, insérez les sommets 2 et 0 aux indices 1 du tableau. De même, pour le sommet 2, insérez ses voisins dans le tableau de la liste.

Graphique non orienté vers la liste de contiguïté

énumérations Java

Représentation du graphique dirigé vers la liste de contiguïté :

Le graphe orienté ci-dessous a 3 sommets. Ainsi, un tableau de liste sera créé de taille 3, où chaque index représente les sommets. Or, le sommet 0 n’a plus de voisins. Pour le sommet 1, il a deux voisins (c'est-à-dire 0 et 2). Donc, insérez les sommets 0 et 2 aux indices 1 du tableau. De même, pour le sommet 2, insérez ses voisins dans le tableau de la liste.

Graphique dirigé vers la liste de contiguïté