Bound the graph

Computer Science Level 3

Let $G$ be a graph of $n$ vertices and $m$ edges. If a depth first search is performed on $G$ what is the tightest upper bound of the running time?

Details and Assumptions

The graph is represented in adjacency matrix.

O(n)

O(n+m)

O(n^{2})

O(nm)

1 solution

Tom Engelsman
Oct 17, 2020

A Depth-First Search of a graph takes $O(m+n)$ time when the graph is represented using adjacency list.

In adjacency matrix representation, graph is represented as an $n \times n$ matrix. To do DFS, for every vertex, we traverse the row corresponding to that vertex to find all adjacent vertices (in adjacency list representation we traverse only the adjacent vertices of the vertex). Therefore time complexity becomes $\boxed{O(n^2)}.$

Bound the graph

1 solution

0 pending reports