https://docs.google.com/presentation/d/e/2PACX-1vQ9bPnukkrFaZfhZhyPCzKnNoTc3v7WQMAAChmbgLzTzql6SZU_1pHfUCRRpqYucA/pubembed?start=false&loop=false&delayms=3000
A Busca em Largura explora o grafo nível por nível, partindo de um vértice inicial e visitando todos os seus vizinhos antes de avançar para o próximo nível de vizinhos1. Utiliza uma fila para controlar a ordem de exploração.
BFS(Grafo G, vértice s):
criar fila Q
marcar s como visitado
enfileirar(Q, s)
enquanto Q não estiver vazia:
v ← desenfileirar(Q)
para cada w em vizinhos(v):
se w não visitado:
marcar w como visitado
enfileirar(Q, w)
Ilustração do processo de exploração em níveis.
Ilustração da Busca em Largura (BFS) explorando níveis do grafo
A Busca em Profundidade mergulha o mais profundamente possível em cada ramo antes de retroceder (backtracking) para explorar ramificações não visitadas2. Emprega uma pilha (ou recursão) para registrar o caminho atual.
DFS(Grafo G, vértice v):
marcar v como visitado
para cada w em vizinhos(v):
se w não visitado:
DFS(G, w)
Exemplo de retrocessos no momento em que não há mais vizinhos não visitados.
Ilustração da Busca em Profundidade (DFS) mostrando retrocessos