DSA Graph Representations

How it works

A matrix needs a fixed mapping between vertex labels and row/column positions. This fixture uses None for no edge, allowing a genuine edge with weight zero. An undirected matrix would need a symmetric relationship policy; these directed values are not silently mirrored. A matrix is not automatically better because its pair lookup is simple: scanning all possible neighbors can include many empty cells.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as graph-representations.py and run python graph-representations.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

vertices = ["gate", "oak", "pond"]
index = {vertex: position for position, vertex in enumerate(vertices)}
matrix = [[None for _ in vertices] for _ in vertices]
matrix[index["gate"]][index["oak"]] = 0
matrix[index["gate"]][index["pond"]] = 4
print(matrix[0])
print(matrix[1][0] is None)
print(matrix[0][1] == 0)

Expected result

[None, 0, 4]
True
True

The zero-weight edge remains distinguishable from an absent edge. The explicit label mapping keeps display names separate from storage positions. A later vertex insertion would require a representation update rather than assuming those indexes remain permanent identities.

Time, space and assumptions

A V-by-V matrix uses O(V²) slots and O(1) indexed pair lookup. Neighbor iteration is O(V) per row, compared with O(degree) for an adjacency list.