Graph Representation Methods: Matrix and List

Graph Representation Methods

Graph representation can be done in using many different ways. We will discuss here two commonly used representations.

• Adjacency Matrix Representation
• Adjacency List Representation

Adjacency Matrix Graph Representation

• In adjacency matrix representation, graph is represented using two dimensional array.
• Following shows the matrix representation for unweighted, undirected graph. For such representation, each array location A[i][j] stores 1 or 0. If there exists an edge between vertices V_i and V_j, set A[i][j] = 1, else set it 0. In this representation, number of 1s in matrix is double than the number of edges.
• For weighted graph, if there exists an edge between vertices V_i and V_j, set G[i][j] = w_ij, else set it 0, where, w_ij indicates weight of edge joining vertices V_iV_j

Adjacency matrix representation of the undirected, unweighted graph

• If graph does not contain any self-loop, all diagonal entries in array would be 0. We can easily find number of self-loops by summing diagonal entries in array.
• Adjacency matrix of complete graph has all ones, except diagonal entries. Complete graph does not have self-loop, so all diagonal entries are zero.
• Empty graph is represented using zero matrix.
• Adjacency matrix of undirected graph is symmetric, i.e. A[i][j] = A[j][i].
• Adjacency matrix of directed graph may not be symmetric.
• Following figure shows the representation of directed unweighted graph using matrix.

Adjacency matrix representation of the directed, unweighted graph

For a weighted graph, cells of the array represent the weight of the corresponding edge. The following figure shows the representation of an undirected weighted graph using a matrix.

Adjacency matrix representation of the undirected, weighted graph

Advantages:

• Simple to represent
• Easy to implement
• Number of edges computed
• Addition of edge is done in constant time O(1).

Disadvantages:

• Requires more memory to represent graph. With n vertices in graph, it needs array of size n x n. Space requirement of such representation is O(n²), where n indicates number of vertices.
• Finding adjacent edges to given vertex takes O(|V|²) times.
• Takes huge amount of effort to add / remove vertex.
• Slow for large graph.

Adjacency List Graph Representation

Another alternative to represent a graph is an adjacency list. Adjacency list uses a linked list to represent the graph. This is a more flexible and dynamic data structure. In this representation, prior knowledge of the number of vertices in the graph is not required. We will discuss here two ways to build adjacency list representation :

Method 1: This method uses common different data structures for vertices and edges. The structure node of vertices has two pointers. Horizontally they point to the list of edges associated with that vertex. Vertically downward they point to the next neighbor node. Figure (B) explains this representation.

Method 2: In this case, we create an array of head nods, and create pointers only for associated edges. As vertices are stored in an array, they can be directly accessed by array index. They do not require storing the address of the next node. Figure (C) explains this representation.

Additional Reading: Read More