# Video for concept and walkthrough

This is 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):# initializationvisited[node] = False for all nodes in graphqueue = empty queue# start from the sourcevisited[source] = Truequeue.push(source) # push to the back of the queue# keep searchingwhile queue is not empty:node = queue.pop() # pop node from front of queuefor 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.

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

## Pseudocode (recursive implementation)

It is easier to implement depth-first search in a recursive way.

# initializationvisited[node] = False for all nodes in graphdefine depth_first_search(node):visited[node] = Truefor 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.

## Pseudocode (iterative implementation)

Depth-first search can has a iterative implementation, 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.

define depth_first_search(source):# initializationvisited[node] = False for all nodes in graphstack = empty stack# start from the sourcestack.push(source) # push to the top of the stack# keep searchingwhile stack is not empty:node = stack.pop() # pop node from top of stackif not visited[node]:visited[node] = Truefor 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.