Graph representation – How do you represent a graph as an adjacency matrix?

In this post, we are going to cover how to represent a graph as an adjacency matrix. An adjacency matrix defines which nodes are connected in a graph in form of a 2D array. The size of the array is n*n, where n is the number of vertices in a graph.   

Consider the graph shown above. It has got 6 vertices and thus its adjacency matrix will have 6*6 values. Here is the adjacency matrix for the graph above:

 

                A             B             C             D             E              F

A             0              1              1              0              0              0

B             1              0              0              1              1              0

C             1              0              0              0              1              0

D             0              1              0              0              1              1

E              0              1              0              1              0              0

F              0              0              0              1              0              0

 

So a graph can be represented as a n*n array in form of an adjacency matrix.

A weighted graph can also be represented as an adjacency matrix. In this case, the 0s and 1s above will be converted to weights of edges of the graphs.

The space complexity for Adjacency matrix is O(n^2), where n is the number of vertices. However, the insert and search time complexity of adjacency matrix is O(1).  An adjacency matrix is a good representation when a graph is dense. This will help us find the relationship between vertices quickly. We say that a graph is dense when the number of edges is proportional to the number of vertices.

Programmatic representation of a graph in an adjacency matrix:

A graph can be represented as an array data structure. A graph for above adjacency matrix in java would be as below:

int adj_matrix[][] =
							{{0	,1	,1	,0	,0	,0},
							{1	,0	,0	,1	,1	,0},
							{1	,0	,0	,0	,1	,0},
							{0	,1	,0	,0	,1	,1},
							{0	,1	,0	,1	,0	,0},
							{0	,0	,0	,1	,0	,0}};

 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself