Back in 2005 Mark Zuckerberg took a “Computer Science” lecture at Harvard.
He started by talking about some of the strategies that Facebook used to improve its performance, one of them being caching.
After talking for a while he asked the audience for any questions. To his surprise there weren’t any technical questions as such. Well anyone will be surprised I guess. After answering a few questions he finally commented “No CS Questions”.
In DFT we pick a vertex to start with. In our example friendship graph we start with Ankur. We visit this and mark it as visited.
Next we explore the adjacent vertices to this vertex, like Reena. But we don’t explore the next adjacent vertex to Ankur i.e. Dikshit, instead we explore further and visit Nidhi, who is connected to Reena. So what we are doing is traversing the depths till we reach a leaf or a node that has been visited. Then we backtrack and start exploring the next adjacent node i.e. Dikshit.
Doesn’t this sound recursive? It is and as you will see our code makes use of recursion to perform DFT.