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: the top-right triangle mirrors the 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, because 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.

Where matrices earn their keep

Floyd-Warshall, the all-pairs shortest path algorithm, works directly on the matrix in O(n³) and has no natural adjacency-list form at all. Spectral clustering uses the eigenvalues of the matrix or its Laplacian, L = D - A, where D holds the degrees on the diagonal. PageRank in its original form is nothing but repeated multiplication of a vector by a normalized version of this matrix. All three want a dense rectangular block of numbers, which is exactly what a matrix is and a list is not.

Beyond the plain 0/1 form you will meet the weighted matrix (entries are edge weights), the distance matrix (entries are shortest path lengths rather than direct edges), and the transition matrix (rows scaled to sum to 1, for random walks). Same grid, different meaning per cell.

Common pitfalls

1. Matrix size: O(n²) memory makes large graphs intractable as matrices
2. Wrong direction: forgetting that directed graphs are not symmetric
3. Self-loops: forgetting to handle A[i][i] entries. By convention a self-loop adds two to an undirected vertex’s degree, because both ends of the edge attach to the same vertex
4. Multiple edges: a matrix cannot represent two edges between the same pair unless you store a count
5. Weighted edge of 0: telling “no edge” apart from “edge of weight 0” is impossible in a plain matrix, which is a real problem for road networks where a zero-cost link exists
6. Indexing: 0-based against 1-based conventions, which is where most off-by-one graph bugs come from

Performance

For most modern graph problems the data is sparse and adjacency lists win, which is why every serious graph library stores lists and converts to a matrix only when an algorithm demands one.

A check worth running every time

The handshake lemma says the degrees of an undirected graph always sum to exactly twice the number of edges, because every edge contributes one to each of its two endpoints. If your degrees do not add up that way, either the matrix is not symmetric or a self-loop has been miscounted. The result panel does this check on whatever you paste in.