Harsh Mishra

Posted on Aug 3

BFS Graph Traversal C++: Story

#algorithms #programming #cpp

🌊 THE BREATH OF THE CITY — A Tale of BFS Traversal

"The city doesn’t speak all at once.
It breathes — one breath, one ripple, one step at a time."
— From “The Heart of Every Graph”, by Sora of the Gates

🌆 Prologue: The City Sleeps in Silence

Once, in the land of Netra, there stood a city like no other.

Its walls were built not in stone, but in connections —
streets and alleys, winding webs between neighborhoods.

Each corner, each plaza, each shadowed gate was a node.
Some touched many others; some were isolated, forgotten.

But something happened.

One night, the city's pulse stopped.

No footsteps. No laughter. No word from its distant corners.

The Watchers of Netra declared:

“We must awaken it.
We must explore every path, every street —
not in chaos, but in order, one breath at a time.”

And thus began the Breath of the City, the ancient ritual now known as Breadth-First Search (BFS).

🔧 The Tools of the Sentinel

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

The Watchers packed their essentials:

A map: connections between places.
A horn: to call neighbors when needed.
A memory scroll: to remember who had already been seen.

Their traversal was not random. It was systematic —
like a wave rippling out from the center of a pond.

📜 The Scroll of Echoing Steps

class Graph {
    int V;
    vector<vector<int>> adj;

public:
    Graph(int V) : V(V) {
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

The Graph was not just a structure —
it was the city itself.

With addEdge(u, v), the Watchers carved a passage between u and v.

Every alley was bi-directional, every bond mutual.

These paths were not yet traveled — only potential, like veins before blood flows.

🌬️ The Ritual of Awakening — BFS Begins

    void bfs(int start) {
        vector<bool> visited(V, false);
        queue<int> q;

        visited[start] = true;
        q.push(start);

        cout << "BFS Traversal: ";

The Watchers gathered at gate start.

They marked it visited in their scroll — they had stood there, awakened it.

Then, they called out through the gate — the call echoed down its passages.

This was the first breath: the starting node placed into the queue —
a sacred vessel that always calls the oldest unvisited corner first.

The traversal began.

🌊 The Wave of the City Moves

        while (!q.empty()) {
            int u = q.front(); q.pop();
            cout << u << " ";

The city answered.

They stepped into the gate u that had waited longest.

They recorded it in the Great Song (cout << u) — the traversal echo.

Each step was remembered, each breath heard.

The breath had begun — and now, it spread.

🗣️ Calling All Neighbors

            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        cout << "\n";
    }
};

From every awakened street, they looked around:

“Who among you still sleeps?”

For each unseen neighbor v, they:

Marked them as visited — to prevent waking them twice.
Added them to the queue — to be awakened in their rightful order.

No leaps. No chaos.

The breath of the city must touch all corners level by level,
neighbor by neighbor, like sunlight rising over rooftops.

🌇 The Watcher’s Walk — An Example

int main() {
    Graph g(7);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(5, 6);

    g.bfs(0);
}

In the city of 7 districts,
the Watchers lit the first torch at district 0.

From there:

They reached 1 and 2
Then 3, 4, and 5
And finally 6

Each breath touched the next closest layer,
and the city began to stir — one neighborhood at a time.

BFS Traversal: 0 1 2 3 4 5 6

A new day had dawned.

🧠 The Wisdom in the Walk

queue<int> q — the sacred procession; who’s next to awaken
visited[] — the mark of breath, to avoid chaos
adj[] — the blueprint of the city's potential
bfs(start) — the breath itself, rippling outward from one spark

Unlike depth-first wanderers who dive into alleys and may get lost,
BFS watches every level, every ripple — calm, controlled, complete.

“Let no corner remain untouched.
Let every whisper carry forward.
Let the city know itself — not all at once,
but with breath, and memory, and time.”

Thus the city of Netra awoke once again —
with the ancient art of BFS,
and the memory of the Watchers who walked not to conquer,
but to listen.

DEV Community