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.
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.
UN boucle dans un graphe est une arête qui part d'un nœud et se termine au même nœud. Par conséquent, un auto-boucle est une boucle sur un seul nœud de graphe, comme on le voit dans un pseudo graphe.
Algorithmes de parcours de graphes
Étant un type de structure de données non linéaire, parcourir un graphe est assez délicat. Traverser un graphe signifie parcourir et explorer chaque nœud étant donné qu'il existe un chemin valide à travers les arêtes. Les algorithmes de parcours de graphe sont principalement de deux types.
- Recherche en largeur d'abord (BFS): La recherche en largeur d'abord est un algorithme de parcours de graphe qui visite un nœud de graphe et explore ses voisins avant de passer à l'un de ses nœuds enfants. Bien que vous puissiez commencer à parcourir un graphique à partir de n'importe quel nœud sélectionné, le Noeud principal est généralement le point de départ préféré.
- Recherche en profondeur d'abord (DFS): Il s'agit du deuxième algorithme majeur de parcours de graphe. Il visite un nœud de graphe et explore ses nœuds enfants ou ses branches avant de passer au nœud suivant, c'est-à-dire en allant d'abord en profondeur avant d'aller en large.
La recherche en largeur d'abord est l'algorithme recommandé pour trouver le plus rapidement possible des chemins entre deux nœuds, en particulier le chemin le plus court.
La recherche en profondeur d'abord est principalement recommandée lorsque vous souhaitez visiter chaque nœud du graphique. Les deux algorithmes de traversée fonctionnent bien dans tous les cas, mais l'un peut être plus simple et plus optimisé que l'autre dans des scénarios sélectionnés.
Une illustration simple peut aider à mieux comprendre les deux algorithmes. Considérez les états d'un pays comme un graphique et essayez de vérifier si deux états, X et Oui, est connecté. Une recherche en profondeur pourrait faire presque le tour du pays sans se rendre compte assez tôt que Oui est à seulement 2 états de X.
L'avantage d'une recherche en largeur d'abord est qu'elle maintient autant que possible la proximité avec le nœud actuel avant de passer au suivant. Il trouvera le lien entre X et Oui en peu de temps sans avoir à explorer tout le pays.
Une autre différence majeure entre ces deux algorithmes réside dans la manière dont ils sont implémentés dans le code. La recherche en largeur est un algorithme itératif et fait usage d'un file d'attente, tandis qu'une recherche en profondeur est généralement mise en œuvre en tant que algorithme récursif qui exploite la empiler.
Vous trouverez ci-dessous un pseudocode démontrant l'implémentation des deux algorithmes.
Recherche étendue d'abord
bfs (Graph G, racine GraphNode) {
laisser q être Nouveau File d'attente// marque la racine comme visitée
root.visited = vrai// ajoute la racine à la file d'attente
q.en file d'attente(racine)
tandis que (q n'est pas vide) {
laisser actuel soit q.dequeue() // supprimer l'élément avant dans la file d'attente
pour (voisins n du courant dans G) {
si (n estne pas encore visité) {
// ajouter à la file d'attente - pour que vous puissiez également explorer ses voisins
q.en file d'attente(n)
n.visited = vrai
}
}
}
}
Recherche en profondeur d'abord
dfs (Graph G, racine GraphNode) {
// cas de base
si (la racine est nul) revenir// marque la racine comme visitée
root.visited = vrai
pour (voisins n de racine dans G)
si (n estne pas encore visité)
dfs (G, n) // appel récursif
}
Quelques autres algorithmes de parcours de graphes dérivent de recherches en largeur d'abord et en profondeur d'abord. Les plus populaires sont :
- Recherche bidirectionnelle : Cet algorithme est une manière optimisée de trouver le chemin le plus court entre deux nœuds. Il utilise deux recherches en largeur qui entrent en collision s'il existe un chemin.
- Tri topologique : Ceci est utilisé dans graphes orientés pour trier les nœuds dans l'ordre souhaité. Vous ne pouvez pas appliquer un tri topologique à des graphes non orientés ou à des graphes avec des cycles.
- Algorithme de Dijkstra : C'est aussi un type de BFS. Il est également utilisé pour trouver le chemin le plus court entre deux nœuds dans un graphe orienté pondéré, qui peut avoir des cycles ou non.
Questions d'entrevue courantes basées sur des graphiques
Les graphiques sont parmi les éléments importants structures de données que tout programmeur devrait connaître. Des questions reviennent souvent sur ce sujet dans les entretiens techniques, et vous pouvez rencontrer quelques problèmes classiques liés au sujet. Ceux-ci incluent des choses comme les problèmes du "juge de la ville", du "nombre d'îles" et du "voyageur de commerce".
Ce ne sont là que quelques-uns des nombreux problèmes d'entretien basés sur des graphiques populaires. Vous pouvez les essayer sur LeetCode, HackerRank, ou GeekspourGeeks.
Comprendre les structures de données de graphe et les algorithmes
Les graphiques ne sont pas seulement utiles pour les entretiens techniques. Ils ont également des cas d'utilisation réels, comme dans réseaux, cartes, et systèmes aériens pour trouver des itinéraires. Ils sont également utilisés dans la logique sous-jacente des systèmes informatiques.
Les graphiques sont excellents pour organiser les données et nous aider à visualiser des problèmes complexes. Cependant, les graphiques ne doivent être utilisés qu'en cas d'absolue nécessité, afin d'éviter la complexité de l'espace ou les problèmes de mémoire.
