- Contrast adjacency matrix and adjacency list representations for a graph. explain it for 5 marks

Definition: An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. On the other hand, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.

Space Complexity: An adjacency matrix has a space complexity of O(V^2) where V is the number of vertices. This is because it needs to store values for every combination of vertices, even if there is no edge between them. In contrast, an adjacency list has a space complexity of O(V + E) where E is the number of edges. This is because it only needs to store the vertices that are connected by an edge.

Time Complexity: For operations like checking if an edge exists between two vertices, an adjacency matrix is faster with a time complexity of O(1). However, for operations like finding all vertices adjacent to a vertex, an adjacency list is faster with a time complexity of O(V).

Usage: Adjacency matrices are better for dense graphs (where most of the elements are non-zero) because they provide a quick way to check if an edge exists. Adjacency lists are better for sparse graphs (where most of the elements are zero) because they take up less space and can find all vertices adjacent to a vertex faster.

Weighted Graphs: In weighted graphs, where edges have weights, adjacency matrices can directly store the weights as elements of the matrix. However, in adjacency lists, each list not only contains the vertices adjacent to a vertex, but also the weights of the connecting edges.