# Breadth-first search and Depth-first search

December 21, 2016

# Video for concept and walkthrough

First, let’s watch a slow-paced easy-to-follow walkthrough of the breadth-first search and depth-first search algorithms.

# Breadth-first search

Breath-first search explores a graph from a source vertex in a way such that all nodes at a distance of 1 are encountered first, then all nodes at a distance of 2, then all nodes at a distance of 3 and so on.

## Pseudocode

```
define breadth_first_search(source):
# initialization
visited[node] = False for all nodes in graph
queue = empty queue
# start from the source
visited[source] = True
queue.push(source) # push to the back of the queue
# keep searching
while queue is not empty:
node = queue.pop() # pop node from front of queue
for each neighbor of node:
if not visited[neighbor]:
queue.push(neighbor) # push to the back of the queue
```

Since we use a queue for nodes, the nodes that gets *discovered first*, also gets *expanded first*. That is, *breadth-first* search. The video above includes a detailed example and walkthrough.

## Code Implementation

The following is the implementation of bfs in cpp.

```
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
bool vis[N] = {};
vector<int>adj_list[N];
int main()
{
// Number of nodes and edges
int n = 6, m = 5;
/*
We will be adding the
following 5 edges.
(0,1), (0,2), (0,3),
(2,4), (4,1)
*/
pair<int, int> edges[] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {4, 1}};
for (int i = 0; i < m; i++)
{
int x = edges[i].first;
int y = edges[i].second;
// As graph is undirected
adj_list[x].push_back(y);
adj_list[y].push_back(x);
}
queue<int>q;
q.push(0);
vis[0] = 1;
while (!q.empty())
{
int node = q.front();
q.pop();
cout << "Visited node: " << node << endl;
for (auto i:adj_list[node])
{
if (!vis[i])
{
q.push(i);
vis[i] = 1;
}
}
}
return 0;
}
```

The following is the implementation of BFS in python:

```
from collections import defaultdict, deque
N = 100
graph = defaultdict(list)
# adding the following edges
edges = [(0, 1), (0, 2), (0, 3), (2, 4), (4, 1)]
for i in range (0, len(edges)):
x = edges[i][0]
y = edges[i][1]
graph[x].append(y)
graph[y].append(x)
visited, queue = set(), deque([0])
visited.add(0)
while queue:
vertex = queue.popleft()
print("Visited " + str(vertex))
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
```

# Depth-first search

Depth-first search explores a graph from a source vertex. It explores all the nodes it can from the 1st neighbor before moving on to the next neighbor.

## Recursive Approach

It is easier to implement depth-first search in a recursive way. The pseudo code is as follows.

```
# initialization
visited[node] = False for all nodes in graph
define depth_first_search(node):
visited[node] = True
for each neighbor of node:
if not visited[neighbor]:
depth_first_search(neighbor)
```

We *expand* a node as soon as we *discover* it. By the time we explore the next neighbor, all nodes that can be explored from the current neighbor have already been explored. That is, *depth-first* search. The video above includes a detailed example and walkthrough.

## Code Implementation

The following is the recursive implementation of dfs in cpp.

```
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
bool vis[N] = {};
vector<int>adj_list[N];
void dfs(int node)
{
vis[node] = 1;
cout << "Reached node: " << node << endl;
for (auto i: adj_list[node])
{
if (!vis[i])
dfs(i);
}
}
int main()
{
// Number of nodes and edges
int n = 6, m = 5;
/*
We will be adding the
following 5 edges.
(0,1), (0,2), (0,3),
(2,4), (4,1)
*/
pair<int, int> edges[] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {4, 1}};
for (int i = 0; i < m; i++)
{
int x = edges[i].first;
int y = edges[i].second;
// As graph is undirected
adj_list[x].push_back(y);
adj_list[y].push_back(x);
}
dfs(0);
return 0;
}
```

The following is the code implementation of dfs in python:

```
from collections import defaultdict
graph = defaultdict(list)
visited = []
def dfs(node):
print("Visited: " + str(node))
visited.append(node)
for n in graph[node]:
if n not in visited:
dfs(n)
# adding the following edges
edges = [(0, 1), (0, 2), (0, 3), (2, 4), (4, 1)]
for i in range (0, len(edges)):
x = edges[i][0]
y = edges[i][1]
graph[x].append(y)
graph[y].append(x)
dfs(0)
```

## Iterative Approach

Depth-first search can have a iterative implementation as well, but we have to be more careful about when we mark a node as visited and when we check whether a node has been visited. The following is the pseudo code for the iterative approach.

```
define depth_first_search(source):
# initialization
visited[node] = False for all nodes in graph
stack = empty stack
# start from the source
stack.push(source) # push to the top of the stack
# keep searching
while stack is not empty:
node = stack.pop() # pop node from top of stack
if not visited[node]:
visited[node] = True
for each neighbor of node:
stack.push(neighbor) # push to the top of the stack
```

# Run-time analysis

For a graph with $n$ nodes and $m$ edges, both depth-first search and breadth-first search have a run-time of $O(m)$. In both the algorithms, we explore each node exactly once, and hence we look at each edge exactly once.

# Further reading

See the replies to this discussion for **bonus videos**. The tutorials on IARCS Online Study material for breadth-first search and depth-first search are very comprehensive. They include a text tutorials (if you prefer reading over videos), pseudocode and also longer videos (20 minute each).

# Next steps

In the upcoming tutorials, we’ll practice implementing breadth-first search and depth-first search.