CKTIS / C
Recherche en profondeur (DFS) en C
La recherche en profondeur (DFS) explore la branche suivante d’un graphe avant de revenir aux autres voisins. L’exemple présente un parcours récursif, le marquage des sommets visités et un ordre d’affichage déterministe.
Version : C23; repository compiler flag, production runtime not attested
Syntaxe
void dfs(int v);La recherche en profondeur (depth-first search, DFS) explore la branche suivante avant de revenir aux autres voisins. Le parcours récursif (recursive traversal) met en œuvre ce modèle en appelant la fonction pour les voisins non visités ; au retour de l’appel, la boucle précédente reprend. DFS ne précise pas à lui seul à quel moment un sommet est traité ; cet exemple l’affiche lors de sa découverte.
Dans l’exemple, graph[v][u] représente une arête orientée de v vers u. La fonction dfs définit visited[v] avant les appels suivants, de sorte que le cycle 0 → 1 → 3 → 0 ne provoque pas une nouvelle visite de 0. L’ordre croissant de u produit 0, 1, 3, 2, 4, chacun sur sa propre ligne. Tous les indices fournis sont compris entre 0 et N - 1.
L’appel dfs(0) ne visite que les sommets accessibles depuis 0. Pour parcourir tout le graphe, appelez dfs pour chaque sommet qui n’a pas encore été visité. Réinitialisez visited avant de relancer un parcours indépendant.
Avec une matrice d’adjacence, un parcours complet prend O(V²) en temps ; une représentation par listes d’adjacence permet O(V + E), où V et E désignent le nombre de sommets et d’arêtes. Le tableau des sommets visités et la pile d’appels demandent O(V) d’espace auxiliaire. Une récursion profonde peut épuiser la pile d’appels ; une pile explicite constitue une solution de remplacement. Le contexte du dépôt mentionne C23 comme option du compilateur, mais ne garantit pas un environnement de production.
Exemples
#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;
}
Résultat
0 1 3 2 4
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.