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

CKTIS / C

Búsqueda en profundidad (DFS) en C

Recorre un árbol de grupos de forma recursiva: comprueba primero los elementos del grupo actual, después sus subgrupos, y guarda si lo necesitas un puntero al grupo de la primera coincidencia.

Versión: ISO C23; implementation support may vary

Sintaxis

#include <stddef.h>

typedef struct Group {
    const char *name;
    const int *items;
    size_t item_count;
    struct Group **subs;
} Group;

static bool find_item(Group *group, int target, Group **out);

find_item realiza una búsqueda en profundidad (DFS) en un árbol de grupos. Cada llamada comprueba primero los elementos del grupo actual y luego visita sus subgrupos en el orden del arreglo. La recursión explora un subárbol completo antes de pasar al siguiente, salvo que encuentre antes el objetivo. true se propaga inmediatamente; false indica que no hubo coincidencia en ese subárbol.

En la estructura autorreferencial, struct Group **subs apunta al primer elemento de un arreglo de punteros a grupos, no a un arreglo de objetos Group. Dentro de la definición ya se puede usar la etiqueta struct Group, pero el tipo sigue incompleto y el alias Group de este typedef aún no está en el ámbito. La estructura puede contener un miembro de tipo puntero, pero no directamente un objeto de su propio tipo.

La macro NULL, definida en <stddef.h>, se expande a una constante de puntero nulo. subs == NULL indica que no hay arreglo de subgrupos; si lo hay, la primera entrada NULL es un centinela de fin, no un hueco que se pueda saltar. Mantén vivos los grupos y los arreglos durante la búsqueda, y el grupo hallado mientras uses el puntero guardado. Si falta el centinela, puede producirse una lectura fuera de los límites. En cada grupo cuyo item_count no sea cero, items debe apuntar al inicio de un tramo de al menos item_count elementos de tipo int que se puedan leer.

Lo opcional es la escritura, no el argumento: pasa &found para una variable de tipo Group *, o NULL para comprobar solo la existencia. La función guarda el grupo mediante *out únicamente si hay coincidencia y out != NULL. Si devuelve false, no cambia la variable del llamador, que puede conservar un resultado anterior.

En el peor caso el tiempo es O(G + I) para G grupos e I elementos locales, con O(h) llamadas simultáneas para una altura h. Para entradas muy profundas, considera una pila explícita; en un grafo con ciclos, registra los nodos visitados. El ejemplo usa sintaxis de ISO C23; la compatibilidad depende de la implementación.

Ejemplos

#include <stddef.h>
#include <stdio.h>

typedef struct Group {
    const char *name;
    const int *items;
    size_t item_count;
    struct Group **subs;
} Group;

static bool find_item(Group *group, int target, Group **out)
{
    for (size_t i = 0; i < group->item_count; ++i) {
        if (group->items[i] == target) {
            if (out != NULL) {
                *out = group;
            }
            return true;
        }
    }

    if (group->subs != NULL) {
        for (size_t i = 0; group->subs[i] != NULL; ++i) {
            if (find_item(group->subs[i], target, out)) {
                return true;
            }
        }
    }
    return false;
}

int main(void)
{
    const int sevens[] = {7};
    const int answers[] = {42};
    Group deep = {"deep", answers, 1, NULL};
    Group right = {"right", answers, 1, NULL};
    Group *left_subs[] = {&deep, NULL};
    Group left = {"left", sevens, 1, left_subs};
    Group *root_subs[] = {&left, &right, NULL};
    Group root = {"root", sevens, 1, root_subs};

    Group *found = NULL;
    if (find_item(&root, 7, &found)) {
        printf("7 -> %s\n", found->name);
    }
    if (find_item(&root, 42, &found)) {
        printf("42 -> %s\n", found->name);
    }
    printf("42 exists: %s\n", find_item(&root, 42, NULL) ? "yes" : "no");
    if (!find_item(&root, 99, &found)) {
        printf("99 missing; saved group: %s\n", found->name);
    }
    return 0;
}

Resultado

7 -> root
42 -> deep
42 exists: yes
99 missing; saved group: deep

`7` se encuentra en `root` antes de revisar los subgrupos. Para `42`, el subárbol `left` lleva a `deep` antes de visitar `right`. La llamada con `NULL` solo comprueba la existencia; al no encontrar `99`, `found` sigue apuntando a `deep`.

Lecciones relacionadas

  • C · Lección 79 · Avanzado · Versión: 3

Fuentes