Un guide de la structure de données de graphe

Un programmeur efficace a besoin d'une solide compréhension des structures de données et des algorithmes. Les entretiens techniques mettront souvent à l'épreuve vos capacités de résolution de problèmes et de pensée critique.

Les graphes sont l'une des nombreuses structures de données importantes en programmation. Dans la plupart des cas, comprendre les graphiques et résoudre des problèmes basés sur des graphiques n'est pas facile.

UTILISEZ LA VIDÉO DU JOUR

Qu'est-ce qu'un graphique et que devez-vous savoir à son sujet ?

Qu'est-ce qu'un graphique ?

Un graphe est une structure de données non linéaire qui a 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, et le graphe est la structure de données à l'origine des arbres.

Bien que vous puissiez construire des structures de données en JavaScript et d'autres langages, vous pouvez implémenter un graphe de différentes manières. Les approches les plus populaires sont listes d'arêtes , listes de contiguïté , et matrices d'adjacence .

La Guide de la Khan Academy pour représenter des graphiques est une excellente ressource pour apprendre à représenter un graphique.

Il existe de nombreux types de graphiques différents. Une distinction commune est entre dirigé et non dirigé graphiques ; ceux-ci reviennent souvent dans les défis de codage et les utilisations réelles.

Types de graphiques

Graphique dirigé: Un graphe dans lequel toutes les arêtes ont une direction, également appelée digraphe.
graphe non orienté : Un graphe non orienté est également appelé graphe bidirectionnel. Dans les graphes non orientés, la direction des arêtes n'a pas d'importance et la traversée peut aller dans n'importe quelle direction.
Graphique pondéré : Un graphe pondéré est un graphe dont les nœuds et les arêtes ont une valeur associée. Dans la plupart des cas, cette valeur représente le coût d'exploration de ce nœud ou de ce bord.
Graphe fini : Un graphe qui a un nombre fini de nœuds et d'arêtes.
Graphique infini : Un graphe qui a une quantité infinie de nœuds et d'arêtes.
Graphique trivial : Un graphe qui n'a qu'un seul nœud et aucune arête.
Graphique simplifié : Lorsqu'une seule arête relie chaque paire de nœuds d'un graphe, on parle de graphe simple.
Graphique nul : Un graphe nul est un graphe qui n'a pas d'arêtes reliant ses nœuds.
Multigraphe : Dans un multigraphe, au moins une paire de nœuds a plus d'une arête qui les relie. Dans les multigraphes, il n'y a pas d'auto-boucles.
Graphique complet : Un graphe complet est un graphe dans lequel chaque nœud se connecte à tous les autres nœuds du graphe. Il est également connu comme un graphique complet .
Pseudo graphe : Un graphe qui a une boucle automatique en dehors des autres arêtes du graphe est appelé un pseudo-graphe.
Graphique régulier : Un graphe régulier est un graphe où tous les nœuds ont des degrés égaux ; c'est-à-dire que chaque nœud a le même nombre de voisins.
Graphique connecté : Un graphe connexe est simplement n'importe quel graphe dans lequel deux nœuds se connectent; c'est-à-dire un graphe avec au moins un chemin entre tous les deux nœuds du graphe.
Graphique déconnecté : Un graphe déconnecté est l'opposé direct d'un graphe connexe. Dans un graphe déconnecté, il n'y a pas d'arêtes reliant les nœuds du graphe, comme dans un nul graphique.
Graphique cyclique : Un graphe cyclique est un graphe contenant au moins un cycle de graphe (un chemin qui se termine là où il a commencé).
Graphe acyclique : Un graphe acyclique est un graphe sans cycle du tout. Il peut être dirigé ou non dirigé.
Sous-graphe : Un sous-graphe est un graphe dérivé. C'est un graphe formé de nœuds et d'arêtes qui sont des sous-ensembles d'un autre graphe.