Adjacency list requires memory of the order of2 pointsθ(V-E)θ(VE)θ(V/E)θ(V+E)
Question
Adjacency list requires memory of the order of2 pointsθ(V-E)θ(VE)θ(V/E)θ(V+E)
Solution
The adjacency list representation of a graph requires memory of the order of θ(V+E), where V is the number of vertices and E is the number of edges in the graph.
Here's why:
-
In an adjacency list, we maintain a master list of all the vertices in the Graph G and for each vertex we have a linked list containing all the vertices that it is connected to.
-
The total number of entries in all the linked lists is twice the number of edges, as an edge between vertices V and E leads to two entries: one in the list for V and one in the list for E.
-
Therefore, the total space required is θ(V+E).
-
V is the space for the master list (as there is one entry for each vertex) and E is the total space for all the linked lists (as each edge contributes to two entries in the lists).
So, the correct answer is θ(V+E).
Similar Questions
Adjacency list requires memory of the order of
Problem StatementImplement a Graph using an Adjacency List. Given the number of vertices (V) and the edges, create an undirected graph using an adjacency list. Print the adjacency list of each vertex.Input format :The first line of input consists of an integer V, representing the number of vertices.The second line consists of an integer E, representing the number of edges.The following E lines consist of the edge information.Output format :The output prints the adjacency list of each vertex.Refer to the sample output for formatting specifications.Code constraints :1 ≤ V ≤ 1001 ≤ E ≤ 100Sample test cases :Input 1 :570 10 41 21 31 42 33 4Output 1 :Adjacency list of vertex 0head -> 1-> 4Adjacency list of vertex 1head -> 0-> 2-> 3-> 4Adjacency list of vertex 2head -> 1-> 3Adjacency list of vertex 3head -> 1-> 2-> 4Adjacency list of vertex 4head -> 0-> 1-> 3Input 2 :671 31 41 52 32 42 54 6Output 2 :Adjacency list of vertex 0head Adjacency list of vertex 1head -> 3-> 4-> 5Adjacency list of vertex 2head -> 3-> 4-> 5Adjacency list of vertex 3head -> 1-> 2Adjacency list of vertex 4head -> 1-> 2-> 6Adjacency list of vertex 5head -> 1-> 2Note :The program will be evaluated only after the “Submit Code” is clicked.Extra spaces and new line characters in the program output will result in the failure of the test case.
Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________?Group of answer choicesO(E)O(E*E)O(V)O(E+V)
vector < vector < int >> printAdjacency(int n, int m, vector < vector < int >> & edges) { // Write your code here. vector < vector < int>> adj_list[n+1]; for (int i=0; i<m; i++){ adj_list[edges[i][0]].push_back(edges[i][1]); adj_list[edges[i][1]].push_back(edges[i][0]); } return adj_list;}
What is the worst time complexity of checking node u and v are directly connected by an edge in a graph G = |V, E| when adjacency list is used
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.