Breadth-first search in C

An adjacency matrix, a queue of frontier nodes, and a visited array.

#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;
}

How it works

1. The queue makes the traversal breadth-first.
2. Marking on enqueue, not dequeue, avoids duplicates.
3. The order out is the order discovered.

Keywords and builtins used here

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

The run, in numbers

Lines

25

Characters to type

460

Tokens

156

Three-star pace

105 tpm

At the three-star pace of 105 tokens a minute, this run takes about 89 seconds.

Type this snippet

Step 1 of 2 in Graphs, step 15 of 20 in Data structures & algorithms.

← Previous Next →