Búsqueda en anchura en C

Una matriz de adyacencia, una cola de nodos frontera y un arreglo de visitados.

#define MAX_NODES 8

int bfs(const int graph[MAX_NODES][MAX_NODES], int nodes, int start,
        int *order) {
    int visited[MAX_NODES] = {0};
    int queue[MAX_NODES];
    int head = 0;
    int tail = 0;
    int seen = 0;

    queue[tail++] = start;
    visited[start] = 1;

    while (head < tail) {
        int node = queue[head++];
        order[seen++] = node;
        for (int next = 0; next < nodes; next++) {
            if (graph[node][next] && !visited[next]) {
                visited[next] = 1;
                queue[tail++] = next;
            }
        }
    }
    return seen;
}

Cómo funciona

1. La cola es lo que hace el recorrido en anchura.
2. Marcar al encolar, no al desencolar, evita duplicados.
3. El orden de salida es el orden de descubrimiento.

Palabras clave y builtins usados aquí

• const
• for
• if
• int
• return
• while

El intento, en números

Líneas

25

Caracteres a escribir

460

Tokens

156

Ritmo de tres estrellas

105 tpm

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

Escribe este fragmento

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

← Anterior Siguiente →