Adjacency Matrix

An adjacency matrix is a 2D array representation of a graph. Each element A[i][j] indicates whether there is an edge from vertex i to vertex j.

It is a N x N matrix for a graph with N vertices. A[i][j] is 1 if there is an edge, else 0.

Adjacency matrix allows easy lookup to check if two vertices are connected. They are commonly used due to simple implementation.

However, they require more space for sparse graphs and do not scale well. Lookup is also slower than adjacency lists.

Solution

Here is an adjacency matrix implementation in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class AdjacencyMatrix:
  
  def __init__(self, num_vertices):
    self.matrix = [[0]*num_vertices for _ in range(num_vertices)]

  def add_edge(self, i, j):
    self.matrix[i][j] = 1
    self.matrix[j][i] = 1 

g = AdjacencyMatrix(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
print(g.matrix)

# [[0, 1, 1, 0], 
#  [1, 0, 0, 0],
#  [1, 0, 0, 0],
#  [0, 0, 0, 0]]

Key aspects:

2D array of 0s initially of size N x N
Edge from u to v stored by setting matrix[u][v] = 1
Symmetric so matrix[v][u] also set to 1

Adjacency matrix provides simple but inefficient representation for graphs.

Description: Adjacency Matrix

An Adjacency Matrix is a 2D array used for representing a graph. The cell at the ith row and jth column of the array represents an edge between the ith and jth vertices of the graph. In a weighted graph, the value of the cell is the weight of the edge; for unweighted graphs, it’s either 0 or 1, indicating the absence or presence of an edge, respectively. While less space-efficient for sparse graphs, this representation allows for quick queries to check for the existence of an edge between any two nodes.

Solution:

Below are examples to implement an undirected graph using an adjacency matrix in Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class AdjacencyMatrix {
    private int[][] matrix;

    public AdjacencyMatrix(int vertices) {
        matrix = new int[vertices][vertices];
    }

    public void addEdge(int src, int dest) {
        matrix[src][dest] = 1;
        matrix[dest][src] = 1;
    }

    public void printGraph() {
        for (int i = 0; i < matrix.length; ++i) {
            for (int j = 0; j < matrix[i].length; ++j) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyMatrix graph = new AdjacencyMatrix(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 3);
        graph.addEdge(3, 4);
        graph.addEdge(1, 2);

        graph.printGraph();
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>

class AdjacencyMatrix {
private:
    std::vector<std::vector<int>> matrix;

public:
    AdjacencyMatrix(int vertices) {
        matrix.resize(vertices, std::vector<int>(vertices, 0));
    }

    void addEdge(int src, int dest) {
        matrix[src][dest] = 1;
        matrix[dest][src] = 1;
    }

    void printGraph() {
        for (const auto& row : matrix) {
            for (const auto& cell : row) {
                std::cout << cell << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    AdjacencyMatrix graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 3);
    graph.addEdge(3, 4);
    graph.addEdge(1, 2);

    graph.printGraph();
    return 0;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class AdjacencyMatrix:
    def __init__(self, vertices):
        self.matrix = [[0 for _ in range(vertices)] for _ in range(vertices)]

    def addEdge(self, src, dest):
        self.matrix[src][dest] = 1
        self.matrix[dest][src] = 1

    def printGraph(self):
        for row in self.matrix:
            print(" ".join(map(str, row)))

if __name__ == "__main__":
    graph = AdjacencyMatrix(5)
    graph.addEdge(0, 1)
    graph.addEdge(0, 4)
    graph.addEdge(1, 3)
    graph.addEdge(3, 4)
    graph.addEdge(1, 2)

    graph.printGraph()

Key Takeaways

Adjacency Matrix is simple to implement and easy to understand.
It’s quick to check if a particular edge exists, taking constant time.
The space complexity is (O(V^2)), making it less suited for sparse graphs.
Java and C++ use 2D arrays, while Python uses a list of lists for the matrix.