Max DFS running time for a graph that is an adjacency matrix and storing a graph
ID: 3914014 • Letter: M
Question
Max DFS running time for a graph that is an adjacency matrix and storing a graph question. explain reasoning.
11. Let G(V, E) be a graph. What is the running time of DFS when the graph is representing using adjacency matrix? What is the running time if the graph is represent as an adjacency list? Assume as usual that n=lvl and m =IEI. 12. Let G(V, E) be a graph. What space (memory) needed to store this graph if it is actually a tree and we are using adjacency matrix? Repeat this question by now assume we are using adjacency list?Explanation / Answer
Q11) For the graph if represented using adjacency matrix, Running Time = O(N2)
Reason:- If your graph is implemented as an adjacency matrix (a V x V array), then, for each node, you have to traverse an entire row of length V in the matrix to discover all its outgoing edges. Please note that each row in an adjacency matrix corresponds to a node in the graph, and the said row stores information about edges stemming from the node. So, the complexity of DFS is O(|V| * |V|) = O(N^2).
For the graph if represented using adjacency list, Running Time = O(M + N)
Reason:- If your graph is implemented using adjacency lists, wherein each node maintains a list of all its adjacent edges, then, for each node, you could discover all its neighbors by traversing its adjacency list just once in liner time. For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E (total number of edges). So, the complexity of DFS is O(|V|) + O(|E|) = O(M + N).
Q12) Space Complexity for:-
Adjacency Matrix = O (V2)
An adjacency matrix is a |V | × |V | matrix of bits where element (i, j) is 1 if and only if the edge (vi , vj ) is in E. Thus an adjacency matrix takes up ?(|V | 2 ) storage (note that the constant factor here is small since each entry in the matrix is just a bit).
Adjacency List = O(|V|+|E|)
An adjacency list is a list of lists. Each list corresponds to a vertex u and contains a list of edges (u, v) that originate from u. Thus, an adjacency list takes up ?(V + E) space.
PLease let me know in case of any clarifications required. Thanks!