Implement Adjacency Matrix
Before we learn how to implement the adjacency matrix for graphs, we need to become familiar with its functionality. Let us consider the following undirected graph having 6 vertices numbered from 0 to 5 and understand how it will be represented with the help of an adjacency matrix.
Undirected graph having 6 vertices
If there is an edge between any two vertices of the graph, then the value in the corresponding cell of the matrix will be 1 or else it will be 0. For example, we can see from the above diagram that there is an edge between the vertex 1 and 2, so the value of the cell in the matrix having row =1 and col =2 will will be 1. Similarly the value of the cell having col=1 and row =2 will also be 1 as this is an undirected graph.
Adjacency Matrix for the Undirected Above Graph
To represent the above undirected graph , the adjacency matrix should look like:
- The row and columns number represents the vertex of the graph in the adjacency matrix.
- Cell having value =1 indicates there is an edge between the row and column vertex in the graph.
| Indexes | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 | 0 | 1 |
| 3 | 1 | 0 | 1 | 0 | 0 | 1 |
| 4 | 1 | 1 | 0 | 0 | 0 | 1 |
| 5 | 0 | 1 | 1 | 1 | 1 | 0 |
Now as we are familiar with the representation of an undirected graph using an adjacency matrix, let’s go through the algorithm we will follow to implement the adjacency matrix for the graph:
Algorithm to Implement Adjacency Matrix
- Define the number of vertices V in the graph
- Create a 2D array adjMatrix of size V x V.
- Initialize all elements of adjMatrix to 0.
- Define a function addEdge(u, v) to add an edge between two vertices:
- Check if u and v are valid vertices (0 <= u, v < V).
- If valid, set adjMatrix[u][v] = 1
- Also set adjMatrix[v][u] = 1 as this is an undirected graph.
- Define a function printAdjMatrix() to print the adjacency matrix.
- Iterate through the matrix using two for loops and print the value of the cells.
C++ Program to Implement Adjacency Matrix
An adjacency matrix is a way to represent graph data structure in C++ in the form of a two-dimensional matrix. It is a simple square matrix of size V*V, where V represents the number of vertices in the graph. Each cell of the matrix represents an edge between the row vertex and column vertex of the graph. In this article, we will learn how to implement an adjacency matrix in C++.