BFS
Lição 10 de 14 do curso Grafos - Série de Estruturas de Dados #9 da Coddy.
Os próximos desafios foram projetados para usar a classe Graph que você acabou de construir.
Cada desafio fornece um arquivo graph bloqueado (o Graph final do capítulo anterior) e um arquivo solution novo onde você escreve uma função que USA o Graph.
Nosso primeiro algoritmo: Busca em Largura (Breadth-First Search). Começando por um vértice, a BFS visita todos os vértices alcançáveis em ondas: primeiro o inicial, depois tudo o que estiver a uma aresta de distância, depois tudo a duas arestas de distância, e assim por diante. A implementação clássica usa uma fila (queue): enfileire o início, depois desenfileire repetidamente, registre o vértice como visitado e enfileire quaisquer vizinhos não visitados.
Como as listas de vizinhos não possuem uma ordem fixa, duas execuções corretas de BFS podem produzir ordens de percurso diferentes. Para tornar a resposta determinística neste desafio, ordene os vizinhos de cada vértice de forma ascendente antes de enfileirá-los.
Desafio
FácilEscreva uma função bfs que recebe um array de inteiros 2D adjacency (cada linha é uma aresta [u, v]) e um inteiro start, e retorna a ordem de visita BFS a partir de start como uma lista de inteiros.
Construa o grafo: para cada [u, v] em adjacency, chame g.addEdge(u, v). Em seguida, realize a BFS a partir de start usando uma fila. Ao processar os vizinhos de um vértice, ordene-os de forma crescente para que a saída seja determinística.
Você deve usar a classe Graph (fornecida em graph) - não use recursos nativos da linguagem (mapas, conjuntos) para modelar a adjacência. Dados auxiliares para o algoritmo (conjuntos de visitados, filas) podem usar tipos da biblioteca padrão (stdlib).
Experimente você mesmo
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}