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], where V is 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.