Guide de la structure de données graphique

Un programmeur efficace doit avoir une solide compréhension des structures de données et des algorithmes. Les réunions techniques vérifieront certainement fréquemment vos capacités d'analyse ainsi que de réflexion importante.

Les graphes sont parmi les nombreuses structures de données cruciales dans les programmes. Dans de nombreux cas, la compréhension des graphes ainsi que la résolution des problèmes liés aux graphes ne sont pas simples.

Qu'est-ce qu'un graphique, et que devez-vous découvrir à son sujet ?

Qu'est-ce qu'un graphe ?

Un graphe est une structure de données non linéaire qui comporte des nœuds (ou sommets) avec des arêtes qui les relient. Tous les arbres sont des sous-types de graphes, mais tous les graphes ne sont pas des arbres, de même que le graphe est le cadre d'information d'où découlent les arbres.

Bien que vous puissiez construire des structures de données en JavaScript et aussi dans d'autres langages, vous pouvez réaliser un graphique de nombreuses façons. Les approches les plus privilégiées sont les listes d'arêtes , listes d'adjacence et aussi matrices d'adjacence .

Le siteGuide de la Khan Academy pour se présenter aux graphiquesest une source merveilleuse pour apprendre à savoir exactement comment représenter un graphique.

Il existe de nombreux types de graphiques différents. Une distinction commune se situe entre dirigé et également non dirigées graphiques ; ceux-ci reviennent souvent dans les difficultés de codage et les utilisations réelles.

Types de graphiques

  1. Graphique dirigé : Un graphe dans lequel toutes les arêtes ont une direction, décrit en outre comme suit . digraphe.
  2. Graphe non orienté : Un graphe non dirigé est également connu comme un graphe à deux voies. Dans les graphes non dirigés, les instructions des arêtes n'ont pas d'importance, de même que la traversée peut entrer dans n'importe quel type d'instructions.
  3. Graphe pondéré : Un graphe pondéré est un graphe dont les nœuds et aussi les arêtes ont effectivement une valeur connectée. Dans de nombreux cas, cette valeur représente la dépense de vérification de ce nœud ou de cette arête.
  4. Graphique fini : Un graphique qui a un nombre limité de nœuds et aussi de côtés.
  5. Graphique infini : Un graphique qui a une quantité illimitée de nœuds ainsi que de côtés.
  6. Graphe trivial : Un graphique qui n'a qu'un seul nœud et aussi aucun côté.
  7. Graphe simple : Lorsqu'une seule arête relie chaque ensemble de nœuds d'un graphique, on l'appelle un graphique simple.
  8. Graphe nul : Un graphique nul est un graphique qui n'a aucune arête reliant ses nœuds.
  9. Multigraphe : Dans un multigraphe, au moins un ensemble de nœuds a plus d'un côté qui les relie. Dans les multigraphes, il n'y a pas d'auto-boucles.
  10. Graphe complet : Un graphe complet est un graphe dans lequel chaque nœud s'attache à tous les autres nœuds du graphe. Il est en outre désigné comme un graphique complet .
  11. Pseudo-graphe : Un graphique qui possède une auto-boucle en plus de diverses autres arêtes du graphique est appelé un pseudo-graphique.
  12. Graphique régulier : Un graphe normal est un graphe où tous les nœuds ont des degrés égaux ; c'est-à-dire que chaque nœud a exactement la même variété de voisins.
  13. Graphique connecté : Un graphe connecté est simplement tout type de graphe dans lequel 2 nœuds quelconques se connectent ; c'est-à-dire un graphe avec au moins un parcours entre tous les 2 nœuds du graphe.
  14. Graphique déconnecté : Un graphique détaché est l'opposé direct d'un graphique lié. Dans un graphe détaché, il n'y a pas d'arêtes reliant les nœuds du graphe, comme dans un... null graphique.
  15. Graphe cyclique : Un graphique cyclique est un graphique ayant au moins un cycle de graphique (un chemin qui se termine là où il a commencé).
  16. Graphique acyclique : Un graphe acyclique est un graphe ne comportant aucun cycle. Il peut être soit dirigé, soit non dirigé.
  17. Sous-graphe : Un sous-graphe est un graphe obtenu. C'est un graphe développé à partir de nœuds et d'arêtes qui font partie d'un autre graphe.
Voir aussi :  SQL vs NoSQL : Quelle est la meilleure base de données pour votre prochain projet ?

A boucle dans un graphe est un côté qui commence par un nœud et se termine exactement au même nœud. Pour cette raison, une boucle d'auto est une boucle sur un seul nœud du graphe, comme on le voit dans un pseudo graphique.

Algorithmes de traversée de graphe

Étant une sorte de structure d'information non linéaire, parcourir un graphique est assez compliqué. Traverser un graphique signifie passer et vérifier chaque nœud offert il y a un cours valide avec les côtés. Les algorithmes de traversée de graphe sont généralement de 2 types .

  1. La recherche en largeur (BFS, Breadth- First Search) : La recherche en premier lieu est un algorithme de traversée de graphe qui vérifie un nœud du graphe ainsi que l'exploration de ses voisins avant de passer à l'un de ses nœuds enfants. Bien que vous puissiez commencer à parcourir un graphe à partir de n'importe quel nœud sélectionné, l'algorithme de recherche de type nœud racine est généralement le point de départ favorisé.
  2. Recherche en profondeur (DFS) : Il s'agit du deuxième algorithme significatif de traversée de graphique. Il voit un nœud de graphique et explore ses nœuds enfants ou ses branches avant de passer au nœud suivant - c'est-à-dire, aller en profondeur initiale avant d'aller en largeur.

