Busca em Profundidade (DFS)

A busca em profundidade é um algoritmo para percorrer ou buscar em uma estrutura de dados, como um grafo ou uma árvore, indo o mais fundo possível ao longo de cada ramificação antes de retroceder. Esse algoritmo é implementado usando uma abordagem recursiva ou uma abordagem usando uma pilha (stack).

Algoritmo:

1. Comece em um nó inicial e marque-o como visitado.
2. Para cada nó adjacente não visitado, repita o passo 1 recursivamente (ou usando uma pilha).
3. Repita até que todos os nós sejam visitados.

A busca em profundidade é utilizada para várias tarefas, como encontrar componentes conexos em um grafo não direcionado, verificar se um grafo é acíclico e percorrer uma árvore.

Exemplo em Go:

Aqui está um exemplo detalhado de busca em profundidade em um grafo não direcionado usando uma abordagem recursiva:

            
           package main

            import "fmt"

            type Graph struct {
                Vertices []*Vertex
            }

            type Vertex struct {
                Key      int
                Visited  bool
                Neighbors []*Vertex
            }

            func main() {
                // Construindo um grafo de exemplo
                graph := &Graph{}
                for i := 0; i < 5; i++ {
                    graph.Vertices = append(graph.Vertices, &Vertex{Key: i})
                }
                graph.Vertices[0].Neighbors = []*Vertex{graph.Vertices[1], graph.Vertices[2]}
                graph.Vertices[1].Neighbors = []*Vertex{graph.Vertices[3]}
                graph.Vertices[2].Neighbors = []*Vertex{graph.Vertices[4]}

                // Realizando a busca em profundidade
                fmt.Println("Busca em Profundidade:")
                dfs(graph.Vertices[0])
            }

            func dfs(vertex *Vertex) {
                if vertex == nil || vertex.Visited {
                    return
                }
                fmt.Println(vertex.Key)
                vertex.Visited = true
                for _, neighbor := range vertex.Neighbors {
                    dfs(neighbor)
                }
            }

            
         

Neste exemplo:

• Definimos um grafo não direcionado com 5 vértices e suas conexões.
• Implementamos a função dfs que realiza a busca em profundidade a partir de um vértice específico.
• Marcamos cada vértice visitado para garantir que não visitemos o mesmo vértice mais de uma vez.
• Percorremos recursivamente cada vizinho não visitado de um vértice.

Esse é um exemplo básico de como implementar a busca em profundidade em Go. É importante notar que existem várias maneiras de implementar DFS, incluindo abordagens iterativas usando pilhas. Escolha a abordagem que melhor se adapta às suas necessidades e ao problema em questão.