CMP.10:5.2 - Choose graph access by the question, retaining edge meaning

For a directed graph with n vertices and m edges, a Boolean adjacency matrix supports a membership test by one entry lookup. Enumerating a vertex’s outgoing neighbors scans n entries. Adjacency lists store actual neighbors; enumeration examines its outgoing degree many entries, while a plain-list membership test can require the same scan. A hash index adds another storage/update trade-off.

A traversal that marks each vertex once and enumerates its outgoing edges therefore takes O(n+m) accesses with lists, and up to O(n²) with a matrix, excluding construction and output. Repeated pair-membership questions on a dense graph can favor the matrix. The graph’s mathematical identity alone does not choose the computational representation.

Now attach numeric weights. If zero is used both for an absent edge and for an existing zero-weight edge, those two states become indistinguishable. For edges 0→1 with weight 0, 1→2 with weight 2 and 0→2 with weight 5, treating zero as absence deletes a path of cost 2 and leaves the apparent direct cost 5. Repair the representation with a separate presence indication or an absent value outside the admitted weights. Changing the shortest-path algorithm cannot recover an edge already discarded by its input representation.