0 votes 0 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 of $G$, when $G$ is represented using adjacency matrix? $O(n)$ $O(m+n)$ $O(n^2)$ $O(mn)$ Algorithms nielit2017july-scientistb-cs algorithms graph-algorithms + – admin asked Mar 30, 2020 • retagged Oct 20, 2020 by Krithiga2101 admin 1.5k views answer comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Apr 3, 2020 reply Follow Share previous year https://gateoverflow.in/1771/gate2014-1-11 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Option C Let G be a graph with n vertices and m edges. the tightest upper bound on the running time of Depth First Search of G, when G is represented as an adjacency matrix=$O(n^{2})$ when G is represented as an adjacency list=$O(n+m)$ Mohit Kumar 6 answered May 31, 2020 Mohit Kumar 6 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes option c adjacency matrix O(N^2) lovegate answered Mar 10, 2021 lovegate comment Share Follow See all 0 reply Please log in or register to add a comment.