Back to Course

Data Structures and Algorithms with C++

0% Complete
0/0 Steps
  1. Introduction to Data Structures and Algorithms
    Overview of Data Structures and Algorithms with C++
  2. Importance of Data Structures and Algorithms in Programming with C++
  3. How to Choose the Right Data Structure or Algorithm for a given Problem with C++
  4. Basic C++ Concepts Review
    Variables and Data Types in C++
  5. Control Flow Statements in C++
  6. Classes and Objects in C++
  7. Methods and Constructors in C++
  8. Basic Input and Output in C++
  9. Data Structures
    Arrays in C++
  10. Stacks and Queues in C++
  11. Linked Lists in C++
  12. Hash Tables in C++
  13. Trees in C++
  14. Types of Trees
    Binary Search Trees in C++
  15. Cartesian Trees in C++
  16. B-Trees in C++
  17. Red-Black Trees in C++
  18. Splay Trees in C++
  19. AVL Trees in C++
  20. KD Trees in C++
  21. Min Heap in C++
  22. Max Heap in C++
  23. Trie Trees in C++
  24. Suffix Trees in C++
  25. Sorting Algorithms
    Quicksort in C++
  26. Mergesort in C++
  27. Timsort in C++
  28. Heapsort in C++
  29. Bubble Sort in C++
  30. Insertion Sort in C++
  31. Selection Sort in C++
  32. Tree Sort in C++
  33. Shell Sort in C++
  34. Bucket Sort in C++
  35. Radix Sort in C++
  36. Counting Sort in C++
  37. Cubesort in C++
  38. Searching Algorithms
    Linear Search in C++
  39. Binary Search in C++
  40. Graphing Algorithms
    Breadth First Search (BFS) in C++
  41. Depth First Search (DFS) in C++
  42. Dijkstra’s Algorithm in C++
  43. Algorithm Design Techniques
    Greedy Algorithms in C++
  44. Dynamic Programming in C++
  45. Divide and Conquer in C++
  46. Backtracking in C++
  47. Randomized Algorithms in C++
  48. Conclusion
    Recap of DSA with C++

Participants 486

Show more

Depth First Search (DFS) is an algorithm used to traverse a graph or a tree. It is one of the most popular algorithms used to traverse a graph and is an important algorithm used in data structures and algorithms with C++. This article will cover the basics of Depth First Search, how it works, its time and space complexity, and have code examples of the algorithm implemented in C++. 

Depth First Search (DFS) is a graph traversal algorithm that starts at the root node and explores as far as possible along each branch before backtracking. It is an algorithm for traversing or searching tree or graph data structures. The DFS algorithm traverses a graph in a depth-ward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

DFS Algorithm

The DFS algorithm consists of three main steps: 

  1. Initialize a stack to store the nodes to be visited.
  2. Push the root node onto the stack.
  3. While the stack is not empty:
    1. Pop the node from the stack.
    2. If the node has not been visited, mark it as visited and add all of its adjacent nodes to the stack.
    3. If the node has been visited, move on to the next node.

Time Complexity

The time complexity of the DFS algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. The best case time complexity is O(V) when all nodes are reachable from the source vertex, while the worst case time complexity is O(V * E) when the graph is completely disconnected. 

Space Complexity

The space complexity of the DFS algorithm is O(V), where V is the number of vertices in the graph. This is because the algorithm uses a stack to store the nodes that need to be visited.

Implementing Depth First Search in C++

Now that we have an understanding of what Depth First Search is and how it works, let’s look at how to implement the algorithm in C++. 

Let’s start by defining a Graph class. The Graph class will represent our graph data structure and will contain the following:

  1. A vector of nodes
  2. A function to add an edge between two nodes
  3. A function to print the graph

The following code shows how we can define the Graph class in C++:

class Graph
{
	vector<int> nodes;
	void addEdge(int u, int v);
	void printGraph();
};

Next, we will define a function to add an edge between two nodes in the graph. This function will take two integers as arguments, which represent the two nodes that the edge will connect. The following code shows how this can be done in C++:

