DFS
Lección 11 de 14 del curso Grafos - Serie de Estructuras de Datos #9 de Coddy.
La Búsqueda en profundidad (Depth-First Search) va a lo profundo antes de ir a lo ancho. Comenzando en un vértice, sigue una arista lo más lejos posible, luego retrocede e intenta con la siguiente. La versión iterativa utiliza una pila (stack): extrae un vértice, regístralo e inserta sus vecinos no visitados de nuevo.
Para que DFS produzca un orden de recorrido determinista en este desafío, inserta los vecinos en orden inverso (reverse-sorted). De esa manera, el vecino más pequeño queda en la parte superior de la pila y se procesa primero, coincidiendo con el orden que produciría un DFS recursivo sobre vecinos ascendentes.
Ten cuidado con que un vértice sea insertado dos veces (diferentes vecinos pueden tenerlo). Verifica el conjunto de visitados al principio del bucle y omítelo si ya ha sido visitado.
Desafío
FácilEscribe una función dfs que reciba un arreglo bidimensional de enteros adjacency (cada fila es una arista [u, v]) y un entero start, y devuelva el orden de visita DFS desde start como una lista de enteros.
Construye el grafo agregando cada arista. Utiliza DFS iterativo mediante una pila: extrae un vértice, si no ha sido visitado, regístralo e inserta sus vecinos en orden inverso para que el más pequeño se procese primero.
Debes utilizar la clase Graph (proporcionada en graph); no utilices elementos integrados del lenguaje (mapas, conjuntos) para modelar la adyacencia. Los datos auxiliares para el algoritmo (conjuntos de visitados, pilas) pueden utilizar tipos de la biblioteca estándar.
Pruébalo tú mismo
#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;
}