Adjacency Matrix

Definition

Concept

Adjacency matrix: square matrix used to represent finite graphs. Dimension: n × n, where n = number of vertices. Entry at row i, column j indicates presence/weight of edge from vertex i to j.

Formal Definition

For graph G=(V,E), adjacency matrix A defined as:

A[i][j] = 1, if (i,j) ∈ E (unweighted graph) w, if edge (i,j) with weight w exists (weighted graph) 0, otherwise

Purpose

Provide constant-time edge lookup. Facilitate matrix-based algorithms. Standard in dense graphs.

Structure and Representation

Matrix Dimensions

Square matrix with rows and columns equal to vertex count. Indexing corresponds to vertex identifiers or labels.

Entry Values

Binary (0/1) for unweighted graphs indicating absence/presence. Numeric weights for weighted graphs. Zero or special null value for no edge.

Symmetry

Undirected graphs: symmetric adjacency matrix (A[i][j] = A[j][i]). Directed graphs: generally asymmetric.

Types of Graphs and Their Matrices

Undirected Graphs

Symmetric adjacency matrix. Edges reflected in both A[i][j] and A[j][i].

Directed Graphs

Asymmetric matrix. Edge direction indicated by nonzero entry in A[i][j].

Weighted Graphs

Matrix entries store edge weights. Zero or special value indicates no edge.

Simple vs. Multigraphs

Simple graphs: binary or weighted single entries. Multigraphs require edge count or list extension, not standard in adjacency matrix.

Space Complexity

Basic Analysis

Requires O(n²) space for n vertices regardless of edge count. Dense graphs use this efficiently; sparse graphs may waste space.

Sparse vs Dense Graphs

Sparse: fewer edges relative to n²; adjacency matrix inefficient. Dense: edges close to n²; adjacency matrix optimal.

Memory Optimization

Use of bit matrices for unweighted graphs reduces space. Compressed sparse row/column formats possible but less common.

Time Complexity of Operations

Edge Lookup

O(1) constant time to check edge existence between vertex pair.

Iteration Over Neighbors

O(n) time to find all neighbors of a vertex due to row scanning.

Graph Construction

O(n²) to initialize matrix; O(m) to fill edges, where m = number of edges.

Construction of Adjacency Matrix

Initialization

Create n × n matrix initialized to zeros or null values.

Filling Edges

For each edge (u,v), set A[u][v] = 1 or weight. For undirected graphs, also set A[v][u].

Algorithmic Steps

Initialize matrix A[n][n] with zerosFor each edge (u,v) in E: A[u][v] = weight or 1 If undirected: A[v][u] = weight or 1

Graph Algorithms Using Adjacency Matrix

Matrix Multiplication for Paths

Compute powers of adjacency matrix to find number of paths of length k between vertices.

Dijkstra's Algorithm

Adjacency matrix supports weighted graphs; dense graphs favor matrix for easy access to edge weights.

Floyd-Warshall Algorithm

All-pairs shortest paths computed via dynamic programming on adjacency matrices.

Breadth-First Search (BFS)

Implemented by scanning adjacency matrix rows for neighbors.

Advantages

Constant-Time Edge Queries

Edge existence queries O(1). Useful for dense graphs and algorithms requiring frequent edge lookups.

Simple Data Structure

Easy to implement and understand. Matrix form enables linear algebra applications.

Algorithm Compatibility

Supports matrix-based algorithms and parallel computation.

Disadvantages

High Space Usage

Always O(n²) space regardless of edge count; inefficient for large, sparse graphs.

Slow Neighbor Enumeration

Requires O(n) time to find neighbors of a single vertex.

Not Suitable for Multigraphs

Cannot easily represent multiple edges between same vertices.

Comparison with Adjacency List

Space Efficiency

Adjacency lists use O(n + m) space; adjacency matrix uses O(n²).

Edge Lookup Time

Adjacency matrix O(1); adjacency list O(k), k = degree of vertex.

Neighbor Enumeration

Adjacency list faster for iterating neighbors: O(k) vs O(n).

Use Cases

Matrix preferred for dense graphs, algorithms involving matrix operations; list preferred for sparse graphs.

Applications

Network Analysis

Modeling connectivity and flows in communication, transportation networks.

Matrix-Based Algorithms

Pathfinding, connectivity checks, and transitive closure via matrix powers.

Computer Graphics

Representing adjacency of polygons or meshes.

Social Networks

Analyzing relationships and influence patterns.

Examples

Undirected Unweighted Graph

Directed Weighted Graph

References

• Gross, J.L., Yellen, J., "Graph Theory and Its Applications," CRC Press, 2nd ed., 2005, pp. 45-78.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., "Introduction to Algorithms," MIT Press, 3rd ed., 2009, pp. 605-620.
• West, D.B., "Introduction to Graph Theory," Prentice Hall, 2nd ed., 2001, pp. 45-67.
• Tarjan, R.E., "Depth-First Search and Linear Graph Algorithms," SIAM Journal on Computing, vol. 1, 1972, pp. 146-160.
• Knuth, D.E., "The Art of Computer Programming, Volume 1: Fundamental Algorithms," Addison-Wesley, 3rd ed., 1997, pp. 290-310.