Você já resolveu um labirinto da vida real? A abordagem que muitos de nós adotam ao resolver um labirinto é que seguimos um caminho até chegar a um beco sem saída e, em seguida, recuamos e refizemos nossos passos para encontrar outro caminho possível.

Essa é exatamente a analogia da pesquisa por profundidade (DFS). É um algoritmo popular de deslocamento de gráfico que começa no nó raiz e percorre o máximo que pode por um determinado ramo e depois segue de novo até encontrar outro caminho inexplorado a ser explorado. Essa abordagem continua até que todos os nós do gráfico tenham sido visitados.

No tutorial de hoje, descobriremos um padrão DFS que será usado para resolver algumas das importantes questões em árvore e gráfico para sua próxima entrevista do Tech Giant! Resolveremos alguns problemas do Medium e Hard Leetcode usando a mesma técnica comum.

Então, vamos começar, sim?

Implementação

Como o DFS tem uma natureza recursiva, ele pode ser implementado usando uma pilha.

Magia DFS:

  1. Empurre um nó para a pilha
  2. Estale o nó
  3. Recupere vizinhos não visitados do nó removido, empurre-os para empilhar
  4. Repita as etapas 1, 2 e 3, desde que a pilha não esteja vazia

Traversals do gráfico

Em geral, existem três percursos DFS básicos para árvores binárias:

  1. Pedido antecipado: Raiz, Esquerda, Direita OU Raiz, Direita, Esquerda
  2. Pós-encomenda: Esquerda, Direita, Raiz OU Direita, Esquerda, Raiz
  3. Em ordem: Esquerda, Raiz, Direita OU Direita, Raiz, Esquerda

144. Transversal de pré-encomenda de árvore binária (dificuldade: média)

Para resolver esta questão, tudo o que precisamos fazer é simplesmente recordar nosso feitiço. Vamos entender muito bem a simulação, já que este é o modelo básico nós estaremos usando para resolver o resto dos problemas.

image 138

Inicialmente, colocamos o nó raiz na pilha. Enquanto a pilha não está vazia, nós a colocamos e empurramos seu filho direito e esquerdo para dentro da pilha.

Quando colocamos o nó raiz, imediatamente o colocamos em nossa lista de resultados. Assim, o primeiro elemento na lista de resultados é a raiz (daí o nome, Pré-encomenda).

O próximo elemento a ser retirado da pilha será o elemento superior da pilha agora: o filho esquerdo do nó raiz. O processo continua de maneira semelhante até que todo o gráfico tenha sido percorrido e todos os valores dos nós da árvore binária entrem na lista resultante.

Sample 2020 04 20 4

145. Transversal de ordem posterior de árvore binária (dificuldade: difícil)

O percurso de pré-encomenda é raiz-esquerda-direitae pós-encomenda é raiz direita-esquerda. Isso significa que o percurso pós-pedido é exatamente o inverso do percurso de pré-pedido.

Portanto, uma solução que pode vir à mente agora é simplesmente reverter a matriz resultante de passagem de pré-encomenda. Mas pense bem – isso custaria O (n) complexidade de tempo para revertê-lo.

Uma solução mais inteligente é copiar e colar o código exato da passagem de pré-ordem, mas coloque o resultado no topo da lista vinculada (índice 0) a cada iteração. Leva um tempo constante para adicionar um elemento ao cabeçalho de uma lista vinculada. Legal certo?

image 143

94. Transversal em ordem de árvore binária (Dificuldade: Média)

Nossa abordagem para resolver esse problema é semelhante aos problemas anteriores. Mas aqui, visitaremos tudo no lado esquerdo de um nó, imprimiremos o nó e, em seguida, visitaremos tudo no lado direito do nó.

image 145

323. Número de componentes conectados em um gráfico não direcionado
(Dificuldade: Média)

Nossa abordagem aqui é criar uma variável chamada ans que armazena o número de componentes conectados.

Primeiro, inicializaremos todos os vértices como não visitados. Começaremos a partir de um nó e, durante a execução do DFS nesse nó (é claro, usando nosso feitiço), ele marcará todos os nós conectados a ele como visitados. O valor de ans será incrementado em 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();
        }

        // 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 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 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. Number of Islands (Dificuldade: Média)

Isso se enquadra em uma categoria geral de problemas em que precisamos encontrar o número de componentes conectados, mas os detalhes são um pouco aprimorados.

Instintivamente, você pode pensar que, uma vez que encontramos um “1”, iniciamos um novo componente. Fazemos um DFS a partir dessa célula nas quatro direções (cima, baixo, direita, esquerda) e alcançamos todos os 1s conectados a essa célula. Todos esses 1s conectados um ao outro pertencem ao mesmo grupo e, portanto, nosso valor de contagem é incrementado em 1. Marcamos essas células de 1 como visitadas e passamos a contar outros componentes conectados.

image 149

547. Círculos de amigos (dificuldade: média)

Isso também segue o mesmo conceito de encontrar o número de componentes conectados. Nesta questão, temos uma matriz NxN, mas apenas N amigos no total. As arestas são dadas diretamente através das células, por isso temos que percorrer uma linha para obter os vizinhos para um “amigo” específico.

Observe que aqui, usamos o mesmo padrão de pilha que nossos problemas anteriores.

image 148

Isso é tudo por hoje! Espero que isso tenha ajudado você a entender melhor o DFS e que tenha gostado do tutorial. Por favor, recomende este post se você acha que pode ser útil para outra pessoa!



Fonte