Implementation (Part 2)
Lição 6 de 9 do curso Busca em Largura (BFS) - Algoritmos de Grafos da Coddy.
Agora, percorremos o grafo em camadas com uma fila.
Desafio
MédioAgora construa o percurso completo.
Escreva uma função chamada bfs que receba n, o array plano edges (não direcionado) e um vértice start, e retorne a ordem em que o BFS visita os vértices a partir de start.
Construa a lista de adjacência (vizinhos ordenados de forma crescente), depois use uma fila: marque e coloque o início na fila e, repetidamente, retire um vértice da fila, registre-o e coloque seus vizinhos não visitados na fila. Apenas os vértices alcançáveis a partir de start são visitados.
Experimente você mesmo
#include <stdlib.h>
int* bfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// Escreva o código aqui
*returnSize = 0;
return edges;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Busca em Largura (BFS) - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity