The two primary ways to represent a Graph are through an adjacency matrix and an adjacency list.
1. Adjacency Matrix
An Adjacency Matrix is a 2-Dimensional Array (or matrix) which is used for representing a graph. The rows and columns correspond to vertices of the graph. The entry in the matrix at row “i” and column “j’ indicates whether tree is an edge from vertex “i” to vertex “j”.
Characteristics of Adjacency Matrix
- Size: – For a Graph with n vertices the adjacency matrix is an n * n matrix.
- Edge: –
- In an unweighted graph, the entry is typically 1 (or True) if there is an edge, and 0 (or false) if there is no edge.
- In a weighted graph, the entry contains the weight of the edge, or a special value (such as 0 or infinity) if there is no edge.
2. Adjacency List
An Adjacency List is a collection of lists or arrays. Each vertex has a list that contains all the vertices it is connected to by a edge.
Characteristics of Adjacency List
- Storage: – Uses an array lists. The size of the array is equal to the number of vertices n.
- Space Efficiency: – Space usage is 0 ( V+ E), where V is the number of vertices and E is the number of edges, making it more efficient for sparse graph.
