Première recherche en profondeur: un guide de parcours de graphe DFS avec 6 exemples de Leetcode

Avez-vous déjà résolu un labyrinthe réel? L'approche que la plupart d'entre nous adoptent en résolvant un labyrinthe est de suivre un chemin jusqu'à ce que nous atteignions une impasse, puis de revenir en arrière et de revenir sur nos pas pour trouver un autre chemin possible.

C'est exactement l'analogie de Depth First Search (DFS). C'est un algorithme de traversée de graphe populaire qui commence au nœud racine et se déplace aussi loin que possible dans une branche donnée, puis revient en arrière jusqu'à ce qu'il trouve un autre chemin inexploré à explorer. Cette approche se poursuit jusqu'à ce que tous les nœuds du graphe aient été visités.

Dans le didacticiel d'aujourd'hui, nous allons découvrir un modèle DFS qui sera utilisé pour résoudre certaines des questions importantes sur les arbres et les graphiques pour votre prochain entretien Tech Giant! Nous allons résoudre certains problèmes de Leetcode moyen et dur en utilisant la même technique courante.

Alors, commençons, d'accord?

la mise en oeuvre

Étant donné que DFS a une nature récursive, il peut être implémenté à l'aide d'une pile.

Sort magique DFS:

  1. Pousser un nœud dans la pile
  2. Pop le nœud
  3. Récupérer les voisins non visités du nœud supprimé, les pousser à empiler
  4. Répétez les étapes 1, 2 et 3 tant que la pile n'est pas vide

Traversées graphiques

En général, il existe 3 traversées DFS de base pour les arbres binaires:

  1. Précommande: racine, gauche, droite OU racine, droite, gauche
  2. Commande de poste: gauche, droite, racine OU droite, gauche, racine
  3. Dans l'ordre: gauche, racine, droite OU droite, racine, gauche

144. Traversée des précommandes de l'arbre binaire (difficulté: moyenne)

Pour résoudre cette question, tout ce que nous devons faire est simplement de rappeler notre sort magique. Comprenons très bien la simulation car c'est le modèle de base que nous utiliserons pour résoudre le reste des problèmes.

Au début, nous poussons le nœud racine dans la pile. Tant que la pile n'est pas vide, nous la faisons sauter et poussons ses enfants droit et gauche dans la pile.

Lorsque nous faisons apparaître le nœud racine, nous le mettons immédiatement dans notre liste de résultats. Ainsi, le premier élément de la liste de résultats est la racine (d'où le nom, Pre-order).

L'élément suivant à sortir de la pile sera l'élément supérieur de la pile pour le moment: l'enfant gauche du nœud racine. Le processus se poursuit de la même manière jusqu'à ce que tout le graphe ait été parcouru et que toutes les valeurs de nœud de l'arbre binaire entrent dans la liste résultante.

145. Traversée post-ordre de l'arbre binaire (Difficulté: Difficile)

Le parcours de pré-commande est racine-gauche-droite , et le post-ordre est racine-droite-gauche . Cela signifie que le parcours post-ordre est exactement l'inverse du parcours pré-ordre.

Une solution qui pourrait venir à l'esprit en ce moment consiste simplement à inverser le tableau résultant de la traversée de pré-ordre. Mais pensez-y - cela coûterait O (n) temps de complexité pour l'inverser.

Une solution plus intelligente consiste à copier et coller le code exact du parcours de précommande, mais à placer le résultat en haut de la liste chaînée (index 0) à chaque itération. L'ajout d'un élément à la tête d'une liste chaînée prend un temps constant. Cool, non?

94. Traversée en ordre de l'arbre binaire (difficulté: moyenne)

Notre approche pour résoudre ce problème est similaire aux problèmes précédents. Mais ici, nous allons visiter tout ce qui se trouve sur le côté gauche d'un nœud, imprimer le nœud, puis visiter tout ce qui se trouve sur le côté droit du nœud.

323. Nombre de composants connectés dans un graphique non orienté

(Difficulté: moyenne)

Notre approche ici est de créer une variable appelée ans qui stocke le nombre de composants connectés.

Tout d'abord, nous initialiserons tous les sommets comme non visités. Nous partirons d'un nœud, et tout en effectuant DFS sur ce nœud (bien sûr, en utilisant notre sort magique), il marquera tous les nœuds connectés comme visités. La valeur de ans sera incrémentée de 1.

 import java.util.ArrayList; import java.util.List; import java.util.Stack; public class NumberOfConnectedComponents { public static void main(String[] args){ int[][] edge = {{0,1}, {1,2},{3,4}}; int n = 5; System.out.println(connectedcount(n, edge)); } public static int connectedcount(int n, int[][] edges) { boolean[] visited = new boolean[n]; List[] adj = new List[n]; for(int i=0; i

200. Number of Islands (Difficulty: Medium)

This falls under a general category of problems where we have to find the number of connected components, but the details are a bit tweaked.

Instinctually, you might think that once we find a “1” we initiate a new component. We do a DFS from that cell in all 4 directions (up, down, right, left) and reach all 1’s connected to that cell. All these 1's connected to each other belong to the same group, and thus, our value of count is incremented by 1. We mark these cells of 1's as visited and move on to count other connected components.

Original text


547. Friend Circles (Difficulty: Medium)

This also follows the same concept as finding the number of connected components. In this question, we have an NxN matrix but only N friends in total. Edges are directly given via the cells so we have to traverse a row to get the neighbors for a specific "friend".

Notice that here, we use the same stack pattern as our previous problems.

That's all for today! I hope this has helped you understand DFS better and that you have enjoyed the tutorial. Please recommend this post if you think it may be useful for someone else!