Depth first search code in C++

Anyone please help me by giving any link for coding DFS. I can’t understand the implimant of DFS.
Also please give some nice notes for DFS (as I’m a novice)
:slight_smile:

This article has a section on DFS which could help http://acm.uva.es/problemset/Art_of_Programming_Contest_SE_for_uva.pdf

If that does not work, here’s TopCoder’s tutorial on graphs which includes DFS

Depth-first Search is an easy algorithm to code up when you get the hang of it (as long as you know recursion).

To show you how DFS works, I’ll be using a binary tree. However, DFS can work with any tree.

In DFS, the computer is traversing a tree and uses a stack. It starts at the root node (the uppermost node), pushes that node into the stack, and then goes down to the left child of the parent node. It continues this process until it gets to the bottom of the tree, and at that point, the computer then pops off of the stack (in other words, goes back up the tree) until it gets back to a node with a right child. If it gets to a node with a right child, it repeats the process of pushing the node into the stack and going down starting with this node and going to the right.

It’s easy to understand DFS if you look at it pictorially. The first link I gave has a picture of a tree undergoing the DFS algorithm. Look at that to get a theoretical understanding of it before looking further in this post for the implementation.

Ah, I see you have gained your theoretical knowledge of DFS, no?
Now let’s look at the implementation of it.

Again, I will be using a binary tree for simplicity. However, you can use any tree.
Additionally, here’s the code in Java, although it is simple enough to translate into C++

The root node of a DFS would be the initial call of the DFS algorithm. This is likely to be in your main input stream.

public static void main( String[] args ) {
    dfs(); // Starting DFS at root node.
}

Now in the DFS algorithm, you have two options:

  1. Go down the left child
  2. Go down the right child

So, in the implementation, you would type both to make sure that the computer does both when needed.

void dfs() {
    dfs(); // to the right child.
    dfs(); // to the left child.
}

Typically, the DFS algorithm would have parameters. But, this is the basic idea.

Now how do we use this in a problem?

Suppose the problem give us a 2D array and we have to traverse that only by going right or down to do something. This is a classic problem that appears in a lot of places, and it is a clear DFS.

If you draw out a tree on paper (which I highly recommend doing each time you do a DFS) you would notice that it is a binary tree. The root node would be the top-left node (simply because the problem asks us to start there) and each node has two nodes, the cell below it and the cell to the right of it.

Now to implement it, our DFS would actually have parameters.
In this DFS, we would have 2 parameters. One for the row we are referencing in the 2D array, and one for the column.

The main input stream would, thus, look like this.

public static void main( String[] args ) {
    dfs( 0, 0 ); // Call to start the DFS at the root node, or top-left cell of the matrix.
}

And the DFS method would look like this:

void dfs( int row, int col ) {

     // Do whatever you were meant to do to the node because of the problem.
     dfs( row + 1, col ); // To the cell in the bottom.
     dfs( row, col + 1 ); // To the cell to the right.
}

I might not have explained this well, but DFS can take a while to understand. I recommend the two sites I’ve given earlier to get a good understanding of DFS.

1 Like

if u want to implement dfs,bfs or any graph algo in c++,then u shuld learn STL(standard template library)…graph algorithms are very complex such that if u start to code them from scratch than ,it becomes very tedious-to implement and to debug…

here is the code for implementation of dfs using STL
#include
#include

using namespace std;

// Graph class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
list *adj; // Pointer to an array containing adjacency lists
void DFSUtil(int v, bool visited[]); // A function used by DFS
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void DFS(int v); // DFS traversal of the vertices reachable from v
};

Graph::Graph(int V)
{
this->V = V;
adj = new list[V];
}

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
    if(!visited[*i])
        DFSUtil(*i, visited);

}

// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()
void Graph::DFS(int v)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper function to print DFS traversal
DFSUtil(v, visited);

}

int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

cout << "Following is Depth First Traversal (starting from vertex 2) \n";
g.DFS(2);

return 0;

}

hope u find it easier this time:))