Types de graphiques dans la structure de données et les applications

Introduction

Un graphe est une structure non linéaire composée de nœuds et d'arêtes. Il peut inclure un ensemble fini ou infini de nœuds maintenus par une arête reliant une paire de nœuds. Les structures de données sont une partie essentielle de tout concept de codage ; ainsi, avoir une bonne compréhension des différents types de graphiques dans les structures de données peut vous aider à résoudre des problèmes complexes du monde réel.

Dans le monde d'aujourd'hui, les données, c'est le pouvoir. Ainsi, l'organisation efficace des données pour un accès facile est essentielle pour tout programmeur. La connaissance des structures de données et de sa variété de graphiques renforce vos compétences en codage pour cibler les problèmes du monde réel et fournir efficacement ses solutions.

Apprenez la science des données pour prendre l'avantage sur vos concurrents

Examinons différents types de graphiques couramment utilisés dans les structures de données et comment ils sont appliqués dans la vie réelle.

Types de graphiques dans les structures de données

Une structure de données est une norme de stockage de données pratique pour tous les langages, tels que la structure de données de graphe python ou la structure de données de graphe java. La maîtrise de tous les types de graphes devrait être une priorité pour quiconque aspire à étudier les structures de données. Puisque la théorie des graphes a de nombreuses applications réelles, elles deviennent vitales dans les structures de données.

Les différents types de graphes dans les Structures de données peuvent être listés ci-dessous :

1. Graphique nul

Comme son nom l'indique, le graphe nul est vide ; en d'autres termes, c'est un graphe sans arêtes. Il se compose uniquement de sommets isolés dans le graphe avec un ensemble d'arêtes vacant.

2. Graphe fini

Si le nombre d'arêtes et de nœuds consiste en un nombre fini dans un graphe, alors le graphe est appelé graphe fini.

3. Graphique infini

Si l'on ne peut pas mettre un nombre fini au nombre de nœuds et au nombre d'arêtes dans un graphe, le graphe est connu comme un graphe infini. Les graphes infinis sont indénombrables, ce qui signifie que vous ne pouvez pas compter le nombre de nœuds ou d'arêtes dans ce type de graphe.

4. Graphique simple

Un graphe est dit simple lorsqu'il n'y a qu'une seule arête entre une paire de sommets. Ainsi, deux nœuds sont reliés par une arête dans un graphe, ce qui permet d'identifier une relation définie entre eux.

5. Multi-graphique

Si une paire de nœuds est connectée à plusieurs arêtes dans un graphe, alors le graphe est appelé multi-graphe. Un multi-graphe n'est pas composé d'auto-boucles. Il existe deux types d'arêtes qui peuvent exister dans un multi-graphe. Elles sont:

• Bords parallèles

Les bords parallèles, comme deux routes parallèles allant d'une source à la même destination, sont appelés bords parallèles.

• Boucle

Il s'agit d'une arête dont les sommets source et destination sont identiques.

Consultez nos programmes US - Data Science

6. Graphe orienté

Un graphe est dit orienté si toutes les arêtes présentes entre deux nœuds ou sommets ont une direction définie. Un graphe orienté est également appelé digraphe. Nous pouvons déterminer le nœud de départ et de fin en regardant un graphe orienté. Rappelez-vous que toutes les arêtes d'un graphe orienté doivent être dirigées pour être appelées un graphe orienté.

7. Graphe non orienté

Un graphe est dit non orienté s'il est difficile d'identifier le nœud de départ et d'arrivée en regardant ses arêtes. Tout comme un graphe orienté, les arêtes doivent être non orientées pour qu'il soit appelé un graphe non orienté.

8. Graphique connecté

Un graphe connexe est un graphe où au moins un chemin existe entre tous les nœuds. En termes plus simples, si vous partez d'un nœud dans un graphe connexe, vous devriez pouvoir visiter chaque nœud présent dans le graphe. Par conséquent, il devrait y avoir au moins un chemin pour chaque nœud.

9. Graphique déconnecté

Dans ce type de graphe, aucune arête n'existe entre une paire de nœuds ou de sommets. Ainsi, contrairement aux graphes connectés, atteindre tous les nœuds à partir de n'importe quel sommet n'est pas possible. Si une paire de sommets n'a pas de chemin entre eux, on parle de graphe déconnecté.

10. Graphique complet

Un graphe n'est considéré comme complet que lorsqu'une arête existe entre chaque nœud, ce qui signifie qu'une arête reliera tous les sommets du graphe. Un graphe complet sur n sommets est noté Kn , et le nombre d'arêtes dans le graphe est nC2 .

11. Graphique cyclique

Un graphe doit avoir au moins une composante cyclique pour être considéré comme un graphe cyclique. Au contraire, si le graphe ne contient aucun cycle, il est considéré comme un graphe acyclique.

12. Graphique régulier

