Depth First Search(DFS)

• DFS is also a type graph traversal algorithm similar to the BFS ,means if we want to visit on every node/vertices through their connected edges.
• DFS is the complement of Depth First Search(DFS).
• DFS use a Stack Data Structure.
• DFS explore the all the vertices depth to depth.
• DFS continues to go deeper.

Procedure

Initialize an Graph G(V,E).and create an empty Stack.Start from any Vertex(Node). Now Apply Below rules :

Rule-1 : Check selected Node is already visited or not. if node id already visited then directly go to the Rule-3.
Rule-2 : Marks selected Node as visited Node, and insert their neighbor into Stack.
Stack must be unique ,means if a node is already inserted then there is no need to insert again.
Rule-3 : Pick one Node element from the Stack by applying delete operation on Stack.
Rule-4 : Repeat Rule-1,Rule-2 and Rule-3 until Stack is empty.

Explanation of DFS by Example

Below is the Graph G(V,E). we will Start from Node A. and initialized one queue Q which is empty :

• Green Color : Visited Node
• Blue Color : Neighbor of Selected Node from the Stack
• Yellow Color : Selected Node from the Stack.

---

---

---

---

---

---

---

Animation of DFS

Code Implementation of DFS

#include<bits/stdc++.h> 
using namespace std; 

class CreateGraph 
{ 
	int V; // Number  of vertices 
	list<int> *adj; // Pointer to an List containing adjacency lists 
	void DFSTempMethod(int v, bool visited[]); // A Menthod used by DFS temporarely 
public: 
	CreateGraph(int V); // Constructor 
	void EdgeAddition(int v, int w); // Method of additon an edge to graph 
	void DFSAlgorithms(); //Call for DFS Algorithm  
}; 

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

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

void CreateGraph::DFSTempMethod(int v, bool visited[]) 
{ 
	// Marked the selected node as visited.
	visited[v] = true; 
	cout << v << " "; 

	list<int>::iterator adjVer; 
	for(adjVer = adj[v].begin(); adjVer != adj[v].end(); ++adjVer) 
		if(!visited[*adjVer]) 
			DFSTempMethod(*adjVer, visited); 
} 

// The Method for  DFS traversal.
void CreateGraph::DFSAlgorithms() 
{ 
	// Mark all the vertices which are not visited 
	bool *visited = new bool[V]; 
	for (int i = 0; i < V; i++) 
		visited[i] = false; 


	for (int i = 0; i < V; i++) 
		if (visited[i] == false) 
			DFSTempMethod(i, visited); 
} 

int main() 
{ 
	// Create a graph.
	CreateGraph NumberOfNode(5);  //Number of Node is 4
	NumberOfNode.EdgeAddition(0, 1);  //Node-0 is connected to Node-1
	NumberOfNode.EdgeAddition(0, 2); //Node-0 is connected to Node-2
	NumberOfNode.EdgeAddition(1, 2); //Node-1 is connected to Node-2
	NumberOfNode.EdgeAddition(1, 3); //Node-1 is connected to Node-3
	NumberOfNode.EdgeAddition(2, 0); //Node-2 is connected to Node-0
	NumberOfNode.EdgeAddition(2, 1); //Node-2 is connected to Node-1
	NumberOfNode.EdgeAddition(3, 1); //Node-3 is connected to Node-1
	NumberOfNode.EdgeAddition(3, 4); //Node-3 is connected to Node-4
	NumberOfNode.EdgeAddition(4, 3); //Node-4 is connected to Node-3 

	cout << "Sequence of traversal of DFS : "<<endl;
	NumberOfNode.DFSAlgorithms(); 

	return 0; 
} 

Time & Space Complexity

Complexity of DFS is depend upon the representation of Graph,means how a graph is implemented. For Example :

• if graph is represented by Adjacency List then complexity will be different.
• if graph is represented by Adjacency matrix ,in this case complexity will be different.

• Time Complexity in the case of Adjacency List will be O(|E|+|V|),
  where E=Number of Edges. V=Number of Vertices/Nodes, and
  Order of O(|E|) can be in range O(1) to O(V^{2})
• Time Complexity in the case of Adjacency Matrix will be O(V^{2}),
• where V=Number of Vertices/Nodes
• Worst Case Space Complexity is O(|V|)

Application of DFS

• Used in Topological sorting.
• Use to Find articulation points (cut vertices) of the graph.
• Use to Find strongly connected components.
• Use to Find connected components
• Solving puzzles such as mazes.
• Generation of words in order to plot the limit of a graph. etc