Search code examples
algorithmtime-complexitydepth-first-searchbreadth-first-searchpseudocode

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

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.

Solution

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

    enter image description here

    Image courtesy - DSA Made Easy by Narasimha karumanchi