À medida que você começa a trabalhar com estruturas de dados e algoritmos, logo perceberá que uma das operações comuns que você precisará realizar é visitar cada nó. Este processo é conhecido como "traversing" a estrutura de dados. Percursos são usados para fazer algo com cada nó na estrutura de dados, como imprimir seus valores, encontrar um valor específico ou realizar certas operações nos nós. Ao visitar sistematicamente cada nó, você garante que o processo não pule nenhum nó. Mas como você determina a ordem na qual deve percorrer a estrutura de dados? Onde o processo deve começar e como o próximo nó deve ser selecionado? Sem uma maneira clara de percorrer a estrutura de dados, atravessá-la seria como caminhar por um labirinto sem um caminho específico para seguir. É aí que algoritmos como breadth-first search (BFS) e depth-first search (DFS) se tornam realmente importantes. Eles são comumente usados para percorrer grafos e para encontrar um caminho entre dois nós. Quando são usados para percorrer uma estrutura de dados, eles definem a ordem na qual os nós devem ser visitados para garantir que nenhum deles seja pulado. Vamos começar com a busca em largura (BFS).

Busca em Largura (BFS)

Busca em largura (BFS) é um algoritmo que visita todos os nós vizinhos antes de passar para o próximo nível no grafo. Ele pode ser usado para encontrar o caminho mais curto entre dois nós em um grafo não ponderado porque ele analisa todos os nós em cada nível, então ele encontra o caminho com menos arestas primeiro. Este algoritmo é comumente implementado usando uma estrutura de dados de fila para acompanhar os nós que foram visitados. Filas seguem o método FIFO (first in, first out), onde o primeiro nó que foi adicionado à fila é o primeiro a ser removido. O algoritmo funciona assim: * Você começa em um nó específico. * Esse nó está marcado como visitado e adicionado à fila. * Enquanto a fila não estiver vazia, o nó atual é removido da fila (dequeued). Então, para cada um dos seus vizinhos, se o vizinho não foi visitado, ele é marcado como visitado e adicionado à fila. Uma consideração importante é que, como a busca em largura (BFS) requer armazenar uma fila na memória e essa fila pode ter um grande número de nós, os requisitos de espaço desse algoritmo podem ser consideráveis. Isso é especialmente verdadeiro para grafos com um grande número de nós no mesmo nível. Vamos ver um exemplo de BFS aplicado a um tipo específico de grafo chamado árvore. Você aprenderá mais sobre árvores em uma lição futura, mas elas são essencialmente grafos sem ciclos, onde os nós são organizados em uma hierarquia. Ciclos são caminhos que começam e terminam no mesmo nó. Vamos aplicar o algoritmo de busca em largura (BFS) a esta árvore: <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-depth-first-and-breadth-first-search-work-1.png" alt="A tree diagram showing nodes A through G arranged in a hierarchy. Node A is at the root, with children B and C. Node B has children D and E, and node C has children F and G."> Passo 1: Começamos na raiz da árvore, no nó A. Adicionamos A à fila e imediatamente o marcamos como visitado. * Fila: [A] * Visitado: {A} Passo 2: Removemos o nó A da fila. Adicionamos seus filhos não visitados (nó B e depois nó C) à fila e os marcamos como visitados. * Fila: [B, C] * Visitado: {A, B, C} A ordem na qual os nós no mesmo nível são adicionados à fila é definida pela implementação da estrutura de dados e pela ordem na qual as arestas (conexões) são armazenadas na representação do grafo. Se a implementação for consistente, a ordem específica na qual os nós no mesmo nível são percorridos não afetará a correção do algoritmo. Ele ainda visitará cada nó nível por nível. Passo 3: Removemos da fila o nó B. Adicionamos seus filhos não visitados, (nó D e então nó E), à fila e os marcamos como visitados. * Fila: [C, D, E] * Visitados: {A, B, C, D, E} Passo 4: Removemos da fila o nó C. Adicionamos seus filhos não visitados, (nó F e depois nó G), à fila e os marcamos como visitados. * Fila: [D, E, F, G] * Visitados: {A, B, C, D, E, F, G} Passo 5: Removemos o nó D da fila. Este nó não possui filhos não visitados, então nada muda no conjunto de visitados. * Fila: [E, F, G] * Visitados: {A, B, C, D, E, F, G} Passo 6: Removemos da fila o nó E. Este nó não possui filhos não visitados, então nada muda no conjunto de visitados. * Fila: [F, G] * Visitados: {A, B, C, D, E, F, G} Passo 7: Removemos F da fila. Este nó não possui filhos não visitados, então nada muda no conjunto de visitados. * Fila: [G] * Visitados: {A, B, C, D, E, F, G} Passo 8: Removemos G da fila. Este nó não possui filhos não visitados, então nada muda no conjunto de visitados. * Fila: [] * Visitados: {A, B, C, D, E, F, G} Quando a fila está vazia, a travessia está completa. Os nós foram percorridos nesta ordem: A → B → C → D → E → F → G <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-depth-first-and-breadth-first-search-work-2.png" alt="The same tree diagram with arrows showing the BFS traversal order: A to B to C to D to E to F to G, demonstrating level-by-level visitation."> Observe como o algoritmo visita os nós por nível. Começamos no nó A, depois passamos para o próximo nível para visitar os nós B e C, depois para o próximo nível para os nós D, E, F e G. Esse é o princípio básico da busca em largura (BFS).

