Solve graph tasks with different contracts
Build three utilities: shortest unweighted route, prerequisite order, and minimum-cost connectivity. Share a graph parser where useful, but do not confuse the algorithms' assumptions.
Task A: edges 0->1, 0->2, 2->3; shortest 0->3 uses 2 edges.
Task B: prerequisites 0->2, 1->2; either 0,1,2 or 1,0,2 is valid.
Task C: undirected weights 0-1:2, 1-2:3, 0-2:9; MST total is 5.
The first two use directed edges in this fixture; the third is undirected. An adjacency-list importer must add both directions only where the graph contract requires it. Validate vertex identifiers before starting traversal.
Acceptance checks
For each utility, cover empty or invalid starts, disconnected vertices, duplicate edges, and cycles where relevant. Reconstruct routes and verify every consecutive edge exists. Validate topological results against every prerequisite, and validate a spanning tree's edge count and connectivity.
Extension: introduce weighted routing and explain why BFS must be replaced when edge weights differ.
Check: report “unreachable,” “cyclic prerequisites,” and “disconnected forest” as distinct outcomes rather than one generic empty result.