graph implementation c using adjacency list
Ce didacticiel explique l'implémentation des graphiques en C ++. Vous découvrirez également différents types, représentations et applications de graphiques:
Un graphique est une structure de données non linéaire. Un graphe peut être défini comme une collection de nœuds qui sont également appelés «sommets» et «arêtes» qui relient deux sommets ou plus.
Un graphe peut également être vu comme un arbre cyclique où les sommets n'ont pas de relation parent-enfant mais maintiennent une relation complexe entre eux.
que fait le c ++
=> Cliquez ici pour la série de formations Absolute C ++.
Ce que vous apprendrez:
Qu'est-ce qu'un graphique en C ++?
Comme indiqué ci-dessus, un graphe en C ++ est une structure de données non linéaire définie comme une collection de sommets et d'arêtes.
Voici un exemple de structure de données de graphique.
Ci-dessus, un exemple de graphe G.Le graphe G est un ensemble de sommets {A, B, C, D, E} et un ensemble d'arêtes {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.
Types de graphiques - Graphiques dirigés et non dirigés
Un graphe dans lequel les arêtes n'ont pas de directions est appelé le graphe non orienté. Le graphique ci-dessus est un graphique non orienté.
Un graphe dans lequel les arêtes ont des directions qui leur sont associées est appelé un graphe orienté.
Ci-dessous est un exemple de graphe orienté.
Dans le graphe dirigé illustré ci-dessus, les arêtes forment une paire ordonnée dans laquelle chaque arête représente un chemin spécifique d'un sommet à un autre sommet. Le sommet à partir duquel le chemin commence est appelé ' Nœud initial 'Tandis que le sommet dans lequel se termine le chemin est appelé le' Nœud terminal ».
Ainsi dans le graphique ci-dessus, l'ensemble des sommets est {A, B, C, D, E} et l'ensemble des arêtes est {(A, B), (A, D), (B, C), (B, E ), (D, E) (E, C)}.
Nous discuterons de la terminologie du graphe ou des termes courants utilisés en relation avec le graphe ci-dessous.
Terminologie des graphes
- Sommet: Chaque nœud du graphe est appelé un sommet. Dans le graphique ci-dessus, A, B, C et D sont les sommets du graphique.
- Bord: Le lien ou le chemin entre deux sommets est appelé une arête. Il relie deux ou plusieurs sommets. Les différents arêtes du graphique ci-dessus sont AB, BC, AD et DC.
- Nœud adjacent: Dans un graphique, si deux nœuds sont connectés par une arête, ils sont appelés nœuds adjacents ou voisins. Dans le graphique ci-dessus, les sommets A et B sont reliés par l'arête AB. Ainsi A et B sont des nœuds adjacents.
- Degré du nœud: Le nombre d'arêtes connectées à un nœud particulier est appelé le degré du nœud. Dans le graphique ci-dessus, le nœud A a un degré 2.
- Chemin: La séquence de nœuds que nous devons suivre lorsque nous devons voyager d'un sommet à un autre dans un graphe s'appelle le chemin. Dans notre exemple de graphe, si nous devons aller du nœud A au C, alors le chemin serait A-> B-> C.
- Chemin fermé: Si le nœud initial est le même qu'un nœud terminal, alors ce chemin est appelé chemin fermé.
- Chemin simple: Un chemin fermé dans lequel tous les autres nœuds sont distincts est appelé un chemin simple.
- Cycle: Un chemin dans lequel il n'y a pas d'arêtes ou de sommets répétés et les premier et dernier sommets sont identiques est appelé un cycle. Dans le graphique ci-dessus, A-> B-> C-> D-> A est un cycle.
- Graphique connecté: Un graphe connecté est celui dans lequel il y a un chemin entre chacun des sommets. Cela signifie qu'il n'y a pas un seul sommet isolé ou sans arête de connexion. Le graphique ci-dessus est un graphique connecté.
- Graphique complet: Un graphique dans lequel chaque nœud est connecté à un autre est appelé le graphique complet. Si N est le nombre total de nœuds dans un graphe, alors le graphe complet contient N (N-1) / 2 nombre d'arêtes.
- Graphique pondéré: Une valeur positive attribuée à chaque arête indiquant sa longueur (distance entre les sommets reliés par une arête) est appelée poids. Le graphe contenant des arêtes pondérées est appelé un graphe pondéré. Le poids d'un bord e est noté w (e) et il indique le coût de la traversée d'un bord.
- Diagraph: Un digraphe est un graphe dans lequel chaque arête est associée à une direction spécifique et le parcours ne peut être effectué que dans la direction spécifiée.
Représentation graphique
La manière dont la structure des données du graphique est stockée en mémoire est appelée «représentation». Le graphique peut être stocké sous forme de représentation séquentielle ou de représentation liée.
Ces deux types sont décrits ci-dessous.
Représentation séquentielle
Dans la représentation séquentielle des graphes, nous utilisons la matrice de contiguïté. Une matrice de contiguïté est une matrice de taille n x n où n est le nombre de sommets du graphe.
Les lignes et colonnes de la matrice de contiguïté représentent les sommets d'un graphe. L'élément de matrice est mis à 1 lorsqu'il y a une arête présente entre les sommets. Si l'arête n'est pas présente, l'élément est mis à 0.
Ci-dessous est un exemple de graphique qui montre sa matrice de contiguïté.
Nous avons vu la matrice de contiguïté pour le graphique ci-dessus. Notez que puisqu'il s'agit d'un graphe non orienté, on peut dire que l'arête est présente dans les deux sens. Par exemple, comme l'arête AB est présente, nous pouvons conclure que l'arête BA est également présente.
Dans la matrice de contiguïté, nous pouvons voir les interactions des sommets qui sont des éléments de la matrice mis à 1 chaque fois que l'arête est présente et à 0 lorsque l'arête est absente.
Voyons maintenant la matrice de contiguïté d'un graphe orienté.
Comme indiqué ci-dessus, l'élément d'intersection dans la matrice de contiguïté sera 1 si et seulement s'il y a une arête dirigée d'un sommet à l'autre.
Dans le graphique ci-dessus, nous avons deux arêtes du sommet A. Une arête se termine par le sommet B tandis que la seconde se termine par le sommet C. Ainsi, dans la matrice d'adjacence, l'intersection de A et B est définie sur 1 comme l'intersection de A et C.
Ensuite, nous verrons la représentation séquentielle du graphique pondéré.
Vous trouverez ci-dessous le graphique pondéré et sa matrice de contiguïté correspondante.
Nous pouvons voir que la représentation séquentielle d'un graphe pondéré est différente des autres types de graphes. Ici, les valeurs non nulles dans la matrice de contiguïté sont remplacées par le poids réel du bord.
Le bord AB a un poids = 4, donc dans la matrice de contiguïté, nous fixons l'intersection de A et B à 4. De même, toutes les autres valeurs non nulles sont changées en leurs poids respectifs.
La liste de contiguïté est plus facile à mettre en œuvre et à suivre. La traversée c'est-à-dire pour vérifier s'il y a une arête d'un sommet à un autre prend du temps O (1) et la suppression d'une arête prend également O (1).
Que le graphique soit clairsemé (moins d'arêtes) ou dense, il prend toujours plus d'espace.
Représentation liée
Nous utilisons la liste de contiguïté pour la représentation liée du graphe. La représentation de liste de contiguïté maintient chaque nœud du graphe et un lien vers les nœuds qui sont adjacents à ce nœud. Lorsque nous traversons tous les nœuds adjacents, nous définissons le pointeur suivant sur null à la fin de la liste.
Considérons d'abord un graphe non orienté et sa liste de contiguïté.
Comme indiqué ci-dessus, nous avons une liste chaînée (liste de contiguïté) pour chaque nœud. Du sommet A, nous avons des arêtes vers les sommets B, C et D. Ainsi, ces nœuds sont liés au nœud A dans la liste de contiguïté correspondante.
Ensuite, nous construisons une liste de contiguïté pour le graphe orienté.
Dans le graphe dirigé ci-dessus, nous voyons qu'il n'y a pas d'arêtes provenant du sommet E. Par conséquent, la liste de contiguïté pour le sommet E est vide.
Construisons maintenant la liste de contiguïté pour le graphe pondéré.
Pour un graphique pondéré, nous ajoutons un champ supplémentaire dans le noeud de la liste de contiguïté pour indiquer le poids du bord comme indiqué ci-dessus.
faire une copie du tableau java
L'ajout d'un sommet dans la liste de contiguïté est plus facile. Cela permet également d'économiser de l'espace grâce à l'implémentation de la liste chaînée. Quand on a besoin de savoir s'il y a une arête entre un sommet à un autre, l'opération n'est pas efficace.
Opérations de base pour les graphiques
Voici les opérations de base que nous pouvons effectuer sur la structure de données du graphique:
- Ajoutez un sommet: Ajoute un sommet au graphique.
- Ajoutez un bord: Ajoute une arête entre les deux sommets d'un graphique.
- Affichez les sommets du graphe: Affichez les sommets d'un graphe.
Implémentation de graphes C ++ à l'aide de la liste d'adjacence
Nous présentons maintenant une implémentation C ++ pour illustrer un graphique simple en utilisant la liste de contiguïté.
Ici, nous allons afficher la liste de contiguïté pour un graphe orienté pondéré. Nous avons utilisé deux structures pour contenir la liste de contiguïté et les arêtes du graphe. La liste de contiguïté s'affiche sous la forme (start_vertex, end_vertex, weight).
Le programme C ++ est le suivant:
#include using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode* next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode* getAdjListNode(int value, int weight, adjNode* head) { adjNode* newNode = new adjNode; newNode->val = value; newNode->cost = weight; newNode->next = head; // point new node to current head return newNode; } int N; // number of nodes in the graph public: adjNode **head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges(), int n, int N) { // allocate new node head = new adjNode*(N)(); this->N = N; // initialize head pointer for all vertices for (int i = 0; i Production:
Production:
Liste de contiguïté graphique
(start_vertex, end_vertex, poids):
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
Applications des graphiques
Laissez-nous discuter de certaines des applications des graphiques.
- Les graphiques sont largement utilisés en informatique pour représenter des graphiques de réseau, ou des graphiques sémantiques ou même pour représenter le flux de calcul.
- Les graphiques sont largement utilisés dans les compilateurs pour décrire l'allocation des ressources aux processus ou pour indiquer l'analyse des flux de données, etc.
- Les graphiques sont également utilisés pour l'optimisation des requêtes dans les langages de base de données dans certains compilateurs spécialisés.
- Dans les sites de réseaux sociaux, les graphiques sont les principales structures permettant de représenter le réseau de personnes.
- Les graphiques sont largement utilisés pour construire le système de transport, en particulier le réseau routier. Un exemple populaire est Google Maps, qui utilise largement des graphiques pour indiquer les directions dans le monde entier.
Conclusion
Un graphique est une structure de données populaire et largement utilisée qui a de nombreuses applications dans le domaine de l'informatique lui-même en dehors d'autres domaines. Les graphes sont constitués de sommets et d'arêtes reliant deux ou plusieurs sommets.
Un graphique peut être dirigé ou non. Nous pouvons représenter des graphiques en utilisant une matrice de contiguïté qui est une représentation linéaire ainsi qu'en utilisant une liste chaînée de contiguïté. Nous avons également discuté de l'implémentation du graphe dans ce tutoriel.
=> Voir ici pour explorer la liste complète des didacticiels C ++.
lecture recommandée
- Didacticiel Python Advanced List (tri de liste, inverse, index, copie, jointure, somme)
- Liste Python - Créer, accéder, découper, ajouter ou supprimer des éléments
- Liste d'adresses IP de routeur par défaut pour les marques de routeurs sans fil courantes
- 12 meilleurs outils de création de graphiques linéaires pour créer de superbes graphiques linéaires (2021 RANKINGS)
- Mot de passe de connexion de routeur par défaut pour les principaux modèles de routeur (liste 2021)
- Structure de données de liste liée en C ++ avec illustration
- Structure de données de liste liée circulaire en C ++ avec illustration
- Structure de données de liste doublement liée en C ++ avec illustration