Busca em Profundidade (DFS)

Enquanto a busca em largura (BFS) primeiro visita todos os nós vizinhos no mesmo nível, a busca em profundidade (DFS) segue cada ramo o mais profundamente possível antes de retroceder. Você pode imaginar este algoritmo como explorando um labirinto escolhendo um caminho específico e seguindo-o até chegar a um beco sem saída ou à saída. Se você chegar a um beco sem saída, você volta e escolhe um caminho diferente. A busca em profundidade (DFS) é comumente usada para resolver quebra-cabeças com uma única solução, detectar ciclos em um grafo e encontrar componentes conectados do grafo. Este algoritmo pode ser implementado usando recursão ou uma estrutura de dados de pilha para acompanhar os nós visitados. Pilhas seguem o método LIFO (last in, first out), onde o último nó que foi adicionado à pilha é o primeiro a ser removido da pilha. O algoritmo funciona assim: * Comece em um nó específico. * Esse nó está marcado como visitado e adicionado à pilha. * Enquanto a pilha não estiver vazia, o nó atual é retirado (removido). É nesse momento que o visitamos ou processamos (por exemplo, imprimindo seu valor). Em seguida, todos os seus vizinhos não visitados são marcados como visitados e adicionados à pilha. Uma das limitações deste algoritmo é que nem sempre é garantido encontrar o caminho mais curto entre dois nós em um grafo não ponderado. Vamos ver um exemplo de Depth-First Search (DFS) aplicado ao nosso exemplo de árvore. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-depth-first-and-breadth-first-search-work-3.png" alt="The same tree diagram as before, showing nodes A through G in their hierarchical structure, ready for DFS demonstration."> Passo 1: Começamos no nó raiz A. Marcamos ele como visitado e adicionamos à pilha. * Pilha: [A] * Visitado: {A} Passo 2: Removemos o nó A da pilha. Então, adicionamos seus filhos não visitados, o nó B e o nó C, à pilha. Nós os adicionaremos em ordem inversa, C e depois B, para que B fique no topo (LIFO) e seja processado em seguida. Também os marcamos como visitados. * Pilha: [C, B] * Visitado: {A, B, C} Passo 3: Removemos o nó B da pilha. Então, adicionamos seus filhos não visitados, o nó D e o nó E, à pilha em ordem inversa (E e depois D). Também os marcamos como visitados. * Pilha: [C, E, D] * Visitados: {A, B, C, D, E} Passo 4: Removemos o nó D da pilha. Este nó não tem filhos para adicionar à pilha. * Pilha: [C, E] * Visitados: {A, B, C, D, E} Passo 5: Removemos o nó E da pilha. Este nó não tem filhos para adicionar à pilha. * Pilha: [C] * Visitados: {A, B, C, D, E} Passo 6: Removemos o nó C. Então, adicionamos seus filhos, o nó F e o nó G, à pilha em ordem inversa (nó G e depois nó F) e os marcamos como visitados. * Pilha: [G, F] * Visitados: {A, B, C, D, E, F, G} Passo 7: Removemos o nó F da pilha. Este nó não tem filhos para adicionar à pilha. * Pilha: [G] * Visitados: {A, B, C, D, E, F, G} Passo 8: Removemos o nó G. Este nó não tem filhos para adicionar à pilha. * Pilha: [] * Visitados: {A, B, C, D, E, F, G} Quando a pilha está vazia, a travessia é concluída e todos os nós foram visitados. O algoritmo visitou os nós nesta ordem: A → B → D → E → C → F → G <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-depth-first-and-breadth-first-search-work-4.png" alt="The tree diagram with numbers showing the DFS traversal order: A(1), B(2), D(3), E(4), C(5), F(6), G(7), demonstrating depth-first exploration of branches."> Observe como começamos no nó A e depois descemos toda a árvore até o nó B e os nós D e E antes de subirmos novamente para o nó C e depois os nós F e G. Este é o princípio central da busca em profundidade (DFS), percorrendo caminhos completos antes de retroceder e encontrar outros caminhos. Neste caso, resolvemos este exemplo usando uma pilha. Alternativamente, a busca em profundidade (DFS) pode ser implementada usando recursão, onde a função processa o nó atual e então faz uma chamada para si mesma para cada um de seus vizinhos não visitados. A pilha de chamadas da função gerencia implicitamente a ordem LIFO (last-in, first-out). Tanto a busca em largura (BFS) quanto a busca em profundidade (DFS) são algoritmos essenciais para percorrer grafos e árvores. A busca em largura (BFS) explora os nós nível por nível, o que é perfeito para encontrar o caminho mais curto em um grafo não ponderado. Por outro lado, a busca em profundidade (DFS) segue um ramo o mais profundamente possível antes de retroceder, o que é perfeito para resolver labirintos e detectar ciclos. Entender suas vantagens e desvantagens é útil para escolher o mais adequado para um problema específico.