Graphs

The stored prompt only says “Graphs”, so begin by clarifying the vertices, edge direction, weights, and objective instead of inventing a particular problem. Model sparse input with an adjacency list and state the invariant: mark a vertex when it is scheduled so it is processed once. Use DFS to explore reachability, detect components, or build a traversal; use BFS when each edge has equal cost and the first visit gives an unweighted shortest distance. If weights are non-negative, explain Dijkstra with a min-heap and stale-entry checks; if negative edges are possible, Dijkstra is invalid and the algorithm must change. Discuss how you would reconstruct a path with parent pointers. Test isolated vertices, disconnected components, parallel edges, self loops, cycles, and a graph too deep for recursive DFS. BFS and DFS take O(V + E); heap-based Dijkstra takes O((V + E) log V).