Dans un graphe régulier, tous les sommets doivent avoir le même degré. Le degré d'un nœud peut être défini comme le nombre de nœuds qui lui sont connectés. Ainsi, dans un graphe régulier, tous les nœuds doivent être connectés au même nombre de nœuds.

13. Graphique bipartite

Pour qu'un graphe soit bipartite, il doit satisfaire les critères suivants.

• Le graphe doit être divisé en ensembles de sommets.
• Les bords ne doivent se former qu'entre un groupe de nœuds de l'autre côté. Cette règle empêche la connexion entre deux sommets d'un même ensemble de nœuds.
• Les deux groupes ne doivent pas avoir de sommets communs entre eux.

Un graphe suivant toutes les règles ci-dessus doit être considéré comme un graphe biparti.

14. Graphique étiqueté

Les arêtes des graphiques peuvent être pondérées. Un poids associé à un bord peut être compris comme le coût de déplacement à travers ce bord. Ces valeurs peuvent être basées sur un paramètre fixe et peuvent changer entre les graphiques. Maintenant, si toutes les arêtes ont un poids qui leur est associé, alors ce graphe peut être appelé un graphe étiqueté.

15. Graphe acyclique dirigé

Un graphe acyclique dirigé est une combinaison de graphes dirigés et acycliques où les arêtes dirigées du graphe ne font aucune forme de cycle. Au contraire, un graphe cyclique orienté est un graphe avec des arêtes orientées qui forme un cycle.

Application du graphe dans la structure de données

L'application la plus importante d'un graphe en informatique est la représentation du flux de calcul. Quelques autres cas célèbres de graphes utilisés sont :

1. Google Maps

Dans Google Maps, les structures de données graphiques définissent et calculent le système de transport. Lorsqu'une route rencontre une autre route et forme un croisement, elle est considérée comme un nœud et la route entre deux de ces nœuds est traitée comme un tronçon. Par conséquent, Google Maps vous trouve le chemin le plus court et le plus rapide vers votre destination en utilisant la structure de données du graphique.

2.Facebook

Facebook utilise des graphiques non orientés pour identifier un utilisateur et ses amis. Chaque utilisateur est traité comme les sommets et les connexions qui les rejoignent en tant qu'amis sont les bords du réseau. Avec des algorithmes basés sur la structure des données graphiques, Facebook suggère des "personnes que vous connaissez peut-être" et affiche des "amis communs".

3. Web mondial

Le World Wide Web est un exemple de graphe orienté. C'est aussi l'idée de base derrière le système de classement de Google. Dans le système World Wide Web, chaque site Web et application Web est traité comme un nœud ou des sommets, et les liens d'un site Web à un autre sont considérés comme la périphérie.

4. Système d'exploitation

Le système d'exploitation est un cas couramment utilisé de graphiques d'allocation de ressources qui utilise chaque processus et chaque ressource comme nœuds ou sommets. Les bords se produisent entre les ressources vers le processus alloué ou entre le processus demandeur et les ressources demandées. Parfois, ce cycle peut former une boucle infinie, initialisant le blocage.

5. Système de cartographie

Votre GPS est un cas de graphiques couramment utilisé pour localiser les restaurants, les magasins et les lieux à proximité que vous choisissez de rechercher à l'aide de cette technologie.

6.MicrosoftExcel

Les graphiques acycliques dirigés ou DAG sont utilisés dans Microsoft Excel.

7. L'algorithme de Dijkstra

L'algorithme de Dijkstra utilise une structure de données graphique pour identifier le chemin le plus court entre deux, ou dans certains cas, plus de deux nœuds.

8. Réseaux de vol :

Le calcul de réseaux de vol optimisés est une autre application réelle de la structure de données graphique. Si vous considérez les aéroports comme des nœuds et les routes comme des arêtes, les données correspondent parfaitement aux critères des graphes. C'est pourquoi, à l'aide de divers algorithmes améliorés, les meilleurs itinéraires entre deux aéroports ou nœuds sont déterminés.

Ce sont les diverses applications des graphes dans la structure des données , utilisées à travers le monde dans diverses applications et systèmes pour organiser et maintenir leur bon fonctionnement,

Commencez votre voyage en tant que data scientist

Si vous souhaitez devenir un scientifique des données et gérer les données avec tact à l'aide des différents graphiques que nous avons appris, consultez une vaste gamme de cours de science des données sur upGrad. L'un des cours les plus populaires est le cours PG-IIITB sur la science des données , un excellent cours pour les scientifiques de données en herbe et en herbe pour commencer !

Voici ce que propose le cours.

• Accompagnement professionnel à 360 degrés par des experts de l'industrie et des mentors
• Expérience pratique avec des projets industriels et des études de cas détaillées pour évaluer les progrès réguliers
• Mise en réseau avec des experts en science des données dans tous les secteurs, à l'échelle mondiale

Vous pouvez également consulter tous les autres cours upGrad sur Data Science .