Liste de contiguïté et représentation matricielle du graphique

Même s'ils semblent différents, tous types de graphiques peut être représenté de la même manière. Il existe généralement deux types de représentation graphique :

1. Matrice d'adjacence
2. Liste de contiguïté

Liste de contiguïté

La liste de contiguïté se compose de listes liées. Chaque sommet est considéré comme un index de tableau et chaque élément représente une liste chaînée. Ces listes chaînées contiennent les sommets qui ont des arêtes avec le sommet d'index.

Voici un exemple de liste de contiguïté :

Disons qu'un graphe contient V nombre de sommets et E nombre d'arêtes.

Généralement, la complexité spatiale sera O(V + E).

Dans le pire des cas, la complexité spatiale sera O(V2) si le graphique donné est le graphique complet

Matrice d'adjacence

La matrice de contiguïté se compose d'un tableau 2D. Graphique ayant un nombre V de sommets, la taille de la matrice sera VxV.

Dire, matrix[i][j] = 5. Cela signifie qu'il y a une arête entre les nœuds i et j où le poids est de 5.

Regardons le graphique suivant et sa matrice d'adjacence :

Nous avons créé le tableau 2D en utilisant ces étapes :

Étape 1) Le sommet A a une arête directe avec B et le poids est de 5. Ainsi, la cellule de la ligne A et la colonne B seront remplies de 5. Le reste des cellules de la ligne A sera rempli de zéro.

Étape 2) Les sommets B ont une arête directe avec C et le poids est de 4. Ainsi, la cellule de la ligne B et de la colonne C sera remplie de 4. Les cellules restantes de la ligne B seront remplies de zéro car B n'a aucune arête sortante vers aucun. d'autres nœuds.

Étape 3) Les sommets C n'ont aucune arête directe avec d'autres sommets. Ainsi, la ligne C sera remplie de zéros.

Étape 4) Le sommet D a une arête dirigée avec A et C.

• Ici, la cellule de la ligne D et de la colonne A aura une valeur de 7. Les cellules de la ligne D et de la colonne C auront une valeur de 2.
• Le reste des cellules de la ligne D sera rempli de zéros.

Étape 5) Les sommets E ont une arête dirigée avec B et D. La cellule de la ligne E et de la colonne B aura une valeur de 6. Les cellules de la ligne E et de la colonne D auront une valeur de 3. Le reste des cellules de la ligne D sera rempli de zéros.

Voici quelques points à noter :

• Le graphique n'a pas d'auto-boucles lorsque la diagonale principale de la matrice de contiguïté est 0.
• Le Graphe est un graphe orienté si les index (a,b) et (b,a) n'ont pas la même valeur. Sinon, le Graphe est un graphe orienté.
• Le graphique sera un graphique pondéré si la valeur des cellules est supérieure à 1.

Il y a un problème avec la matrice de contiguïté car elle nécessite des espaces au carré. Ici, nous stockons les arêtes qui ne sont pas connectées. Ces bords allouent de l'espace dans la mémoire.

Par exemple, si nous avons un graphique avec 100 nœuds, alors 10 cellules sont nécessaires pour le stocker dans le RAM. Avec moins d'arêtes dans le graphe, l'allocation d'une mémoire aussi importante peut être un gaspillage. Ainsi, la complexité spatiale utilisant la matrice d'adjacence sera O(N2), où N signifie le nombre de nœuds dans le graphique.