Back to Course

0% Complete
0/0 Steps

Lesson 41 of 48
In Progress

Depth First Search (DFS) in C++

Yasin Cakal

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 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

// Iterate through all adjacent nodes
for (int i = 0; i < adjacent.size(); 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

// Iterate through all adjacent nodes
for (int i = 0; i < adjacent.size(); 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

// Iterate through all adjacent nodes
for (int i = 0; i < adjacent.size(); 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

// Iterate through all adjacent nodes
for (int i = 0; i < adjacent.size(); 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

// Iterate through all adjacent nodes
for (int i = 0; i < adjacent.size(); 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
}