DFS
Leçon 11 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.
Le parcours en profondeur (Depth-First Search) va en profondeur avant d'aller en largeur. En partant d'un sommet, il suit une arête aussi loin que possible, puis revient sur ses pas et essaie la suivante. La version itérative utilise une pile (stack) : dépilez un sommet, enregistrez-le, et empilez ses voisins non visités.
Pour que le DFS produise un ordre de parcours déterministe dans ce défi, empilez les voisins dans l'ordre trié inverse. De cette façon, le plus petit voisin se retrouve au sommet de la pile et est traité en premier, ce qui correspond à l'ordre qu'un DFS récursif sur des voisins par ordre croissant produirait.
Attention à ce qu'un sommet ne soit pas empilé deux fois (différents voisins peuvent tous deux y mener). Vérifiez l'ensemble des sommets visités au début de la boucle et ignorez le sommet s'il a déjà été visité.
Défi
FacileÉcrivez une fonction dfs qui reçoit un tableau d'entiers 2D adjacency (chaque ligne est une arête [u, v]) et un entier start, et renvoie l'ordre de visite DFS à partir de start sous forme de liste d'entiers.
Construisez le graphe en ajoutant chaque arête. Utilisez un DFS itératif avec une pile : dépilez un sommet, s'il n'a pas été visité, enregistrez-le et empilez ses voisins dans l'ordre inverse du tri afin que le plus petit soit traité en premier.
Vous devez utiliser la classe Graph (fournie dans graph) - n'utilisez pas les types intégrés du langage (maps, sets) pour modéliser l'adjacence. Les données auxiliaires pour l'algorithme (ensembles de sommets visités, piles) peuvent utiliser les types de la bibliothèque standard.
Essayez vous-même
#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;
}