Graph Representation Methods

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

• 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 Vi and Vj, 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 Vi and Vj, set G[i][j] = wij, else set it 0, where, wij indicates weight of edge joining vertices ViVj

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

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

• 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(n2), where n indicates number of vertices.
• Finding adjacent edges to given vertex takes O(|V|2) times.
• Takes huge amount of effort to add / remove vertex.
• Slow for large graph.