void Graph::addEdge(int u, int v)
{
	nodes.push_back(u);
	nodes.push_back(v);
}

Finally, we will define a function to print the graph. This function will take no arguments and will simply print out the list of nodes in the graph. The following code shows how this can be done in C++:

void Graph::printGraph()
{
	for (int i = 0; i < nodes.size(); i++)
		cout << nodes[i] << " ";
	cout << endl;
}

Now that we have defined our Graph class, we can start to implement the DFS algorithm. The following code shows how the DFS algorithm can be implemented in C++:

void dfs(Graph g, int source) 
{ 
    // Create a stack 
    stack<int> stack; 
  
    // Mark all the vertices as not visited 
    bool *visited = new bool[g.nodes.size()]; 
    for (int i = 0; i < g.nodes.size(); i++) 
        visited[i] = false; 
  
    // Push the source node onto the stack 
    stack.push(source); 
  
    while (stack.empty() == false) 
    { 
        // Pop a node from the stack 
        int n = stack.top(); 
        stack.pop(); 
  
        // If the node has not been visited, mark it as visited and add all of its adjacent nodes to the stack 
        if (visited[n] == false) 
        { 
            cout << n << " "; 
            visited[n] = true; 
			
			// Get all adjacent nodes of the popped node n 
			vector<int> adjacent = g.adj[n]; 

			// Iterate through all adjacent nodes 
			for (int i = 0; i < adjacent.size(); i++) 
				if (visited[adjacent[i]] == false) 
					stack.push(adjacent[i]); 
        } 
    } 
}

Conclusion

In this article, we discussed Depth First Search (DFS) and how to implement the algorithm in C++. We started by discussing what DFS is and how it works. We then discussed the time and space complexity of the DFS algorithm. Finally, we looked at how to implement the DFS algorithm in C++.

Exercises

Given a graph, implement the DFS algorithm to traverse the graph.

void dfs(Graph g, int source) 
{ 
    // Create a stack 
    stack<int> stack; 
  
    // Mark all the vertices as not visited 
    bool *visited = new bool[g.nodes.size()]; 
    for (int i = 0; i < g.nodes.size(); i++) 
        visited[i] = false; 
  
    // Push the source node onto the stack 
    stack.push(source); 
  
    while (stack.empty() == false) 
    { 
        // Pop a node from the stack 
        int n = stack.top(); 
        stack.pop(); 
  
        // If the node has not been visited, mark it as visited and add all of its adjacent nodes to the stack 
        if (visited[n] == false) 
        { 
            cout << n << " "; 
            visited[n] = true; 
			
			// Get all adjacent nodes of the popped node n 
			vector<int> adjacent = g.adj[n]; 

			// Iterate through all adjacent nodes 
			for (int i = 0; i < adjacent.size(); i++) 
				if (visited[adjacent[i]] == false) 
					stack.push(adjacent[i]); 
        } 
    } 
}

Given a graph, implement a function to print out the nodes in the graph in DFS order.

void printDFS(Graph g, int source) 
{ 
    // Create a stack 
    stack<int> stack; 
  
    // Mark all the vertices as not visited 
    bool *visited = new bool[g.nodes.size()]; 
    for (int i = 0; i < g.nodes.size(); i++) 
        visited[i] = false; 
  
    // Push the source node onto the stack 
    stack.push(source); 
  
    while (stack.empty() == false) 
    { 
        // Pop a node from the stack 
        int n = stack.top(); 
        stack.pop(); 
  
        // If the node has not been visited, mark it as visited and add all of its adjacent nodes to the stack 
        if (visited[n] == false) 
        { 
            cout << n << " "; 
            visited[n] = true; 
			
			// Get all adjacent nodes of the popped node n 
			vector<int> adjacent = g.adj[n]; 

			// Iterate through all adjacent nodes 
			for (int i = 0; i < adjacent.size(); i++) 
				if (visited[adjacent[i]] == false) 
					stack.push(adjacent[i]); 
        } 
    } 
}

Given a graph and two nodes, implement a function to check if there is a path between the two nodes using the DFS algorithm.

