Estrutura de dados - amplitude primeiro transversal

O algoritmo Breadth First Search (BFS) percorre um gráfico em um movimento de largura e usa uma fila para lembrar de obter o próximo vértice para iniciar uma pesquisa, quando um beco sem saída ocorre em qualquer iteração.

Como no exemplo dado acima, o algoritmo BFS atravessa de A para B para E para F primeiro e depois para C e G por último para D. Ele emprega as seguintes regras.

• Rule 1- Visite o vértice não visitado adjacente. Marque como visitado. Mostre-o. Insira-o em uma fila.

• Rule 2 - Se nenhum vértice adjacente for encontrado, remova o primeiro vértice da fila.

• Rule 3 - Repita a Regra 1 e a Regra 2 até que a fila esteja vazia.

Degrau	Travessia	Descrição
1		Inicialize a fila.
2		Começamos visitando S (nó inicial) e marque-o como visitado.
3		Em seguida, vemos um nó adjacente não visitado de S. Neste exemplo, temos três nós, mas em ordem alfabética, escolhemosA, marque-o como visitado e coloque-o na fila.
4		Em seguida, o nó adjacente não visitado de S é B. Nós o marcamos como visitado e o colocamos na fila.
5		Em seguida, o nó adjacente não visitado de S é C. Nós o marcamos como visitado e o colocamos na fila.
6		Agora, Sé deixado sem nós adjacentes não visitados. Então, retiramos da fila e encontramosA.
7		De A temos Dcomo nó adjacente não visitado. Nós o marcamos como visitado e o colocamos na fila.

Nesta fase, não ficamos sem nós não marcados (não visitados). Mas, de acordo com o algoritmo, continuamos retirando a fila para obter todos os nós não visitados. Quando a fila é esvaziada, o programa acabou.

A implementação deste algoritmo em linguagem de programação C pode ser vista aqui .