Graph Traversals

There are multiple methods of traversing a graph. Two of the most popular traversals are Depth First Search and Breadth First Search.

Depth First Search

Depth-first search is one of the most basic traversal algorithms for a graph data structure. The basic idea of depth-first search is to start from a node usually called the root and explore the graph as far as possible and then eventually backtrack all the way back to the root.

The pseudocode for this algorithm is as follows,

Algorithm DFS(G, V):
    mark V as visited
    for all edges from V to W in G.adjacent(V) do
    if vertex W is not marked visited then do
        DFS(G,W)

This is the recursive implementation of the algorithm. As you can notice, we just start with a node and explore all vertices which are adjacent to the vertex V on which the function was called. The most important part of this algorithm is the visited values. These values tell us if a vertex has already been visited earlier. During the dfs function, we first check if the neighbour has been already visited earlier. If it has been visited, then we don't revisit it. This makes sure that we don't go back and forth on the same edge which will result in an infinite loop. Consider the following animation which shows the calls for the dfs function. The root node is 1 in this case.

The time complexity of this algorithm is O(V<sup>2</sup>) when the graph is implemented as an adjacency matrix. This is because for each node you have to traverse the whole row which will be of length V. Thus V² elements will be accessed which results in the quadratic time complexity.

Although, if we implement this graph in the form of an adjacency list, then the time complexity of DFS reduces to O(V+E). Every vertex will be visited only once which gives us a time of O(V). But for each vertex we'll also iterate through all the neighbours. The sum of the sizes of all the lists in an undirected graph will be 2E which gives us a time complexity for this part of the algorithm as O(2E) ~ O(E). Hence the total time complexity for DFS using adjacency list will be O(V+E). For directed graphs, we'll get O(E) instead of O(2E) which still gives us the same complexity as O(V+E).

Breadth First Search

Breadth First Search is another method of traversing/searching a graph. As you might have noticed, DFS traverses recursively. In BFS, we traverse in the order of a level. We start out with a vertex which is called the root. We first explore all the neighbours and then move onto the next level neighbours. BFS traverses a graph in a level order manner.

The pseudocode for BFS is as follows,

Algorithm BFS(G, V)
    let Q be a queue
    Q.enqueue(V)
    mark V as visited
    while Q is not empty do
        V = Q.dequeue()
        for all neighbours W of V in G do
            if W is not visited then do
                Q.enqueue(W)
                mark W as visited

The following gif shows a standard BFS traversal on the graph.

The time complexity of this algorithm is O(V+E) when the graph is implemented using an adjacency list.