Harsh Mishra

Posted on Aug 3

DFS Graph Traversal using Recursion C++: Story

#cpp #algorithms #programming

🩸 The Curse Beneath the Roots — A Recursive DFS Tale

“The land doesn’t reveal its heart to those who skim its surface.
It answers only to the voice that calls again… and again… and again.”
— Whispers of Oldwood, Book II

🌲 Prologue: The Forest of Forgotten Bonds

There once stood a forest known only in whispers: Oldwood.
It was no ordinary forest. It was alive — and not metaphorically.
Each tree remembered.
Each stone whispered.
Each path twisted not through geography… but through memories.

It was said that anyone who entered Oldwood would lose their way —
not because they didn’t know the road,
but because the forest led them away from it.

Only one kind of traveler could unravel its truth:

The Echo Walkers — beings who carried a voice that could call down into the roots and wait for the answer.

And their weapon? Not steel.
Not spell.
But the recursion of thought itself.

🗺️ The Mark of the Forest

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

Before the journey, the Walker carried with him the Map of Whispers — a scroll of tangled paths — and silence.

🌿 Etching the Forest’s Memory

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

Oldwood was carved by forgotten hands.
Whenever a memory was restored between two points, a path returned.

Each addEdge(u, v) was a fallen memory being reawakened, like two trees whispering once more.

🧠 The Walker’s Mind: A Soul Map

    void dfsUtil(int node, vector<bool> &visited) {
        visited[node] = true;
        cout << node << " ";

And then came the voice.

Not a physical one.
Not something shouted.
But a mental chant — echoing down the passageways of Oldwood.

This was the heart of the Walker:

“I see you, node. I mark you. And I remember you now.”

Each node, once touched, would never be the same.
The forest knew it had been seen.

🌀 Recursion — The Echo That Falls Deeper

        for (int child : adj[node]) {
            if (!visited[child]) {
                dfsUtil(child, visited);
            }
        }
    }

This is what made an Echo Walker different.

He didn’t mark all the trails with sticks.
He didn’t carry flags.

He called… and waited for the reply.

If a child whispered back — untouched, unmarked —
he followed it without fear, trusting that if he kept going… he would reach all.

This recursive whisper was the Walker’s deepest ritual.
Every call led to another, which led to another, which led to another…

Until silence returned —
meaning the path had ended.
Only then did he retreat.

🧭 The Journey Begins

    void dfs(int start) {
        vector<bool> visited(V, false);
        cout << "DFS Traversal: ";
        dfsUtil(start, visited);
        cout << "\n";
    }
};

When the Echo Walker finally chose a gate — start —
he didn’t march in or draw a sword.

He closed his eyes, touched the soil, and whispered:

“I begin.”

His mind flooded with the visited ledger, still empty.
Then — like lightning splitting through centuries — he called the ancient name: dfsUtil(start).

And so began his descent.

🔓 A Fragment from the Past

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.dfs(0);
}

Oldwood took form.

From the root (0), he heard two voices: 1 and 2.
From 1, he reached 3 and 4.
From 2, he journeyed to 5… and finally, 6.

No loops.
No stack.

Just his mind and the forest’s response.

He left behind footprints so subtle that only the traversal itself remembered them:

DFS Traversal: 0 1 3 4 2 5 6

Each number not just a node — but a memory unearthed.

📜 The Truth of Recursion in DFS

dfs(start) — The call to begin, the opening whisper
dfsUtil(node, visited) — The whisper itself, echoing through paths not yet traveled
visited[] — A sacred ward to never ask the same soul twice
Recursive call — The key: you don’t dive with a tool… you fall with trust

🐚 And Why This Will Burn Into You Forever

Other methods demand control.
This one demands surrender.

DFS with a stack says, “I choose how far I go.”

Recursive DFS says,

“Let the depth take me. I will walk until there is nowhere else.”

It’s not linear.
It’s not logical.
It’s spiritual — a depth-first journey into the unknown, where memory and decision become one.

“Those who dive by thought, not sword,
Shall reach the roots where curses sleep.
And awaken not just secrets…
But the land itself.”

DEV Community