Adjacency Matrix to Edge List Converter
Convert an adjacency matrix to an edge list.
Calculate vertex degrees, detect weighted graphs, and analyze graph structure from matrix input.
Adjacency Matrix Representation
An adjacency matrix is a square n×n grid where entry A[i][j] represents the connection (or weight) between vertex i and vertex j.
Unweighted Graphs
- A[i][j] = 1 → edge exists between i and j
- A[i][j] = 0 → no edge
Weighted Graphs
- A[i][j] = w → edge with weight w exists between i and j
- A[i][j] = 0 → no edge
Undirected vs Directed
- Undirected: the matrix is symmetric (A[i][j] = A[j][i])
- Directed: A[i][j] ≠ A[j][i] is possible (edges have direction)
Reading Degree from the Matrix
The degree of vertex i equals the number of non-zero entries in row i. For undirected graphs, this counts each edge once per endpoint.
Example: 4×4 Matrix
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
Edge list: 1–2, 1–3, 2–4, 3–4 Degrees: vertex 1=2, vertex 2=2, vertex 3=2, vertex 4=2
This is a cycle graph C₄.
Space Complexity
Adjacency matrices use O(n²) space, making them inefficient for sparse graphs. Edge lists use O(m) space, which is much better when edges m « n².