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

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] = {};
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
}
queue<int>q;
q.push(0);
vis = 1;
while (!q.empty())
{
int node = q.front();
q.pop();
cout << "Visited node: " << node << endl;
{
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]
y = edges[i]
graph[x].append(y)
graph[y].append(x)
visited, queue = set(), deque()
while queue:
vertex = queue.popleft()
print("Visited " + str(vertex))
for neighbour in graph[vertex]:
if neighbour not in visited:
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] = {};
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
}
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]
y = edges[i]
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. 