34 votes 34 votes Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjacency matrix? $\Theta(n)$ $\Theta(n+m)$ $\Theta(n^2)$ $\Theta(m^2)$ Algorithms gatecse-2014-set1 algorithms graph-algorithms normal graph-search + – go_editor asked Sep 26, 2014 • edited Oct 27, 2017 by kenzou go_editor 12.2k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Aspi R Osa commented Jan 12, 2016 reply Follow Share explainaton? 0 votes 0 votes Ahwan commented Jul 20, 2017 reply Follow Share with Adjacency List: O(E+V) Adjacency matrix: O( V^2) By the way in dense graph, E is nearly equal to V sq...so adjacency list will also take O(V^2,V)=O(V^2) 9 votes 9 votes rishi71662data4 commented Nov 12, 2017 reply Follow Share What is dense graph ? Is a graph with maximum edges ? 0 votes 0 votes vishalshrm539 commented Dec 8, 2017 reply Follow Share in dense graph , order of no. of edges = O(|V|)^2 in sparse graph, it is O(|V|) 3 votes 3 votes Please log in or register to add a comment.
Best answer 30 votes 30 votes 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 * 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 $O(n^2)$. Correct Answer: $C$ Regina Phalange answered Apr 6, 2017 • edited Apr 29, 2019 by Naveen Kumar 3 Regina Phalange comment Share Follow See all 2 Comments See all 2 2 Comments reply Ayush Upadhyaya commented Jan 2, 2019 reply Follow Share $O(V)$ calls are made to DFS visit and in DFS visit, examining neighbour of each vertex takes $O(V)$ times so total time $O(V^2)$ 16 votes 16 votes Abhrajyoti00 commented Dec 12, 2022 reply Follow Share Useful : CS161Lecture09.pdf (stanford.edu) 0 votes 0 votes Please log in or register to add a comment.
14 votes 14 votes Ans (C) http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html Keith Kr answered Jan 12, 2015 • edited Oct 27, 2017 by kenzou Keith Kr comment Share Follow See all 2 Comments See all 2 2 Comments reply Mohnish commented Dec 6, 2020 reply Follow Share link not working 0 votes 0 votes abhishek29 commented Oct 12, 2022 reply Follow Share Working link: Graph Searching (archive.org) 0 votes 0 votes Please log in or register to add a comment.
13 votes 13 votes 1. Depth-first search requires O(V + E) time if implemented with adjacency lists 2. Depth-first search requires O(V2) time if implemented with an adjacency matrix Sougatamoy Biswas 1 answered Jan 19, 2016 • edited Jan 6, 2018 by Puja Mishra Sougatamoy Biswas 1 comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V2). varunrajarathnam answered Aug 7, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.