Adjacency Matrix to Edge List Converter

Why graphs need representations

Graph theory has been a branch of mathematics since Leonhard Euler solved the “Seven Bridges of Königsberg” problem in 1736, proving that no walk could cross each bridge exactly once. Modern graph theory underlies everything from social networks to transportation routing, internet topology, molecular chemistry, and circuit design.

To compute with graphs algorithmically, you need a way to represent them in memory. The two most common representations are adjacency matrices and adjacency lists (also called edge lists).

The adjacency matrix

An adjacency matrix is a square n×n grid where each cell A[i][j] represents the relationship between vertex i and vertex j:

• A[i][j] = 1: edge exists between i and j (unweighted graph)
• A[i][j] = 0: no edge
• A[i][j] = w: edge with weight w (weighted graph)
• A[i][i]: self-loop (vertex connected to itself)

The matrix is n×n where n is the number of vertices. For a 5-vertex graph, the matrix has 25 cells.

Undirected vs directed graphs

Undirected graph: edges have no direction. If A connects to B, then B connects to A. The matrix is symmetric: A[i][j] = A[j][i].

Directed graph (digraph): edges have direction. A → B is different from B → A. The matrix is not symmetric in general.

Example matrices:

Undirected (4 vertices forming a cycle):

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Symmetric — top-right mirrors bottom-left.

Directed (4 vertices in a cycle 1→2→3→4→1):

0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0

Not symmetric — each edge points in only one direction.

Reading information from the matrix

A well-formed adjacency matrix reveals graph properties at a glance:

Number of edges:

• Undirected: count the 1’s in the upper or lower triangle (above/below the diagonal), then add diagonal entries (self-loops)
• Directed: count all non-zero entries

Vertex degree (number of connections):

• Undirected: degree of vertex i = sum of non-zero entries in row i (or column i, equivalent for symmetric matrices)
• Directed: out-degree = row sum, in-degree = column sum

Self-loops: non-zero entries on the diagonal A[i][i]

Isolated vertices: vertex with all zeros in row and column

Complete graph (every vertex connected to every other): all off-diagonal entries are non-zero

Example: small undirected graph

Consider:

    0 1 1 0
    1 0 1 1
    1 1 0 1
    0 1 1 0

This 4-vertex graph:

• Row 1: 1 connects to 2 and 3 → degree 2
• Row 2: 2 connects to 1, 3, 4 → degree 3
• Row 3: 3 connects to 1, 2, 4 → degree 3
• Row 4: 4 connects to 2 and 3 → degree 2
• Symmetric → undirected
• Diagonal is 0 → no self-loops
• 5 edges total

It’s a graph with 4 vertices forming a “kite” shape: vertices 2 and 3 connected to everyone, vertices 1 and 4 each connected to 2 and 3 only.

Adjacency list representation

The same graph as an adjacency list:

• 1: [2, 3]
• 2: [1, 3, 4]
• 3: [1, 2, 4]
• 4: [2, 3]

For each vertex, list its neighbors. For weighted graphs, include weights:

• 1: [(2, 5), (3, 3)]
• 2: [(1, 5), (3, 8), (4, 2)]
• etc.

When to use matrix vs list

The choice depends on graph density:

Sparse graphs (m « n²):

• Use adjacency lists
• Space: O(n + m)
• Faster for most operations
• Example: social network where each person has 200 friends among 1 million users

Dense graphs (m ≈ n²):

• Use adjacency matrix
• Space: O(n²)
• Direct edge lookup in O(1)
• Example: complete graph or near-complete

Operations that prefer matrix:

• Checking if edge exists: O(1) for matrix, O(deg(v)) for list
• Matrix multiplication for path counting
• Computing transitive closure

Operations that prefer list:

• Listing all neighbors: O(deg(v)) for list, O(n) for matrix
• Adding/removing vertices: easier with list
• Sparse graph operations in general

Space complexity comparison

For n vertices and m edges:

For n=1,000 vertices and m=5,000 edges (sparse):

• Matrix: 1,000,000 cells (mostly zeros)
• Adjacency list: ~10,000 entries
• Edge list: 5,000 entries

For n=1,000 vertices and m=400,000 edges (dense):

• Matrix: 1,000,000 cells
• Adjacency list: 800,000 entries (almost as big as matrix)
• Matrix wins in this case

Matrix multiplication and paths

A powerful property: matrix powers count paths.

If A is the adjacency matrix:

• A² (matrix squared) shows paths of length 2
• A³ shows paths of length 3
• A^k shows paths of length k

So A²[i][j] = number of paths from vertex i to vertex j using exactly 2 edges.

This connects graph theory to linear algebra. Many graph algorithms (PageRank, spectral clustering) use matrix operations on adjacency matrices.

Specific algorithms using matrices

Floyd-Warshall (all-pairs shortest paths):

• Operates directly on adjacency matrix
• O(n³) time
• Finds shortest path between every pair of vertices
• Especially useful for dense graphs

Spectral clustering: uses eigenvalues of the adjacency matrix (or its Laplacian) to find graph structure.

PageRank (Google’s original algorithm): iteratively multiplies a vector by the adjacency matrix to find vertex importance.

Power method for finding dominant eigenvector: useful for many graph centrality measures.

Adjacency matrix variants

Beyond the basic adjacency matrix:

Weighted adjacency matrix: entries are edge weights, not just 0/1

Laplacian matrix: L = D - A, where D is the degree matrix. Has special spectral properties.

Normalized Laplacian: scaled version useful for spectral methods.

Distance matrix: entries are shortest path distances (not just direct edges).

Modularity matrix: used in community detection.

Transition matrix: rows normalized to sum to 1 (probability matrix for random walks).

Real-world applications

Social networks (Facebook, LinkedIn):

• Adjacency matrices for friend connections
• Very sparse for large networks
• Usually stored as adjacency lists

Transportation networks (Google Maps):

• Edges = road segments
• Weights = distance or time
• Dijkstra’s algorithm uses adjacency lists

Internet topology:

• Routers and connections
• Highly sparse
• BGP routing uses adjacency information

Molecular chemistry:

• Atoms and bonds
• Small but dense for individual molecules
• Matrix representations common

Circuit design:

• Components and connections
• Both sparse and dense subgraphs exist

Recommendation systems:

• User-item bipartite graphs
• Matrix factorization (SVD) for predictions

Common pitfalls

1. Matrix size: O(n²) memory makes large graphs intractable as matrices
2. Wrong direction: forgetting that directed graphs aren’t symmetric
3. Self-loops: forgetting to handle A[i][i] entries
4. Multiple edges: matrix can’t represent multiple edges between same pair (use multigraph specially)
5. Weighted edge of 0: distinguishing “no edge” from “edge weight 0”
6. Indexing: 0-based vs 1-based indexing convention mismatches
7. Numerical precision: weighted graphs with floating-point weights can have rounding issues

Performance benchmarks

For graph algorithms, performance varies dramatically with representation:

For most modern graph problems with sparse data, adjacency lists win.

Bottom line

Adjacency matrices represent graphs as n×n grids where A[i][j] indicates edges. For undirected graphs, the matrix is symmetric; for directed graphs, generally not. Space is O(n²) regardless of edge count — efficient for dense graphs (m ≈ n²), wasteful for sparse graphs (m « n²). Vertex degree = sum of non-zero entries in the row. Matrix multiplication counts paths of given length. Used in Floyd-Warshall, PageRank, and spectral methods. For practical graph algorithms on sparse real-world data (social networks, internet), adjacency lists are typically preferred. Edge list extraction from a matrix is a common preprocessing step.