bfs.c

#include <stdio.h>
#include "graphArr.h"

// BFS queue (circular buffer)
int queue[NUM_NODES];
int head = 0;
int tail = 0;

// Visited array and distances
char visited[NUM_NODES];
int distance[NUM_NODES];

// BFS traversal from a starting node
// Returns the sum of all distances (to prevent optimization)
int bfs(int start) {
    // Initialize
    for (int i = 0; i < NUM_NODES; i++) {
        visited[i] = 0;
        distance[i] = -1;
    }
    head = 0;
    tail = 0;

    // Enqueue start node
    queue[tail++] = start;
    visited[start] = 1;
    distance[start] = 0;

    int sum = 0;

    while (head != tail) {
        // Dequeue
        int node = queue[head++];
        if (head >= NUM_NODES) head = 0;  // wrap around

        int dist = distance[node];
        sum += dist;

        // Visit all neighbors
        int edge_start = row_start[node];
        int edge_end = row_start[node + 1];

        for (int e = edge_start; e < edge_end; e++) {
            int neighbor = neighbors[e];
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                distance[neighbor] = dist + 1;
                queue[tail++] = neighbor;
                if (tail >= NUM_NODES) tail = 0;  // wrap around
            }
        }
    }

    return sum;
}

int main(int argc, char *argv[]) {
    // Run BFS from two different starting points
    int total = 0;
    total += bfs(0);
    total += bfs(NUM_NODES / 2);

    if (argc >= 2) {
        printf("bfs_sum:%d, %s\n", total, argv[0]);
    }

    return 0;
}