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

CKTIS / C

Pesquisa em profundidade (DFS) em C

A pesquisa em profundidade (DFS) explora o ramo seguinte de um grafo antes de regressar aos restantes vizinhos. O exemplo demonstra uma travessia recursiva, a marcação dos vértices visitados e uma ordem de impressão determinística.

Versão: C23; repository compiler flag, production runtime not attested

Sintaxe

void dfs(int v);

A pesquisa em profundidade (depth-first search, DFS) explora o ramo seguinte antes de regressar aos restantes vizinhos. A travessia recursiva (recursive traversal) implementa este padrão através de chamadas à função para os vizinhos não visitados; quando uma chamada regressa, o ciclo anterior é retomado. A DFS, por si só, não determina quando um vértice é processado; este exemplo imprime-o quando é descoberto.

No exemplo, graph[v][u] representa uma aresta dirigida de v para u. A função dfs define visited[v] antes de efetuar mais chamadas, pelo que o ciclo 0 → 1 → 3 → 0 não volta a entrar em 0. A ordem crescente de u produz 0, 1, 3, 2, 4, cada um numa linha própria. Todos os índices fornecidos estão no intervalo 0–N - 1.

A chamada dfs(0) visita apenas os vértices alcançáveis a partir de 0. Para percorrer o grafo inteiro, chame dfs para cada vértice ainda não visitado. Reinicialize visited antes de iniciar novamente uma travessia independente.

Com uma matriz de adjacência, uma travessia completa demora O(V²); uma representação por listas de adjacência permite O(V + E), sendo V e E o número de vértices e de arestas. O vetor de visitados e a pilha de chamadas exigem O(V) de espaço auxiliar. Uma recursão profunda pode esgotar a pilha de chamadas; uma pilha explícita é uma alternativa. O contexto do repositório identifica C23 como opção do compilador, mas não atesta um ambiente de produção.

Exemplos

#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

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes