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 queueSince 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 stackRun-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.