In this tutorial, you will learn about **depth-first search algorithms** with examples and pseudocode. Additionally, you will learn how to implement DFS in C, Java, Python, and C++.

In this article, you will learn-

## What is Depth First Search?

The **Depth First Search** **(DFS)** is an algorithm for traversing or searching through tree or graph data structures that uses backtracking. It investigates all the nodes by going ahead if conceivable or uses backtracking.

Note: It can be implemented using a stack.

Depth-first Search or Depth-first traversal is a recursive algorithm for looking through all the vertices of a graph or tree data structure. Traversal implies visiting all the nodes of a graph.

## Depth First Search Algorithm

A standard DFS execution places every vertex of the graph into one of two classes:

- Visited
- Not Visited

The reason for the algorithm is to mark every vertex as visited while evading cycles.

The DFS algorithm functions as follows:

- Start by putting any of the graph’s vertices on top of a stack.
- Take the top item of the stack and add it to the visited list.
- Create a list of that vertex’s adjacent nodes. Add the ones which aren’t in the visited list to the top of the stack.
- Continue to repeating stages 2 and 3 until the stack is vacant.

## Depth First Search Example

Let’s see how the Depth First Search algorithm functions with an example. We use an undirected graph with 5 vertices.

We start from vertex 0, the DFS algorithm begins by placing it in the Visited list and placing all its adjacent vertices in the stack.

Visit the element and put it in the visited list

Then, we visit the element at the top of the stack for example 1, and go to its adjacent nodes. Since 0 has just been visited, we visit 2 instead.

Visit the element at the top of the stack

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.

After we visit the last element 3, it doesn’t have any unvisited adjacent nodes, so we have finished the Depth First Traversal of the graph.

After we visit the last element 3, it doesn’t have any unvisited adjacent nodes, so we have finished the Depth First Traversal of the graph.

## DFS Pseudocode (recursive Implementation)

The pseudocode for DFS appears beneath. In the init() work, notice that we run the DFS work on each node. This is on the grounds that the graph may have two diverse separated parts so to ensure that we cover each vertex, we can likewise run the DFS algorithm on each node.

DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u) }

## DFS Implementation in Python, Java, and C/C++

The code for the Depth First Search Algorithm with an example appears underneath. The code has been rearranged so that we can focus on the algorithm instead of different details.

**Python**

# DFS algorithm in Python # DFS algorithm def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph[start] - visited: dfs(graph, next, visited) return visited graph = {'0': set(['1', '2']), '1': set(['0', '3', '4']), '2': set(['0']), '3': set(['1']), '4': set(['2', '3'])} dfs(graph, '0')

**Java**

// DFS algorithm in Java import java.util.*; class Graph { private LinkedList<Integer> adjLists[]; private boolean visited[]; // Graph creation Graph(int vertices) { adjLists = new LinkedList[vertices]; visited = new boolean[vertices]; for (int i = 0; i < vertices; i++) adjLists[i] = new LinkedList<Integer>(); } // Add edges void addEdge(int src, int dest) { adjLists[src].add(dest); } // DFS algorithm void DFS(int vertex) { visited[vertex] = true; System.out.print(vertex + " "); Iterator<Integer> ite = adjLists[vertex].listIterator(); while (ite.hasNext()) { int adj = ite.next(); if (!visited[adj]) DFS(adj); } } public static void main(String args[]) { Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println("Following is Depth First Traversal"); g.DFS(2); } }

**C**

// DFS algorithm in C #include <stdio.h> #include <stdlib.h> struct node { int vertex; struct node* next; }; struct node* createNode(int v); struct Graph { int numVertices; int* visited; // We need int** to store a two dimensional array. // Similary, we need struct node** to store an array of Linked lists struct node** adjLists; }; // DFS algo void DFS(struct Graph* graph, int vertex) { struct node* adjList = graph->adjLists[vertex]; struct node* temp = adjList; graph->visited[vertex] = 1; printf("Visited %d \n", vertex); while (temp != NULL) { int connectedVertex = temp->vertex; if (graph->visited[connectedVertex] == 0) { DFS(graph, connectedVertex); } temp = temp->next; } } // Create a node struct node* createNode(int v) { struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; } // Create graph struct Graph* createGraph(int vertices) { struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i < vertices; i++) { graph->adjLists[i] = NULL; graph->visited[i] = 0; } return graph; } // Add edge void addEdge(struct Graph* graph, int src, int dest) { // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode; } // Print the graph void printGraph(struct Graph* graph) { int v; for (v = 0; v < graph->numVertices; v++) { struct node* temp = graph->adjLists[v]; printf("\n Adjacency list of vertex %d\n ", v); while (temp) { printf("%d -> ", temp->vertex); temp = temp->next; } printf("\n"); } } int main() { struct Graph* graph = createGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printGraph(graph); DFS(graph, 2); return 0; }

**C++**

// DFS algorithm in C++ #include <iostream> #include <list> using namespace std; class Graph { int numVertices; list<int> *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); }; // Initialize graph Graph::Graph(int vertices) { numVertices = vertices; adjLists = new list<int>[vertices]; visited = new bool[vertices]; } // Add edges void Graph::addEdge(int src, int dest) { adjLists[src].push_front(dest); } // DFS algorithm void Graph::DFS(int vertex) { visited[vertex] = true; list<int> adjList = adjLists[vertex]; cout << vertex << " "; list<int>::iterator i; for (i = adjList.begin(); i != adjList.end(); ++i) if (!visited[*i]) DFS(*i); } int main() { Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.DFS(2); return 0; }

## The complexity of Depth First Search

The time complexity of the DFS algorithm is addressed as O(V + E), where V is the number of hubs and E is the number of edges.

The space complexity of the algorithm is O(V).

## Application of DFS Algorithm

- For finding the path
- To test if the graph is bipartite
- For finding the strongly connected components of a graph
- For detecting cycles in a graph

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.