bool isPath(Graph g, int source, int dest) 
{ 
    // Create a stack 
    stack<int> stack; 
  
    // Mark all the vertices as not visited 
    bool *visited = new bool[g.nodes.size()]; 
    for (int i = 0; i < g.nodes.size(); i++) 
        visited[i] = false; 
  
    // Push the source node onto the stack 
    stack.push(source); 
  
    while (stack.empty() == false) 
    { 
        // Pop a node from the stack 
        int n = stack.top(); 
        stack.pop(); 
  
        // If the node has not been visited, mark it as visited and add all of its adjacent nodes to the stack 
        if (visited[n] == false) 
        { 
            visited[n] = true; 
			
			// Check if the popped node is the destination node 
			if (n == dest) 
				return true; 
			
			// Get all adjacent nodes of the popped node n 
			vector<int> adjacent = g.adj[n]; 

			// Iterate through all adjacent nodes 
			for (int i = 0; i < adjacent.size(); i++) 
				if (visited[adjacent[i]] == false) 
					stack.push(adjacent[i]); 
        } 
    } 
	
	// No path exists 
	return false; 
}

Given a graph, implement a function to find all connected components using the DFS algorithm.

vector<vector<int>> connectedComponents(Graph g) 
{ 
	vector<vector<int>> components; 
	
	// Mark all the vertices as not visited 
    bool *visited = new bool[g.nodes.size()]; 
    for (int i = 0; i < g.nodes.size(); i++) 
        visited[i] = false; 
  
    // Iterate through all nodes 
    for (int i = 0; i < g.nodes.size(); i++) 
    { 
		// Create a stack for DFS 
		stack<int> stack; 
		
		// If the node has not been visited, add it to the stack 
        if (visited[i] == false) 
			stack.push(i); 

		// Create a vector to store the connected component 
		vector<int> component; 

		// Iterate through the stack 
		while (stack.empty() == false) 
		{ 
			// Pop a node from the stack 
			int n = stack.top(); 
			stack.pop(); 
	
			// If the node has not been visited, mark it as visited and add all of its adjacent nodes to the stack 
			if (visited[n] == false) 
			{ 
				component.push_back(n); 
				visited[n] = true; 
				
				// Get all adjacent nodes of the popped node n 
				vector<int> adjacent = g.adj[n]; 
	
				// Iterate through all adjacent nodes 
				for (int i = 0; i < adjacent.size(); i++) 
					if (visited[adjacent[i]] == false) 
						stack.push(adjacent[i]); 
			} 
		} 
		
		// Add the connected component to the list of components 
		components.push_back(component); 
    } 
	
	return components; 
}

Given a graph and two nodes, implement a function to find the shortest path between the two nodes using the DFS algorithm.

vector<int> shortestPath(Graph g, int source, int dest) 
{ 
    // Create a stack 
    stack<int> stack; 
	
	// Create a vector to store the shortest path 
	vector<int> path; 
  
    // Mark all the vertices as not visited 
    bool *visited = new bool[g.nodes.size()]; 
    for (int i = 0; i < g.nodes.size(); i++) 
        visited[i] = false; 
  
    // Push the source node onto the stack 
    stack.push(source); 
  
    while (stack.empty() == false) 
    { 
        // Pop a node from the stack 
        int n = stack.top(); 
        stack.pop(); 
  
        // If the node has not been visited, mark it as visited and add all of its adjacent nodes to the stack 
        if (visited[n] == false) 
        { 
            visited[n] = true; 
			
			// Add the node to the path 
			path.push_back(n); 
			
			// Check if the popped node is the destination node 
			if (n == dest) 
				return path; 
			
			// Get all adjacent nodes of the popped node n 
			vector<int> adjacent = g.adj[n]; 

			// Iterate through all adjacent nodes 
			for (int i = 0; i < adjacent.size(); i++) 
				if (visited[adjacent[i]] == false) 
					stack.push(adjacent[i]); 
        } 
    } 
	
	// No path exists 
	return path; 
}