I remember the first time I tried to write a search algorithm for a social network map. I wanted to find the shortest path between two people—the classic "six degrees of separation" problem. My first instinct was to use recursion. I thought, "I'll just visit a friend, then their friend, then their friend's friend."

The problem? I ended up diving deep into one single branch of the network, potentially traveling halfway across the globe in my data structure, only to realize the person I was looking for was actually a direct friend of the starting person. I had accidentally written a Depth-First Search (DFS), which is great for exploring a maze, but terrible for finding the shortest path. To find the closest connection, I needed to explore in concentric circles.

The "Layer" Problem

Let's look at a small graph. Imagine we have four people: 0 (Alice), 1 (Bob), 2 (Charlie), and 3 (Diana). Alice is friends with Bob and Charlie. Bob is friends with Diana. Charlie is also friends with Diana. If I start at Alice and want to find Diana, I want to check everyone at distance 1 first, then everyone at distance 2.

# Simple adjacency matrix for our network
int graph[4][4] = {
    {0, 1, 1, 0}, // Alice: friends with Bob, Charlie
    {1, 0, 0, 1}, // Bob: friends with Alice, Diana
    {1, 0, 0, 1}, // Charlie: friends with Alice, Diana
    {0, 1, 1, 0}  // Diana: friends with Bob, Charlie
};

If I use recursion, I might go Alice $\rightarrow$ Bob $\rightarrow$ Diana. That works, but in a massive graph, I might go Alice $\rightarrow$ Bob $\rightarrow$ ... $\rightarrow$ someone in Tokyo $\rightarrow$ ... $\rightarrow$ Diana, without ever realizing Charlie was right there next to Alice. I need a way to say, "Hold on, finish checking all my immediate friends before you move on to their friends."

Managing the Waiting Room

Since C doesn't give us a built-in Queue, I have to build one. Think of a queue as a waiting room. When I visit a person, I don't immediately jump to their friends; instead, I put all their friends in the waiting room. I only process the next person once everyone who arrived before them has been handled.

I'll start with a simple array-based queue. It's not the most memory-efficient for huge graphs, but for our exploration, it's perfect.

int queue[100];
int front = 0, rear = 0;

void enqueue(int v) {
    queue[rear++] = v;
}

int dequeue() {
    return queue[front++];
}

int isEmpty() {
    return front == rear;
}

Now, here is where I hit my first snag during my early attempts: cycles. If Alice is friends with Bob, and Bob is friends with Alice, my code would just bounce between them forever. I need a visited array to keep track of who has already been "processed."

Putting the Pieces Together

Now I can implement the Breadth-First Search. The logic is: mark the start as visited, put it in the queue, and then loop until the queue is empty. Inside that loop, I pull someone out, look at all their neighbors, and if a neighbor hasn't been visited, I mark them and put them in the queue.

void bfs(int startNode) {
    int visited[4] = {0, 0, 0, 0}; // Initialize all to not visited
    
    visited[startNode] = 1;
    enqueue(startNode);
    
    printf("Traversal order: ");
    
    while (!isEmpty()) {
        int current = dequeue();
        printf("%d ", current);
        
        for (int i = 0; i < 4; i++) {
            // If there's an edge AND we haven't been there yet
            if (graph[current][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(i);
            }
        }
    }
    printf("\n");
}

If I run this starting at node 0 (Alice), the output is 0 1 2 3. Notice how it hits Bob (1) and Charlie (2) before it ever reaches Diana (3). It effectively maps the graph in "waves."

Refining the Logic

You might be wondering: "Why mark it as visited before putting it in the queue, rather than after taking it out?" I tried it both ways. If you mark it after dequeue, you might end up adding the same node to the queue multiple times if it's a neighbor to several people currently being processed. That's a waste of memory and can lead to redundant work. Always mark the node the moment you "discover" it.

📋 Practical Task

Exercise: Calculating Degrees of Separation

Modify the BFS implementation provided in the lesson to not only traverse the graph but to calculate the distance (the number of hops) from the starting node to every other node in the graph.

Requirements:

• Create an integer array int distance[4].
• Initialize the starting node's distance to 0 and all others to -1.
• When you discover a new neighbor and enqueue it, set its distance as distance[current] + 1.
• Print the final distance of each node from the start node (e.g., "Node 3 is 2 hops away from Node 0").