Breadth-first search and Depth-first search[ Edit ]

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):

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

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.

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

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):

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