Adjacency Matrix

Adjacency Matrix is a 2D array of size V*V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 which indicates that there is an edge from vertex i to vertex j. The adjacency matrix for undirected graph is always symmetric. It also helps to represent the weighed graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

The adjacency matrix for the above graph is

The following is the simple C++ implementation of Adjacency Matrix:

#include
using namespace std;
int vertArray[20][20]; //the adjacency matrix initially 0
int count = 0;
void displayMatrix(int x) {
   int u, v;
   for(u = 0; u < x; u++) {
      for(v = 0; v < x; v++) {
         cout << vertArray[u][v] << " ";
      }
      cout << endl;
   }
}

//Function to add edge into the matrix
void add_edge(int x, int y) {
   vertArray[x][y] = 1;
   vertArray[x][y] = 1;
}

main(int argc, char* argv[]) {
   int v = 6;
   //there are 6 vertices in the graph
   add_edge(0, 4);
   add_edge(0, 3);
   add_edge(1, 2);
   add_edge(1, 4);
   add_edge(1, 5);
   add_edge(2, 3);
   add_edge(2, 5);
   add_edge(5, 3);
   add_edge(5, 4);
   displayMatrix(v);
}

0 0 0 1 1 0
0 0 1 0 1 1
0 0 0 1 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 1 0

• The representation of Adjacency Matrix is easier to implement and follow.
• Removing an edge takes O(1) time.
• The queries like whether there is an edge from vertex ’u’ to vertex ‘v’ are efficient and can be done in O(1).

• The Adjacency matrix consumes more space O(V^2).
• Even if the graph is sparse (contains less number of edges), it consumes the same space.
• Adding a vertex has the time complexity of O(V^2).