Intro to Graph Algorithms — BFS & DFS

3 min readMay 29, 2020

Originally published at https://shawnlyu.com on May 29, 2020.

Graphs are a pervasive data structure in computer science, and algorithms for working with them are fundamental to the field.
Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009.

Given a graph defined as G=(V,E) which is a set of vertices and edges, we’d be curious about how to represent it and how to search it systematically so as to visit the vertices following the edges. This blog will briefly introduce two ways of representations of a graph, and then will dive deep into two graph search algorithms: Breadth-First-Search (BFS) and Depth-First-Search (DFS).

How to Represent a Graph

The two most common ways of representing a graph are:

(1) Adjacent Matrix
(2) Adjacent List

To construct an adjacent matrix, we initialize a 2D array by the size of |V|² and set matrix[i][j]=True if the vertex i and j are connected. With this matrix, we will be able to find whether two nodes are connected efficiently. However, it could be wasteful on space when the graph is sparse, i.e., |E| is far smaller than |V| and most of the values in the matrix would be False.

Another way is to construct an array of lists, where each list contains vertices that are connected to that node. Though it might take longer to determine whether two nodes are connected, it saves a lot of space, especially for large sparse graphs.

How to Search a Graph

Breadth-First-Search (BFS)

BFS is a graph searching algorithm such that, referring to Introduction to Algorithms, ‘Given a graph G=(V,E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to discover every vertex that is reachable from s’. Or to put it another way, BFS would visit every node at the distance k (from the source) before moving on to the nodes at the distance (from the source) k+1. With that being said, BFS could also generate the shortest paths from the source vertex to others. The pseudocode for BFS is as following:

queue = [root]
while queue:
    node = queue.dequeue()
    # some operations on node happen here
    # and then:
    for nei in neighbour(node):
        queue.append(nei)

Time complexity: O(|V|+|E|).
Visiting each node takes O(|V|) and searching through each edge takes O(|E|).

Depth-First-Search (DFS)

Let’s take a look at the definition in the Introduction to Algorithms: ‘In depth-first search, edges are explored out of the most recently discovered vertex v that still has unexplored edges leaving it. When all of v’s edges have been explored, the search “backtracks” to explore edges leaving the vertex from which v was discovered.’. As you can imagine, instead of exploring level by level in BFS, it tries to go as deep as possible, before it reaches the end and return to the previous level.

def helper(node=root):
    if node is None:
        return
    # some operations on node happen here
    # and then:
    for nei in neighbour(node):
        helper(nei)

Time complexity: O(|V|+|E|)

Practices

Leetcode problems are available here: