Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C

Búsqueda en profundidad (DFS) en C

La búsqueda en profundidad (DFS) explora la siguiente rama de un grafo antes de volver a los demás vecinos. El ejemplo muestra un recorrido recursivo, el marcado de vértices visitados y un orden de impresión determinista.

Versión: C23; repository compiler flag, production runtime not attested

Sintaxis

void dfs(int v);

La búsqueda en profundidad (depth-first search, DFS) explora la siguiente rama antes de volver a los demás vecinos. El recorrido recursivo (recursive traversal) aplica este patrón mediante llamadas a la función para los vecinos no visitados; al volver de una llamada, se reanuda el bucle anterior. DFS por sí sola no especifica cuándo se procesa un vértice; este ejemplo lo imprime al descubrirlo.

En el ejemplo, graph[v][u] representa una arista dirigida de v a u. La función dfs establece visited[v] antes de realizar más llamadas, por lo que el ciclo 0 → 1 → 3 → 0 no vuelve a entrar en 0. El orden creciente de u produce 0, 1, 3, 2, 4, cada uno en una línea. Todos los índices proporcionados están dentro del intervalo 0–N - 1.

La llamada dfs(0) visita únicamente los vértices alcanzables desde 0. Para recorrer todo el grafo, llama a dfs para cada vértice que aún no se haya visitado. Restablece visited antes de iniciar de nuevo un recorrido independiente.

Con una matriz de adyacencia, un recorrido completo requiere O(V²) de tiempo; una representación con listas de adyacencia permite O(V + E), donde V y E son el número de vértices y aristas. El array de visitados y la pila de llamadas requieren O(V) de espacio auxiliar. Una recursión profunda puede agotar la pila de llamadas; una pila explícita es una alternativa. El contexto del repositorio señala C23 como opción del compilador, pero no confirma un entorno de producción.

Ejemplos

#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;
}

Resultado

0
1
3
2
4

El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.

Fuentes