[Verse 1]
Started with a graph and nodes to explore
Stack-based journey, going deep to the core
Mark it visited, push it on the stack
Choose a neighbor, never looking back
Recursive calls or iterative way
DFS gonna find that path today
Go as far as possible before retreat
Every branch explored, algorithm complete
[Chorus]
Deep First Search, stack it up high
Mark visited, don't ask why
Backtrack when you hit the wall
DFS explores it all
Stack, mark, dive, retreat
Make that traversal complete
Deep First Search, that's the key
O of V plus E complexity
[Verse 2]
Pre-order visit when you first arrive
Post-order action keeps the search alive
White nodes unvisited, gray means in progress
Black nodes are finished, no more to process
Three colors coding every single state
DFS timing keeps the order straight
Discovery time when we first explore
Finish time when there's nothing more
[Chorus]
Deep First Search, stack it up high
Mark visited, don't ask why
Backtrack when you hit the wall
DFS explores it all
Stack, mark, dive, retreat
Make that traversal complete
Deep First Search, that's the key
O of V plus E complexity
[Bridge]
Topological sort with DFS power
Strongly connected components every hour
Cycle detection in a directed graph
DFS applications got you covered, that's a fact
Forest of trees when the search is done
Each connected component weighs a ton
[Verse 3]
Start from any vertex, doesn't matter which
Adjacency list or matrix, pick your pitch
LIFO structure, last in first out
That's what stack-based searching is about
Parenthesis theorem keeps the nesting clean
Most elegant traversal you've ever seen
Linear time complexity, can't get better
DFS mastery, you're a go-getter
[Chorus]
Deep First Search, stack it up high
Mark visited, don't ask why
Backtrack when you hit the wall
DFS explores it all
Stack, mark, dive, retreat
Make that traversal complete
Deep First Search, that's the key
O of V plus E complexity
[Outro]
From root to leaf, then back again
DFS journey never ends
Master the depth, control the flow
Graph algorithms, now you know