Introduction to Adjacency Matrix For Graphs
Graphs are a very important data structure for many applications. They’re employed in a variety of areas, including computer science, engineering, biology, and medicine. The adjacency matrix is an important data structure that can be used to represent a graph in linear algebra. It can be very useful for finding the shortest path between nodes in a graph and for determining the set of nodes that are connected directly to a given node.
We will learn how to use the adjacency matrix to implement various algorithms to find paths and connected components in a graph.
What is Adjacency Matrix?
Adjacency Matrix is a graph representation of relationships between nodes. It can be used to find out which nodes are adjacent to each other and how they are related. An adjacency matrix usually represents an undirected graph, meaning it does not have a direction between any two nodes. It does not include any edge weights. Each cell of the matrix indicates whether the corresponding node is adjacent to another node. These cells can either be empty (0) or filled (1). The “edge set” and “node set,” respectively, are the terms used to describe the matrix’s rows and columns. An adjacency matrix stores the edges of a graph. There are edges in every row and column in the graph.
For example, if we have an undirected graph with N vertices and M edges, then the adjacency matrix will have N rows and M columns. A matrix’s entry i,j represents how many edges connect one vertex to another. If i ≠ j, then i-j represents an edge in the graph. Similarly, if i = j, then this edge represents a self-loop.
Representation of adjacency matrix
Let M be a positive integer and suppose we have an m x n adjacency matrix X. Then the adjacency matrix of the undirected graph represented by X is of the form below. If v is a vertex, it is located at position (i,j). The corresponding element Ai represents the set of neighbours of v located at positions (i−1,j), (i,j−1), …, (i−m+1,j). In other words, the element of row i and column j is equal to the number of times that i-th vertex is connected to j-th vertex, excluding the case where i=j in which case it is equal to 0.
Since every vertex has the same number of neighbours, it can be shown that all the entries of an adjacency matrix are non-negative real numbers.
If vertex v does not have an edge connecting to any other vertex, the corresponding element of the adjacency matrix for that vertex will be equal to zero.
How to create an adjacency matrix?
If you are working with graphs, then it is very likely that you will need to create an adjacency matrix. This is a simple and effective way of visualizing the relationships between nodes in a graph. Adjacency matrices can be built in several ways. Here are some of the methods that you can use:
Undirected graph adjacency matrix creation
To create an undirected graph adjacency matrix, you need to perform the steps listed below:
- Identify all of the nodes in the graph.
- Label each node with a unique ID and record the ID of each edge in the network.
- Calculate the distance between every pair of nodes and store the result in the table of the undirected graph adjacency matrix. Each entry in this table indicates the distance of the corresponding pair of nodes.
- Create the matrix using the recorded data. The resulting matrix will contain two columns for each set of adjacent nodes and two rows for each pair in the undirected graph.
Here is an example of an undirected graph created using this method:
Directed graph adjacency matrix creation
To create a directed graph adjacency matrix, follow the steps below:
- Identify every node in the network.
- Label each node with a unique ID and keep track of the ID of each network edge.
- Calculate the distance between each pair of nodes in the network and save the findings in the directed graph adjacency matrix table. Each entry in this table indicates the distance of the corresponding pair of nodes.
- Using the recorded data, create the matrix. The resultant matrix will have one column for each group of nearby nodes in the directed graph, and two rows for each pair.
This method creates a directed graph like this:
Algorithm of an Adjacency Matrix
<a href="https://codedamn.com/playground/P4FtObYQo5IUA7wgPsZuX">// C program for the above approach
#include <stdio.h>
int N, M;
void createAdjMatrix(int Adj[][N + 1],
int arr[][2])
{
for (int i = 0; i < N + 1; i++) {
for (int j = 0; j < N + 1; j++) {
Adj[i][j] = 0;
}
}
for (int i = 0; i < M; i++) {
int x = arr[i][0];
int y = arr[i][1];
Adj[x][y] = 1;
Adj[y][x] = 1;
}
}
void printAdjMatrix(int Adj[][N + 1])
{
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
printf("%d ", Adj[i][j]);
}
printf("\n");
}
}
int main()
{
N = 5;
int arr[][2] = { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 1, 5 } };
M = sizeof(arr) / sizeof(arr[0]);
int Adj[N + 1][N + 1];
createAdjMatrix(Adj, arr);
printAdjMatrix(Adj);
return 0;
}
</a>Code language: C/AL (cal)Example of an Adjacency Matrix
The following is an example of an adjacency matrix for a directed graph with 6 nodes and 6 edges:
Conclusion
An Adjacency matrix is a powerful tool for representing and manipulating graphs. By using the matrix, we can easily find the shortest path between two vertices or calculate the degree of a vertex. Thanks for reading!
Frequently Asked Questions to Resolve (FAQs)
What is an adjacency matrix in graphs?
In an undirected or directed graph, an adjacency matrix represents the adjacency relationship between vertices. Graphs describe the relationships between their vertices. They consist of the node ID (or name) at each row and a column, and a table that lists the distances between any two nodes. It is also known as a weighted adjacency matrix or adjacency list. An adjacency matrix is used widely in network analysis to understand the structure of complex networks such as social networks, biological networks, etc.
How do you find an adjacency matrix?
An adjacency matrix is a table that shows the relationship between vertices in a graph. Each row is a vertex, and each column is an edge connecting them. Each entry in the table is a pair of numbers that tells you which vertex is connected to which another vertex. [1,2] tells you that vertex 1 is connected to vertex 2.
What is the condition for an adjacency matrix?
A graph is said to be an adjacency matrix if each node has an edge with only other nodes that are adjacent to that node. More specifically, if the graph is an adjacency matrix, every edge only exists between two nodes if there is an edge between the two nodes.
What are adjacency matrices used for?
An adjacency matrix is used to determine the neighbors of a node in an undirected graph. Therefore, it can be used to analyze the relationships in a network.
What is the process of finding an adjacency matrix?
Find all vertices in the graph, including the origin vertex and its neighbors. An origin vertex is the first vertex found when the algorithm starts. All other vertices are called neighbors of the origin vertex. The algorithm stops when there are no neighbors left to find. Create the adjacency matrix by finding all possible edges between the neighbors of the origin vertex. For example, if the origin vertex has neighbors A and B, then there will be two possible edges connecting A to B: edge 1 = {A, B} and edge 2 = {B, A}. The adjacency matrix will have two rows and two columns, where the first column contains the edges from row 1 and the second column contains the edges from row 2. If there are two possible edges between node i and node j, then there is a corresponding element aij in the adjacency matrix.
Sharing is caring
Did you like what Vanshika wrote? Thank them for their work by sharing it on social media.