Question

Q 10 If a graph containing n vertices and medges, is represented using adjacency list structure, how much of memory will be required?
Ops: A. O O(n-m)
B. O O(n*m)
C. C On)
D. O O(n+m)​

Answer 1

Answer:

An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is the adjacency list representation of the above graph.

Answer 2

Option (D): O(n+m)​

If a graph containing n vertices and merges, is represented using adjacency list structure, O(n+m)​ memory will be required.

• A list of lists is an adjacency list. Each list has an associated vertex (u) and a list of edges (u, v) that come from that vertex. An adjacency list therefore occupies (V + E) space.
• One of the simplest and most popular representations of a network is an adjacency list, often known as an edge list.
• The list of connected nodes for each edge in the network serves as an indicator.
• A graph is represented as an array of linked lists by an adjacency list. Each item in the linked list that the index of the array represents represents a different vertex that forms an edge with that vertex.
• An adjacency list is a combination of an edge list and an adjacency matrix, and that is exactly what it is.
• In addition to serving as a representation of a graph, an adjacency list is a collection of linked lists that makes it simple to identify which vertices are close to one another.

#SPJ2