Depth first search (DFS) vs breadth first search (BFS) pseudocode and complexity

Question

I have to develop pseudocode for an algorithm that computes the number of connected components in a graph G = (V, E) given vertices V and edges E.

I know that I can use either depth-first search or breadth-first search to calculate the number of connected components.

However, I want to use the most efficient algorithm to solve this problem, but I am unsure of the complexity of each algorithm.

Below is an attempt at writing DFS in pseudocode form.

function DFS((V,E))
     mark each node in V with 0
     count ← 0
     for each vertex in V do
          if vertex is marked then
               DFSExplore(vertex)

function DFSExplore(vertex)
     count ← count + 1
     mark vertex with count
     for each edge (vertex, neighbour) do
          if neighbour is marked with 0 then
               DFSExplore(neighbour)

Below is an attempt at writing BFS in pseudocode form.

function BFS((V, E))
     mark each node in V with 0
     count ← 0, init(queue)     #create empty queue 
     for each vertex in V do
          if vertex is marked 0 then
               count ← count + 1
               mark vertex with count
               inject(queue, vertex)             #queue containing just vertex
               while queue is non-empty do
                    u ← eject(queue)                          #dequeues u
                    for each edge (u, w) adjacent to u do
                         if w is marked with 0 then
                              count ← count + 1
                              mark w with count
                              inject(queue, w)     #enqueues w

My lecturer said that BFS has the same complexity as DFS.

However, when I searched up the complexity of depth-first search it was O(V^2), while the complexity of breadth-first search is O(V + E) when adjacency list is used and O(V^2) when adjacency matrix is used.

I want to know how to calculate the complexity of DFS / BFS and I want to know how I can adapt the pseudocode to solve the problem.

A graph with V vertices can have as many as V*(V-1)/2 edges. So there's no difference between O(V + E) and O(V^2) unless the problem statement puts a smaller upper bound on E. — user3386109
Which reference told you that DFS's time complexity is O(V^2)? — kaya3
Your lecturer is correct. In the DFS code you have for each edge (vertex, neighbour) do. And in the BFS code you have for each edge (u, w) adjacent to u do. Those two lines can be implemented either with adjacency lists, or with an adjacency matrix. If implemented with adjacency lists, both algorithms can be said to run in O(V + E) time. If implemented with an adjacency matrix, both algorithms can be said to run in O(V^2) time. But that's a distinction without a difference, since E can be O(V^2), in which case O(V + E) is O(V + V^2) which is just O(V^2). — user3386109

Saumya Agnihotri Saumya Agnihotri · Accepted Answer · 2021-05-14T08:05:33

Time complexity for both DFS & BFS is same i.e O(V+E) if you're using adjacency list. So if you ask, which one is better then it completely depends on the type of problem you are going to solve. Let's say you want to solve a problem where you have your goal near the starting vertex then BFS would be a better choice. Plus, if you consider memory then DFS is a better option because there is no need of storing child pointers.

Image courtesy - DSA Made Easy by Narasimha karumanchi

Depth first search (DFS) vs breadth first search (BFS) pseudocode and complexity

1 Answers