Implementazione (Parte 2)

Lezione 6 di 9 del corso Ricerca in ampiezza - Algoritmi sui grafi di Coddy.

Ora attraversiamo il grafo a livelli usando una coda.

Sfida

Medio

Ora realizza la visita completa.

Scrivi una funzione chiamata bfs che accetta n, l’array piatto edges (non orientato) e un vertice start, e restituisce l’ordine in cui BFS visita i vertici a partire da start.

Costruisci la lista di adiacenza (con i vicini ordinati in modo crescente), poi usa una coda: contrassegna e inserisci in coda il vertice iniziale, quindi rimuovi ripetutamente un vertice dalla coda, registralo e inserisci in coda i suoi vicini non visitati. Vengono visitati solo i vertici raggiungibili da start.

Provalo tu

#include <stdlib.h>

int* bfs(int n, int* edges, int edges_size, int start, int* returnSize) {
    // Scrivi il codice qui
    *returnSize = 0;
    return edges;
}