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.
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?
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ó.
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.
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.
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!