Adjacency Matrix
About
An Adjacency Matrix is a 2D array representation of a graph where:
Rows and columns represent vertices.
Each cell (i, j) contains 1 (or weight) if there is an edge from vertex i to vertex j, otherwise 0.
Why Use an Adjacency Matrix?
Fast Edge Lookup: Checking if an edge exists is O(1).
Best for Dense Graphs: If the graph has many edges, adjacency matrices are efficient.
Easier Implementation: Simple 2D array structure.
Structure of an Adjacency Matrix
An adjacency matrix consists of:
A 2D array
graph[V][V], whereVis the number of vertices.If the graph is undirected,
graph[i][j] = graph[j][i].If the graph is weighted, the matrix stores weights instead of 1s.
Representation
For a graph with 4 vertices (V = 4) and edges (0→1, 0→2, 1→3, 2→3):
0
1
2
3
0
0
1
1
0
1
1
0
0
1
2
1
0
0
1
3
0
1
1
0
1. Graph Representation Using a 2D Array
Code
import java.util.*;
class Graph {
private int vertices; // Number of vertices
private int[][] adjacencyMatrix; // Adjacency Matrix
// Constructor
public Graph(int vertices) {
this.vertices = vertices;
adjacencyMatrix = new int[vertices][vertices]; // Initialize matrix with 0s
}
// Method to add an edge (Undirected Graph)
public void addEdge(int src, int dest) {
adjacencyMatrix[src][dest] = 1;
adjacencyMatrix[dest][src] = 1; // For undirected graph
}
// Method to add a directed edge
public void addDirectedEdge(int src, int dest) {
adjacencyMatrix[src][dest] = 1;
}
// Method to remove an edge
public void removeEdge(int src, int dest) {
adjacencyMatrix[src][dest] = 0;
adjacencyMatrix[dest][src] = 0; // For undirected graph
}
// Method to check if an edge exists
public boolean hasEdge(int src, int dest) {
return adjacencyMatrix[src][dest] == 1;
}
// Method to print the adjacency matrix
public void printGraph() {
System.out.println("Adjacency Matrix:");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
System.out.print(adjacencyMatrix[i][j] + " ");
}
System.out.println();
}
}
// Method to get neighbors of a given vertex
public List<Integer> getNeighbors(int vertex) {
List<Integer> neighbors = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[vertex][i] == 1) {
neighbors.add(i);
}
}
return neighbors;
}
// Depth-First Search (DFS)
public void dfs(int startVertex) {
boolean[] visited = new boolean[vertices];
System.out.print("DFS Traversal: ");
dfsHelper(startVertex, visited);
System.out.println();
}
private void dfsHelper(int vertex, boolean[] visited) {
visited[vertex] = true;
System.out.print(vertex + " ");
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[vertex][i] == 1 && !visited[i]) {
dfsHelper(i, visited);
}
}
}
// Breadth-First Search (BFS)
public void bfs(int startVertex) {
boolean[] visited = new boolean[vertices];
Queue<Integer> queue = new LinkedList<>();
visited[startVertex] = true;
queue.add(startVertex);
System.out.print("BFS Traversal: ");
while (!queue.isEmpty()) {
int vertex = queue.poll();
System.out.print(vertex + " ");
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[vertex][i] == 1 && !visited[i]) {
queue.add(i);
visited[i] = true;
}
}
}
System.out.println();
}
// Main Method for Testing
public static void main(String[] args) {
Graph graph = new Graph(5);
// Adding edges
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
// Printing the adjacency matrix
graph.printGraph();
// Checking if edge exists
System.out.println("Edge between 0 and 1: " + graph.hasEdge(0, 1));
System.out.println("Edge between 2 and 3: " + graph.hasEdge(2, 3));
// Removing an edge
graph.removeEdge(1, 4);
graph.printGraph();
// Getting neighbors of a vertex
System.out.println("Neighbors of vertex 1: " + graph.getNeighbors(1));
// Performing DFS and BFS
graph.dfs(0);
graph.bfs(0);
}
}Output
Adjacency Matrix:
0 1 1 0 0
1 0 0 1 1
1 0 0 0 1
0 1 0 0 0
0 1 1 0 0
Edge between 0 and 1: true
Edge between 2 and 3: false
Adjacency Matrix:
0 1 1 0 0
1 0 0 1 0
1 0 0 0 1
0 1 0 0 0
0 0 1 0 0
Neighbors of vertex 1: [0, 3]
DFS Traversal: 0 1 3 2 4
BFS Traversal: 0 1 2 3 4 Operations Breakdown and Time Complexity
Operation
Time Complexity
Explanation
Add Edge
O(1)
Directly updates the adjacency matrix.
Remove Edge
O(1)
Directly removes the edge from the matrix.
Check Edge
O(1)
Looks up value in matrix.
Get Neighbours
O(V)
Scans row in matrix to find connected vertices.
DFS Traversal
O(V²)
In the worst case, visits every vertex and edge.
BFS Traversal
O(V²)
Uses queue, but still needs to check matrix for neighbours.
2. Weighted Graph Implementation
If the graph is weighted, we replace 1 with the weight of the edge.
Code
import java.util.*;
class WeightedGraph {
private int vertices; // Number of vertices
private int[][] adjacencyMatrix; // Adjacency Matrix
// Constructor
public WeightedGraph(int vertices) {
this.vertices = vertices;
adjacencyMatrix = new int[vertices][vertices];
// Initialize the matrix with a large value to indicate no edge (-1 is used here)
for (int i = 0; i < vertices; i++) {
Arrays.fill(adjacencyMatrix[i], -1);
}
}
// Method to add an edge (Undirected Graph)
public void addEdge(int src, int dest, int weight) {
adjacencyMatrix[src][dest] = weight;
adjacencyMatrix[dest][src] = weight; // For undirected graph
}
// Method to add a directed edge
public void addDirectedEdge(int src, int dest, int weight) {
adjacencyMatrix[src][dest] = weight;
}
// Method to remove an edge
public void removeEdge(int src, int dest) {
adjacencyMatrix[src][dest] = -1;
adjacencyMatrix[dest][src] = -1; // For undirected graph
}
// Method to check if an edge exists
public boolean hasEdge(int src, int dest) {
return adjacencyMatrix[src][dest] != -1;
}
// Method to get the weight of an edge
public int getEdgeWeight(int src, int dest) {
return adjacencyMatrix[src][dest];
}
// Method to print the adjacency matrix
public void printGraph() {
System.out.println("Weighted Adjacency Matrix:");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
System.out.print((adjacencyMatrix[i][j] == -1 ? "∞" : adjacencyMatrix[i][j]) + "\t");
}
System.out.println();
}
}
// Method to get neighbors of a given vertex
public List<Integer> getNeighbors(int vertex) {
List<Integer> neighbors = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[vertex][i] != -1) {
neighbors.add(i);
}
}
return neighbors;
}
// Depth-First Search (DFS)
public void dfs(int startVertex) {
boolean[] visited = new boolean[vertices];
System.out.print("DFS Traversal: ");
dfsHelper(startVertex, visited);
System.out.println();
}
private void dfsHelper(int vertex, boolean[] visited) {
visited[vertex] = true;
System.out.print(vertex + " ");
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[vertex][i] != -1 && !visited[i]) {
dfsHelper(i, visited);
}
}
}
// Breadth-First Search (BFS)
public void bfs(int startVertex) {
boolean[] visited = new boolean[vertices];
Queue<Integer> queue = new LinkedList<>();
visited[startVertex] = true;
queue.add(startVertex);
System.out.print("BFS Traversal: ");
while (!queue.isEmpty()) {
int vertex = queue.poll();
System.out.print(vertex + " ");
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[vertex][i] != -1 && !visited[i]) {
queue.add(i);
visited[i] = true;
}
}
}
System.out.println();
}
// Main Method for Testing
public static void main(String[] args) {
WeightedGraph graph = new WeightedGraph(5);
// Adding edges with weights
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 2);
graph.addEdge(1, 3, 7);
graph.addEdge(1, 4, 1);
graph.addEdge(2, 4, 3);
// Printing the adjacency matrix
graph.printGraph();
// Checking if edge exists and its weight
System.out.println("Edge between 0 and 1: " + graph.hasEdge(0, 1));
System.out.println("Weight of edge (0,1): " + graph.getEdgeWeight(0, 1));
System.out.println("Edge between 2 and 3: " + graph.hasEdge(2, 3));
// Removing an edge
graph.removeEdge(1, 4);
graph.printGraph();
// Getting neighbors of a vertex
System.out.println("Neighbors of vertex 1: " + graph.getNeighbors(1));
// Performing DFS and BFS
graph.dfs(0);
graph.bfs(0);
}
}Output
Weighted Adjacency Matrix:
∞ 4 2 ∞ ∞
4 ∞ ∞ 7 1
2 ∞ ∞ ∞ 3
∞ 7 ∞ ∞ ∞
∞ 1 3 ∞ ∞
Edge between 0 and 1: true
Weight of edge (0,1): 4
Edge between 2 and 3: false
Weighted Adjacency Matrix:
∞ 4 2 ∞ ∞
4 ∞ ∞ 7 ∞
2 ∞ ∞ ∞ 3
∞ 7 ∞ ∞ ∞
∞ ∞ 3 ∞ ∞
Neighbors of vertex 1: [0, 3]
DFS Traversal: 0 1 3 2 4
BFS Traversal: 0 1 2 3 4
Operations Breakdown and Time Complexity
Operation
Time Complexity
Explanation
Add Edge
O(1)
Directly updates the adjacency matrix.
Remove Edge
O(1)
Directly removes the edge from the matrix.
Check Edge
O(1)
Looks up value in matrix.
Get Edge Weight
O(1)
Directly accesses weight from matrix.
Get Neighbors
O(V)
Scans row in matrix to find connected vertices.
DFS Traversal
O(V²)
Worst-case visits all vertices and edges.
BFS Traversal
O(V²)
Uses queue, but still checks matrix for neighbors.
Last updated