Unit 8: Graphs and Graph Theory

Given an undirected graph, count how many disconnected groups of vertices exist.

Use BFS to find the fewest edges from a start vertex to a target and reconstruct the path.

Traverse a graph and identify a cycle without mistaking the edge back to the parent as a cycle.

Use visiting and finished states to detect whether a directed graph contains a cycle.

Color neighboring vertices with opposite colors and detect conflicts.

Given course prerequisites, produce a valid order or report that no order exists because of a cycle.

Explain how vertices can reach each other in directed graphs and outline a two-pass strategy.

Use a priority queue to find shortest paths when all edge weights are nonnegative.

Choose edges that connect all vertices with minimum total cost while avoiding cycles.

Treat cells as graph vertices and recolor a connected region using BFS or DFS.

Count connected groups of land cells and explain how marking visited cells prevents double counting.

List every path from source to target in a directed acyclic graph.

Copy graph nodes and edges without duplicating shared neighbors incorrectly.

Identify edges whose removal disconnects a graph and explain the role of discovery times.

Given a friendship graph, find everyone within two connections of a student.

Find a path in a road network while avoiding closed edges and reporting no path when necessary.

Given software package dependencies, determine a safe installation order.

Use BFS in a grid to find the closest boundary exit while avoiding walls.

Given keys found in rooms, decide whether every room can be visited.

Process edges and identify the first edge that connects vertices already connected.

Find vertices whose removal disconnects the graph and explain why they matter in network reliability.

Compare adjacency lists, adjacency matrices, and edge lists for dense and sparse graphs.

Given an edge list, compute each vertex degree and identify isolated or highly connected vertices.

Find a path that minimizes the largest single edge cost encountered along the route.

Given task durations and dependencies, compute the earliest completion time for the final task.

Recommend activities based on shared memberships while excluding activities already selected.

Given a BFS or DFS that marks visited too late, show how duplicates or loops can occur.

Given a graph and neighbor order, predict BFS and DFS visit orders.

Model systems as vertices and access paths as edges, then find shortest paths from an exposed node to a sensitive node.

Create a graph assignment with representation choice, traversal code, path reconstruction, tests, and written analysis.