CKTIS / C
Ricerca in profondità (DFS) in C
La ricerca in profondità (DFS) esplora il ramo successivo di un grafo prima di tornare agli altri vicini. L’esempio mostra una visita ricorsiva, la marcatura dei vertici visitati e un ordine di stampa deterministico.
Versione: C23; repository compiler flag, production runtime not attested
Sintassi
void dfs(int v);La ricerca in profondità (depth-first search, DFS) esplora il ramo successivo prima di tornare agli altri vicini. La visita ricorsiva (recursive traversal) realizza questo schema chiamando la funzione per i vicini non visitati; al ritorno da una chiamata, riprende il ciclo precedente. DFS non specifica di per sé quando viene elaborato un vertice; questo esempio lo stampa al momento della scoperta.
Nell’esempio, graph[v][u] rappresenta un arco diretto da v a u. La funzione dfs imposta visited[v] prima di effettuare altre chiamate, quindi il ciclo 0 → 1 → 3 → 0 non visita nuovamente 0. L’ordine crescente di u produce 0, 1, 3, 2, 4, ciascuno su una riga. Tutti gli indici passati rientrano nell’intervallo 0–N - 1.
La chiamata dfs(0) visita solo i vertici raggiungibili da 0. Per coprire l’intero grafo, chiama dfs per ogni vertice non ancora visitato. Reimposta visited prima di avviare di nuovo una visita indipendente.
Con una matrice di adiacenza, una visita completa richiede tempo O(V²); una rappresentazione con liste di adiacenza consente O(V + E), dove V ed E indicano il numero di vertici e di archi. L’array dei visitati e lo stack delle chiamate richiedono O(V) di spazio ausiliario. Una ricorsione profonda può esaurire lo stack delle chiamate; uno stack esplicito è un’alternativa. Il contesto del repository indica C23 come opzione del compilatore, ma non attesta un ambiente di produzione.
Esempi
#include <stdio.h>
enum { N = 5 };
static const int graph[N][N] = {
{0, 1, 1, 0, 0},
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{1, 0, 0, 0, 0},
{0, 0, 0, 0, 0}
};
static int visited[N] = {0};
static void dfs(int v)
{
visited[v] = 1;
printf("%d\n", v);
for (int u = 0; u < N; ++u) {
if (graph[v][u] && !visited[u]) {
dfs(u);
}
}
}
int main(void)
{
dfs(0);
return 0;
}
Risultato
0 1 3 2 4
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.