Graph Representation (Adjacency List & Matrix)

Given the number of vertices **n** and a list of **edges**, build both representations of the graph:

- **Adjacency List**: an array where `list[i]` contains all neighbors of vertex i.

- **Adjacency Matrix**: an n×n 2D array where `matrix[i][j] = 1` if there is an edge between i and j, else 0.

Assume the graph is **undirected**.

Input: n = 4, edges = [[0,1],[1,2],[2,3]]

Output: list: [[1],[0,2],[1,3],[2]], matrix: 4x4 with 1s at symmetric edge positions

Each edge appears in both directions for an undirected graph.

Input: n = 1, edges = []

Output: list: [[]], matrix: [[0]]

Single isolated vertex, no edges.

Time

O(V + E) for adjacency list, O(V^2) for adjacency matrix.

Space

O(V + E) for list, O(V^2) for matrix.

#1 — Path graph

Input: n=4 edges=[[0,1],[1,2],[2,3]]

Expected: {"list":[[1],[0,2],[1,3],[2]],"matrix":[[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,0]]}

#2 — Single isolated vertex

Input: n=1 edges=[]

Expected: {"list":[[]],"matrix":[[0]]}

#3 — Triangle graph

Input: n=3 edges=[[0,1],[0,2],[1,2]]

Expected: {"list":[[1,2],[0,2],[0,1]],"matrix":[[0,1,1],[1,0,1],[1,1,0]]}

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.