Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C

Pesquisa em profundidade (DFS) em C

Pesquisa recursivamente numa árvore de grupos: verifica primeiro os elementos do grupo atual, depois os seus subgrupos, e guarda, se necessário, um apontador para o grupo da primeira ocorrência.

Versão: ISO C23; implementation support may vary

Sintaxe

#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 faz uma pesquisa em profundidade (DFS) numa árvore de grupos. Cada chamada verifica primeiro os elementos do grupo atual e depois visita os subgrupos pela ordem do vetor. A recursão percorre toda uma subárvore antes de passar à seguinte, a menos que encontre primeiro o valor procurado. true propaga-se de imediato; false indica que não houve correspondência nessa subárvore.

Na estrutura autorreferencial, struct Group **subs aponta para o primeiro elemento de um vetor de apontadores para grupos, não para um vetor de objetos Group. Dentro da definição, a etiqueta struct Group já pode ser usada, mas o tipo ainda está incompleto e o nome alternativo Group deste typedef ainda não está visível. A estrutura pode ter um membro do tipo apontador, mas não pode conter diretamente um objeto do seu próprio tipo.

NULL é uma macro definida em <stddef.h> que é expandida para uma constante de apontador nulo. subs == NULL indica a ausência de um vetor de subgrupos; num vetor existente, a primeira entrada NULL é uma sentinela de fim, não uma posição vazia que possa ser ignorada. Os grupos e os vetores têm de existir durante a pesquisa, e o grupo encontrado tem de continuar a existir enquanto usares o apontador guardado. Sem a sentinela, pode ocorrer uma leitura fora dos limites. Em cada grupo cujo item_count seja diferente de zero, items tem de apontar para o início de uma sequência de pelo menos item_count elementos do tipo int que possam ser lidos.

O que é opcional é a escrita, não o argumento: passa &found para uma variável do tipo Group *, ou NULL para verificar apenas se o valor existe. A função guarda o grupo através de *out apenas se encontrar o valor e out != NULL. Se devolver false, deixa inalterada a variável de quem chamou, que pode ainda ter um resultado anterior.

No pior caso, o tempo é O(G + I) para G grupos e I elementos locais, com O(h) chamadas simultâneas para uma árvore de altura h. Para estruturas muito profundas, considera uma pilha explícita; num grafo com ciclos, regista os nós visitados. O exemplo usa sintaxe ISO C23; o suporte pode variar consoante a implementação.

Exemplos

#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` é encontrado em `root` antes de serem consultados os subgrupos. Para `42`, a subárvore `left` leva a `deep` antes de `right` ser visitado. A chamada com `NULL` verifica apenas a existência; a pesquisa sem sucesso por `99` deixa `found` a apontar para `deep`.

Lições relacionadas

  • C · Lição 79 · Avançado · Versão: 3

Fontes