# Depth First Search (DFS)

## Depth First Search (DFS)

Depth First Search is one of the most simple graph algorithms. It traverses the graph by first checking the current node and then moving to one of its sucessors to repeat the process. If the current node has no sucessor to check, we move back to its predecessor and the process continues (by moving to another sucessor). If the solution is found the search stops.

### Implementation (C++14)

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

class Graph{
int v;    // number of vertices

// pointer to a vector containing adjacency lists
public:
Graph(int v);  // Constructor

// function to add an edge to graph

// prints dfs traversal from a given source `s`
void dfs();
void dfs_util(int s, vector < bool> &visited);
};

Graph::Graph(int v){
this -> v = v;
adj = new vector < int >[v];
}

adj[v].push_back(v);  // add u to v's list (remove this statement if the graph is directed!)
}
void Graph::dfs(){
// visited vector - to keep track of nodes visited during DFS
vector < bool > visited(v, false);  // marking all nodes/vertices as not visited
for(int i = 0; i < v; i++)
if(!visited[i])
dfs_util(i, visited);
}
// notice the usage of call-by-reference here!
void Graph::dfs_util(int s, vector < bool > &visited){
// mark the current node/vertex as visited
visited[s] = true;
// output it to the standard output (screen)
cout << s << " ";

// traverse its adjacency list and recursively call dfs_util for all of its neighbours!
// (only if the neighbour has not been visited yet!)
for(vector < int > :: iterator itr = adj[s].begin(); itr != adj[s].end(); itr++)
if(!visited[*itr])
dfs_util(*itr, visited);
}

int main()
{
// create a graph using the Graph class we defined above
Graph g(4);

cout << "Following is the Depth First Traversal of the provided graph"
<< "(starting from vertex 0): ";
g.dfs();
// output would be: 0 1 2 3
return 0;
} ``````

### Evaluation

Space Complexity: O(n)

Worse Case Time Complexity: O(n)
Depth First Search is complete on a finite set of nodes. I works better on shallow trees.

### Implementation of DFS in C++

``````#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct Graph{
int v;
public:
Graph(int vcount);
void deleteEdge(int u,int v);
vector<int> DFS(int s);
void DFSUtil(int s,vector<int> &dfs,vector<bool> &visited);
};
Graph::Graph(int vcount){
this->v = vcount;
for(int i=0;i<vcount;i++)
for(int i=0;i<vcount;i++)
for(int j=0;j<vcount;j++)
}

}

void Graph::deleteEdge(int u,int w){
}

void Graph::DFSUtil(int s, vector<int> &dfs, vector<bool> &visited){
visited[s]=true;
dfs.push_back(s);
for(int i=0;i<this->v;i++){
DFSUtil(i,dfs,visited);
}
}

vector<int> Graph::DFS(int s){
vector<bool> visited(this->v);
vector<int> dfs;
DFSUtil(s,dfs,visited);
return dfs;
}``````