Adjacency Matrix

An adjacency matrix is a fundamental data structure used in graph theory to represent relationships between vertices in a graph. For a graph with n vertices, it is represented as an n × n matrix where each element (i,j) indicates whether vertices i and j are connected by an edge.

Structure and Properties

Basic Definition

• For an unweighted graph:
  • Matrix element (i,j) = 1 if vertices i and j are connected
  • Matrix element (i,j) = 0 if no direct connection exists
• For a weighted graph:
  • Matrix element (i,j) contains the edge weight instead of 1
• For an undirected graph:
  • The matrix is symmetric across the main diagonal
  • A(i,j) = A(j,i) for all i,j

Space Complexity

The adjacency matrix requires Θ(n²) space, where n is the number of vertices, making it:

• Efficient for dense graphs
• Less space-efficient for sparse graphs

Applications

Algorithm Implementation

Adjacency matrices are particularly useful in:

• Graph traversal algorithms
• Shortest path calculations
• Network flow problems
• Matrix multiplication based graph algorithms

Real-world Usage

Common applications include:

• Social network connections
• Computer networks topology
• Route planning systems
• Circuit design

Advantages and Disadvantages

Advantages

1. Constant-time O(1) edge lookup
2. Simple implementation for graph operations
3. Efficient for dense graphs
4. Natural representation for matrix operations

Disadvantages

1. Space inefficiency for sparse graphs
2. Static size (requires matrix resizing for dynamic graphs)
3. May waste memory with unnecessary zero entries

Implementation

# Simple implementation example
class AdjacencyMatrix:
    def __init__(self, n):
        self.size = n
        self.matrix = [[0 for _ in range(n)] for _ in range(n)]

Related Concepts

The adjacency matrix is one of several graph representations, alongside:

• Adjacency list
• Incidence matrix
• Edge list

Each representation has its own trade-offs in terms of space efficiency and operation complexity, making them suitable for different use cases in graph algorithms.