Búsqueda en profundidad en C

El mismo grafo, un recorrido recursivo y otro orden de visita.

#define MAX_NODES 8

static void visit(const int graph[MAX_NODES][MAX_NODES], int nodes, int node,
                  int *visited, int *order, int *seen) {
    visited[node] = 1;
    order[(*seen)++] = node;

    for (int next = 0; next < nodes; next++) {
        if (graph[node][next] && !visited[next]) {
            visit(graph, nodes, next, visited, order, seen);
        }
    }
}

int dfs(const int graph[MAX_NODES][MAX_NODES], int nodes, int start,
        int *order) {
    int visited[MAX_NODES] = {0};
    int seen = 0;
    visit(graph, nodes, start, visited, order, &seen);
    return seen;
}

Cómo funciona

1. La recursión reemplaza la cola explícita con la pila de llamadas.
2. El arreglo de visitados es lo que detiene los ciclos.
3. Recolectar en postorden da un orden topológico.

Palabras clave y builtins usados aquí

• const
• for
• if
• int
• return
• static
• void

El intento, en números

Líneas

21

Caracteres a escribir

517

Tokens

165

Ritmo de tres estrellas

105 tpm

Al ritmo de tres estrellas de 105 tokens por minuto, este intento toma unos 94 segundos.

Escribe este fragmento

Paso 2 de 2 en Grafos; paso 16 de 20 en Estructuras de datos y algoritmos.

← Anterior Siguiente →