Algorithm
An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the context of graph theory, an adjacency matrix is a convenient way to represent a graph's structure.
For an undirected graph with n vertices, the adjacency matrix is an n×n matrix A, where A[i][j]=1 if there is an edge between vertex i and vertex j, and A[i][j]=0 otherwise. Since the graph is undirected, the matrix is symmetric, and A[i][j]=A[j][i] for all i and j.
For a directed graph, the adjacency matrix may not be symmetric. In this case, A[i][j]=1 indicates a directed edge from vertex i to vertex j, and A[i][j]=0 means there is no such edge.
Here's an example of an undirected graph represented by an adjacency matrix:
0 1 2 3
0 0 1 1 1
1 1 0 1 0
2 1 1 0 1
3 1 0 1 0
In this example, there is an edge between vertex 0 and vertex 1, as well as between vertex 0 and vertex 2, and so on.
Code Examples
#1 Adjacency Matrix implement in Python
Code -
Python Programming
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[0] * vertices for _ in range(vertices)]
def add_edge(self, start, end):
if 0 <= start < self.vertices and 0 <= end < self.vertices:
# Assuming an undirected graph, so we update both entries
self.adj_matrix[start][end] = 1
self.adj_matrix[end][start] = 1
def display(self):
for row in self.adj_matrix:
print(" ".join(map(str, row)))
# Example usage:
if __name__ == "__main__":
num_vertices = 5
graph = Graph(num_vertices)
# Adding edges
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
# Displaying the adjacency matrix
print("Adjacency Matrix:")
graph.display()
#2 Adjacency Matrix implement in Java
Code -
Java Programming
public class AdjacencyMatrix {
private int[][] matrix;
private int vertices;
public AdjacencyMatrix(int vertices) {
this.vertices = vertices;
this.matrix = new int[vertices][vertices];
}
// Add an edge between two vertices
public void addEdge(int source, int destination) {
// Assuming a simple, undirected graph, so we set both matrix[source][destination] and matrix[destination][source] to 1
matrix[source][destination] = 1;
matrix[destination][source] = 1;
}
// Print the adjacency matrix
public void printMatrix() {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
// Example usage
int numberOfVertices = 5;
AdjacencyMatrix graph = new AdjacencyMatrix(numberOfVertices);
// Adding edges
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
// Printing the adjacency matrix
graph.printMatrix();
}
}
#3 Adjacency Matrix implement in C
Code -
C Programming
#include <stdio.h>
// Maximum number of vertices in the graph
#define MAX_VERTICES 100
// Function to initialize the adjacency matrix
void initializeMatrix(int matrix[MAX_VERTICES][MAX_VERTICES], int numVertices) {
for (int i = 0; i < numVertices; ++i) {
for (int j = 0; j < numVertices; ++j) {
matrix[i][j] = 0; // Initialize all elements to 0
}
}
}
// Function to add an edge to the adjacency matrix
void addEdge(int matrix[MAX_VERTICES][MAX_VERTICES], int startVertex, int endVertex) {
matrix[startVertex][endVertex] = 1;
matrix[endVertex][startVertex] = 1; // For undirected graphs
}
// Function to display the adjacency matrix
void displayMatrix(int matrix[MAX_VERTICES][MAX_VERTICES], int numVertices) {
printf("Adjacency Matrix:\n");
for (int i = 0; i < numVertices; ++i) {
for (int j = 0; j < numVertices; ++j) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int numVertices, numEdges;
printf("Enter the number of vertices: ");
scanf("%d", &numVertices);
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];
// Initialize the adjacency matrix
initializeMatrix(adjacencyMatrix, numVertices);
printf("Enter the number of edges: ");
scanf("%d", &numEdges);
// Add edges to the adjacency matrix
for (int i = 0; i < numEdges; ++i) {
int start, end;
printf("Enter edge %d (start end): ", i + 1);
scanf("%d %d", &start, &end);
addEdge(adjacencyMatrix, start, end);
}
// Display the adjacency matrix
displayMatrix(adjacencyMatrix, numVertices);
return 0;
}
#4 Adjacency Matrix implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int vertices;
vector < vector<int>> adjacencyMatrix;
public:
// Constructor
Graph(int v) : vertices(v), adjacencyMatrix(v, vector<int>(v, 0)) {}
// Add an edge to the graph
void addEdge(int src, int dest) {
// Assuming a simple, undirected graph
adjacencyMatrix[src][dest] = 1;
adjacencyMatrix[dest][src] = 1;
}
// Display the adjacency matrix
void display() {
cout << "Adjacency Matrix:" << endl;
for (int i = 0; i < vertices; ++i) {
for (int j = 0; j < vertices; ++j) {
cout << adjacencyMatrix[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
// Create a graph with 4 vertices
Graph graph(4);
// Add edges
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
// Display the adjacency matrix
graph.display();
return 0;
}
Demonstration
Adjacency Matrix Data Structure and Algorithm