Introduction

Bem-vindo de volta à série Algoritmos de Grafos! Após a Busca em Profundidade (DFS), voltamos nossa atenção para a Busca em Largura (BFS), a outra travessia fundamental de grafos.

Enquanto a DFS mergulha fundo, a BFS explora em camadas: primeiro o vértice inicial, depois todos os seus vizinhos, depois tudo o que estiver a dois passos de distância, e assim por diante. Essa ordem camada por camada é exatamente o que faz a BFS encontrar os caminhos mais curtos em grafos não ponderados.

Como no restante da série, um grafo é fornecido como n (contagem de vértices, 0 a n - 1) e edges, um array plano de pares não direcionados [u0, v0, u1, v1, ...].

Vamos começar!