Algoritmos em Grafos: Busca em Largura e Busca em profundidade
O que são Grafos?
Grafos são um ramo da matemática que estuda relações entre objetos pertencentes a um determinado conjunto.
Você pode pensar por exemplo que $${a, b}$$ é um grafo que leva de a para b.
Historicamente, foi Leonhard Euler, mesmo criador da identidade de Euler.
$$E^{i\pi} + 1 = 0$$
Publicou em 1736 um artigo sobre o problema das sete pontes de Königsberg.
E este foi considerado o ponto de partida da teoria dos grafos.
Onde grafos são usados?
Dentro da computação em todo lugar diretamente ou indiretamente.
- Redes Neurais
- Estrutura de árvores
- Rede de computadores
- Computação Gráfica
- Redes Sociais
Se precisa de coordenação provavelmente vai ter um grafo incluso.
Fica ainda mais interessante porque Linguagens Formais e Automatos.
Fundamental para a construções de linguagens (programação, regular, marcação).
Também usa grafos como estrutura de representação para automatos e diagramas de transição
Algoritmos de Busca
Como um grafo é formado por relações, contendo ou não um direcionamento.
É necessário sob algum critério percorrer esse grafo.
E para isso temos um problema essencial que precisa ser resolvido.
Qual critério?
Normalmente ou estamos trabalhando com grafos esparsos ou grafos densos.
Sendo grafos esparsos aqueles que tem poucas arestas em relação ao número de vértices.
E grafos densos aqueles que tem muitas arestas.
Essa caracteristica influência diretamente a escolha do algoritmo de busca mais eficiente.
Os dois algoritmos mais clássicos para essa busca são:
- (BFS - Breadth First Search): Busca em Largura.
- (DFS - Depth First Search): Busca em profundidade.
Algoritmos
Busca em Largura (BFS)
O algoritmo de busca em largura explora nível por nível.
Ou seja se pensarmos em uma árvore.
Ele verificaria primeiros os vizinhos da raiz.
Depois os vizinhos dos vizinhos da raiz e por assim vai.
Para fazer isso a gente utiliza uma estrutura de dados fila/queue.
Propriedades da busca em largura
Se existir uma solução, este algoritmo consegue encontrar.
Ótimo em arestas unitárias vai encontrar o caminho mais curto em termo de números de passos.
Complexidade:
Vai ter o tempo de percorrer $$O(V + E)$$ ou seja o tempo para percorrer todos os vertices e arestas.
Espaço: $$O(V)$$ porque precisa armazenar a fila e o conjunto de visitados.
Lógica passo a passo
- Colocamos um nó na fila, e marcamos como visitado.
- Enquanto a fila não estiver vazia:
- Retiramos o primeiro elemento.
- Visitamos todos os vizinhos não visitados do nó.
- Adicionamos esses vizinhos a fila e marcamos como visitados.
Busca em Profundidade
A busca em profundidade em comparação explora todo um ramo do grafo até o fim antes de voltar e explorar outros ramos.
Ao contrário da busca em largura, aqui usamos pilha/stack (Last In, First Out).
Propriedades da busca em profundidade
Completo? Em grafos finitos mas, não garante o caminho mais curto em grafos não ponderados.
Ótimo? Não, não é adequado quando você precisa do menor número de arestas.
Complexidade:
- Tempo: $$O(V + E)$$
- Espaço: $$O(V)$$
Risco Prático em recursão pode estourar a pilha em grafos muito profundos, prefira uma versão iterativa.
Lógica passo a passo
- Marca o nó inicial como visitado e entre nele.
- Para cada vizinho não visitado, repita o processo.
- Quando o nó não tem vizinhos não visitados, realize um backtrack.
- Continue até visitar todos os nós alcançáveis.
Conclusão
Não existe um algoritmo universalmente “melhor”: tudo depende do objetivo.
BFS (Busca em Largura):
Garante o menor caminho em grafos não ponderados.
Mais indicado quando o problema exige a solução mais curta.
DFS (Busca em Profundidade):
Útil para exploração completa, detecção de ciclos, ordenação topológica e backtracking.
Mais indicado quando queremos percorrer toda a estrutura ou analisar propriedades do grafo.
Ambos têm mesma complexidade assintótica $$ O(V+E)$$ mas, se aplicam a cenários distintos.
E devem ser tratados com cautela para não escolher a pior opção por puro achismo.
Ademas, espero que tenham gostado do post e valeu