BFS
Lezione 10 di 14 del corso Grafi - Serie sulle strutture dati #9 di Coddy.
Le prossime sfide sono progettate per usare la classe Graph che hai appena creato.
Ogni sfida include un file graph bloccato (Graph finale del capitolo precedente) e un nuovo file solution in cui scrivi una funzione che USA Graph.
Il nostro primo algoritmo: Ricerca in ampiezza. Partendo da un vertice, BFS visita tutti i vertici raggiungibili a ondate: prima il punto di partenza, poi tutti quelli a distanza di un arco, poi tutti quelli a distanza di due archi e così via. L'implementazione classica usa una coda: inserisci il punto di partenza nella coda, poi estrai ripetutamente un vertice, registralo come visitato e inserisci nella coda i suoi vicini non visitati.
Poiché gli elenchi dei vicini non hanno un ordine fisso, due esecuzioni corrette di BFS possono produrre ordini di visita diversi. Per rendere deterministica la risposta in questa sfida, ordina i vicini di ogni vertice in ordine crescente prima di inserirli nella coda.
Sfida
FacileScrivi una funzione bfs che riceve un array di interi bidimensionale adjacency (ogni riga è un arco [u, v]) e un intero start, e restituisce l’ordine di visita BFS a partire da start come elenco di interi.
Costruisci il grafo: per ogni [u, v] in adjacency, chiama g.addEdge(u, v). Poi esegui la BFS a partire da start usando una coda. Quando elabori i vicini di un vertice, ordinali in ordine crescente affinché l’output sia deterministico.
Devi usare la classe Graph (fornita in graph): non usare le strutture integrate del linguaggio (mappe, insiemi) per rappresentare l’adiacenza. I dati ausiliari per l’algoritmo (insiemi dei visitati, code) possono usare i tipi della libreria standard.
Provalo tu
#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;
}
Tutte le lezioni di Grafi - Serie sulle strutture dati #9
Esercitati da solo: Compilatore C online