DFS
Lezione 11 di 14 del corso Grafi - Serie sulle strutture dati #9 di Coddy.
La ricerca in profondità esplora in profondità prima che in ampiezza. Partendo da un vertice, segue un arco il più lontano possibile, poi torna indietro e prova il successivo. La versione iterativa usa uno stack: estrae un vertice, lo registra e reinserisce i suoi vicini non visitati.
Per fare in modo che la DFS produca un ordine di visita deterministico in questa sfida, inserisci i vicini in ordine inverso e ordinato. In questo modo, il vicino più piccolo si trova in cima allo stack e viene elaborato per primo, riproducendo l'ordine che produrrebbe una DFS ricorsiva sui vicini in ordine crescente.
Fai attenzione a non inserire un vertice due volte (più vicini diversi potrebbero includerlo). Controlla l'insieme dei visitati all'inizio del ciclo e salta il vertice se è già stato visitato.
Sfida
FacileScrivi una funzione dfs che riceva un array di interi 2D adjacency (ogni riga è un arco [u, v]) e un intero start, e restituisca l’ordine di visita DFS a partire da start sotto forma di elenco di interi.
Costruisci il grafo aggiungendo ogni arco. DFS iterativa con uno stack: estrai un vertice; se non è stato visitato, registralo e inserisci i suoi vicini in ordine decrescente, così da elaborare per primo il più piccolo.
Devi usare la classe Graph (fornita in graph): non usare le strutture integrate del linguaggio (mappe, insiemi) per rappresentare l’adiacenza. Per i dati ausiliari dell’algoritmo (insiemi dei vertici visitati, stack) puoi 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 = dfs(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