Ai rezolvat vreodată un labirint din viața reală? Abordarea pe care o fac cei mai mulți dintre noi în timp ce rezolvăm un labirint este aceea că urmăm o cale până când ajungem într-un punct mort, apoi ne retrogradăm și ne revenim la pași pentru a găsi o altă cale posibilă.

Aceasta este exact analogia Depth First Search (DFS). Este un algoritm popular de parcurgere a graficului care începe de la nodul rădăcină și se deplasează cât de mult poate în jos pe o ramură dată, apoi retrage până când găsește o altă cale neexplorată de explorat. Această abordare este continuată până când toate nodurile grafului au fost vizitate.

În tutorialul de astăzi, vom descoperi un model DFS care va fi folosit pentru a rezolva câteva dintre întrebările importante despre arborele și graficele pentru următorul dvs. interviu tehnic gigant! Vom rezolva unele probleme Leetcode medii și dure utilizând aceeași tehnică comună.

Deci, să începem, nu-i așa?

Implementare

Deoarece DFS are o natură recursivă, acesta poate fi implementat folosind o stivă.

Vrajă magică DFS:

  1. Împingeți un nod în stivă
  2. Apăsați nodul
  3. Recuperați vecinii nevizitați ai nodului eliminat, împingeți-i în stivă
  4. Repetați pașii 1, 2 și 3 atâta timp cât stiva nu este goală

Traversări grafice

În general, există 3 traversări de bază DFS pentru arborii binari:

  1. Pre-comanda: Rădăcină, stânga, dreapta SAU Rădăcină, dreapta, stânga
  2. Post Comanda: Stânga, Dreapta, Rădăcină SAU Dreapta, stânga, rădăcină
  3. În ordine: Stânga, Rădăcină, Dreapta SAU Dreapta, Rădăcină, Stânga

144. Transversal de precomandă a arborelui binar (dificultate: medie)

Pentru a rezolva această întrebare, tot ce trebuie să facem este să ne reamintim pur și simplu vraja magică. Să înțelegem foarte bine simularea, deoarece acesta este șablon de bază vom folosi pentru a rezolva restul problemelor.

Prima cautare in adancime un ghid de traversare a graficului

La început, împingem nodul rădăcină în stivă. În timp ce stiva nu este goală, o deschidem și îi împingem copilul din stânga și dreapta în stivă.

Pe măsură ce deschidem nodul rădăcină, îl punem imediat în lista noastră de rezultate. Astfel, primul element din lista de rezultate este rădăcina (de aici și numele, precomandă).

Următorul element care va fi scos din stivă va fi elementul de sus al stivei chiar acum: copilul stâng al nodului rădăcină. Procesul este continuat în mod similar până când întregul grafic a fost parcurs și toate valorile nodului arborelui binar intră în lista rezultată.

Prima cautare in adancime un ghid de traversare a graficului

145. Arborele binar postordinar transversal (dificultate: greu)

Pre-comandă traversare este rădăcină-stânga-dreapta, iar post-comandă este dreapta-stânga-rădăcină. Aceasta înseamnă că traversarea post-comandă este exact inversul parcursului de precomandă.

Deci, o soluție care ar putea veni în minte chiar acum este pur și simplu inversarea matricei rezultate de traversare precomandă. Dar gândiți-vă la asta – asta ar costa O (n) complexitate de timp pentru ao inversa.

O soluție mai inteligentă este să copiați și să inserați codul exact al traversării de precomandă, dar să puneți rezultatul în partea de sus a listei conectate (index 0) la fiecare iterație. Este nevoie de timp constant pentru a adăuga un element în capul unei liste legate. Super, nu?

1612126809 59 Prima cautare in adancime un ghid de traversare a graficului

94. Arborele binar Inorder Traversal (Dificultate: medie)

Abordarea noastră de a rezolva această problemă este similară cu problemele anterioare. Dar aici, vom vizita tot ce se află pe partea stângă a unui nod, vom imprima nodul și apoi vom vizita totul din partea dreaptă a nodului.

1612126809 614 Prima cautare in adancime un ghid de traversare a graficului

323. Numărul de componente conectate într-un grafic nedirectat
(Dificultate: medie)

Abordarea noastră aici este de a crea o variabilă numită ans care stochează numărul de componente conectate.

În primul rând, vom inițializa toate vârfurile ca nevizitate. Vom începe de la un nod și, în timp ce efectuăm DFS pe acel nod (desigur, folosind vraja noastră magică), va marca toate nodurile conectate la acesta ca fiind vizitate. Valoarea a ans va fi incrementat cu 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<adj.length; i++){
            adj[i] = new ArrayList<Integer>();
        }

        // create the adjacency list
        for(int[] e: edges){
            int from = e[0];
            int to = e[1];
            adj[from].add(to);
            adj[to].add(from);

        }
        Stack<Integer> stack = new Stack<>();
        int ans = 0; // ans = count of how many times DFS is carried out

        // this for loop through the entire graph
        for(int i = 0; i < n; i++){
            // if a node is not visited
            if(!visited[i]){
                ans++;
                //push it in the stack
                stack.push(i);

             
                while(!stack.empty()) {

                    int current = stack.peek();
                    stack.pop(); //pop the node
                    visited[current] = true; // mark the node as visited

                    List<Integer> list1 = adj[current];

        // push the connected components of the current node into stack
                    for (int neighbours:list1) {
                        if (!visited[neighbours]) {
                            stack.push(neighbours);
                        }
                    }
                }

        }
    }
        return ans;
    }
}

200. Numărul de insule (Dificultate: medie)

Acest lucru se încadrează într-o categorie generală de probleme în care trebuie să găsim numărul de componente conectate, dar detaliile sunt cam modificate.

Instinctual, ați putea crede că odată ce găsim un „1” inițiam o nouă componentă. Facem un DFS din acea celulă în toate cele 4 direcții (sus, jos, dreapta, stânga) și ajungem la toate 1 conectate la acea celulă. Toate aceste 1 conectate între ele aparțin aceluiași grup și, prin urmare, valoarea noastră de numara este incrementat cu 1. Marcăm aceste celule de 1 ca vizitate și trecem la numărarea altor componente conectate.

1612126810 74 Prima cautare in adancime un ghid de traversare a graficului

547. Cercuri de prietenie (dificultate: medie)

Aceasta urmează, de asemenea, același concept ca și găsirea numărului de componente conectate. În această întrebare, avem o matrice NxN, dar numai N prieteni în total. Marginile sunt date direct prin celule, așa că trebuie să traversăm un rând pentru a obține vecinii pentru un anumit „prieten”.

Observați că aici, folosim același model de stivă ca problemele noastre anterioare.

1612126810 1 Prima cautare in adancime un ghid de traversare a graficului

Asta e tot pentru astăzi! Sper că acest lucru te-a ajutat să înțelegi mai bine DFS și că ți-a plăcut tutorialul. Vă rugăm să recomandați această postare dacă credeți că poate fi utilă pentru altcineva!