Breadth- first search est la formule recommandée pour trouver des chemins entre 2 nœuds aussi rapidement que possible, en particulier le chemin le plus rapide.

Voir aussi :  Comment créer et concevoir un formulaire utilisateur VBA

Profondeur- la toute première recherche est principalement conseillée lorsque vous souhaitez aller à chaque nœud du graphique. Les deux algorithmes de traversée fonctionnent bien dans tous les cas, mais l'un pourrait être plus simple et plus performant que l'autre dans certains scénarios.

Une illustration de base peut aider à reconnaître beaucoup mieux les deux algorithmes. Considérez les états d'une nation comme un graphique et essayez d'inspecter si 2 états, X et aussi Y sont jointes. Une recherche en profondeur pourrait suivre un chemin qui fait presque le tour de la nation sans reconnaître suffisamment tôt que Y est simplement à 2 états de X .

L'avantage d'une recherche de type breadth-first est qu'elle conserve autant que possible la proximité du nœud existant avant de passer au suivant. Elle va certainement découvrir le lien entre X et aussi Y en peu de temps sans avoir à explorer tout le pays.

Une autre différence significative entre ces 2 formules reste dans la façon dont elles sont exécutées en code. La recherche en largeur d'abord est une formule itérative ainsi que l'utilisation d'une file d'attente tandis qu'une recherche en profondeur est généralement appliquée sous la forme d'une file d'attente algorithme récursif qui tire parti de la pile .

Voici un pseudocode démontrant l'application des deux algorithmes.

Première recherche en largeur

Première recherche en profondeur

Deux autres algorithmes de traversée de graphes sont issus de la recherche en largeur et de la recherche en profondeur. L'un des plus éminents sont :

  • La recherche bidirectionnelle : Cette formule est un moyen amélioré de découvrir le parcours le plus rapide entre 2 nœuds. Elle fait appel à deux recherches breadth-first qui s'affrontent s'il existe un parcours.
  • Type topologique : Cette formule est utilisée dans cartes orientées pour disposer les nœuds dans l'ordre préféré. Vous ne pouvez pas appliquer un type topologique aux graphes non dirigés ou aux graphiques avec des cycles.
  • L'algorithme de Dijkstra : Il s'agit en outre d'un type de BFS. Il est également utilisé pour trouver le parcours le plus rapide entre 2 nœuds dans un graphe non orienté. carte de routage pondérée , qui peut comporter des cycles ou non.

Questions d'entretien courantes basées sur les graphiques

Les graphes sont parmi les structures d'information cruciales que tout développeur doit reconnaître. Les préoccupations tournent souvent sur ce sujet dans les réunions techniques, et aussi vous pouvez rencontrer des problèmes intemporels liés à ce sujet. Ceux-ci consistent en des points comme le " tribunal de la ville ", le " nombre d'îles ", ainsi que les problèmes du " voyageur de commerce ".

Voir aussi :  Comment créer un serveur Web de base dans Go

Il s'agit simplement de quelques-uns des nombreux problèmes de réunion à base de graphiques les plus importants. Vous pouvez les essayer surLeetCode,HackerRankouGeeksforGeeks.

Comprendre les structures de données graphiques et aussi les algorithmes.

Les graphes ne sont pas seulement utiles pour les réunions techniques. Ils ont aussi des cas d'utilisation dans le monde réel, comme dans la section la mise en réseau, les cartes, et systèmes de transport aérien pour la localisation des chemins. Ils sont en outre utilisés dans le raisonnement sous-jacent des systèmes informatiques.

Les graphiques sont remarquables pour organiser les données ainsi que pour nous aider à envisager des problèmes complexes. Cependant, les graphiques ne doivent être utilisés que lorsque c'est absolument nécessaire, pour éviter les problèmes d'espace ou de mémoire.

Qu'est-ce que la structure de données graphique expliquer avec un exemple?

Un graphe est une structure de données commune constituée d'un ensemble fini de nœuds (ou sommets) et d'un ensemble d'arêtes les reliant. Une paire (x, y) est appelée arête, ce qui indique que le sommet x se connecte au sommet y. Dans les exemples ci-dessous, les cercles représentent les sommets, tandis que les lignes représentent les arêtes.

Qu'est-ce qu'un graphe dans une structure de données ?

Les graphes dans les structures de données sont des structures de données non linéaires constituées d'un nombre fini de nœuds ou de sommets et des arêtes qui les relient. Les graphes dans les structures de données sont utilisés pour résoudre les problèmes du monde réel dans lesquels ils représentent la zone problématique sous la forme d'un réseau comme les réseaux téléphoniques, les réseaux de circuits et les réseaux sociaux.

Comment créer un graphe de structure de données 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. Opérations de base pour les graphes

  • Ajouter un sommet : ajoute un sommet au graphe.
  • Ajouter une arête : ajoute une arête entre les deux sommets d'un graphe.
  • Afficher les sommets du graphe : Affichez les sommets d'un graphe.

Comment maîtriser un graphe en structure de données ?

Certains des meilleurs algorithmes de graphe sont mentionnés ci-dessous.

  • Implémentez la traversée en largeur d'abord.
  • Implémenter la traversée en profondeur d'abord.
  • Calculez le nombre de nœuds au niveau du graphique.
  • Trouver tous les chemins entre deux nœuds.
  • Trouver tous les composants connectés d'un graphique.
  • Algorithmes de Prim et de Kruskal.

Cliquez pour évaluer cet article !
[Total: Moyenne : ]

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.