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.