# Depth First Search – DFS

#### Linux: Introduction to Linux and Its Distributions

Depth first search in short form DFS is a graph traversal algorithm. The time complexity of DFS is O(V+E) where V is the number of vertex and E is the number of edges

## Depth First Search Algorithm

We will maintain a visited list and a stack
The algorithm works as follows

1. We will start this algorithm by putting any nodes at the top of the stack.
2. Take the top node from the stack let’s say it is r. Then add it to the visited list
3. Traverse through the adjacency list of node r. If the adjacent node is not visited, put this node at the top of the stack
4. Repeat 2 and 3 until the stack is empty

## Depth First Search Example

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

Start from node 0. Put 0 at the visited list and put all of it’s adjacent node to the stack.

Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead.

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 completed the Depth First Traversal of the graph.

## DFS Pseudocode (recursive implementation)

The pseudocode of the DFS recursive implementation is given below.

```DFS(G, u)
u.visited = true
if v.visited == false
DFS(G,v)

init() {
For each u ∈ G
u.visited = false
For each u ∈ G
if u.visited==false
DFS(G, u)
}
```

If the graph has more than one connected component then starting from a node will not visit all other nodes. So in the init function, we call dfs for every unvisited node.

## DFS Implementation in Python

```adj=[]
n=int(input()) # number of vertices.
m=int(input()) # number of edges

for i in range(n):

# input edge list.
for i in range(m):
a, b=map(int, input().split())

visited=[]
for i in range(n):
visited.append(0)

def dfs(r):
print(r)
visited[r]=1
if visited[i]==0:
dfs(i)

for i in range(n):
if visited[i]==0:
dfs(i)

```

## DFS Implementation in C++

```#include<bits/stdc++.h>

using namespace std;
vector<int> visited;
void dfs(int r)
{
visited[r]=1;
cout<<r<<endl;
{
if(visited[it]==0)
{
dfs(it);
}
}

}
int main()
{
int n,m;
cin>>n; // n is the number of vertices
cin>>m; // m is the number of edges
adj.resize(n); // n vector for each node

// input edgelist
for(int i=0;i<m;i++)
{
int a, b;
cin>>a>>b;
}
visited.resize(n);

for(int i=0;i<n;i++){
if(visited[i]==0)
{
dfs(i);
}
}

return 0;
}
```