Unit 18: Graphs
Nodes connected by edges instead of a strict hierarchy, and the handful of algorithms that spread across them, find a path, or connect them all.
7 topics · 26 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
Graph Terminology and Representations
- How it worksHow does an adjacency list store only a node's actual neighbors while an adjacency matrix stores every possible pair?
- Worked exampleBuild the adjacency list and the adjacency matrix for a graph with edges A-B, B-C, and A-C.
- Going furtherWhat happens to the memory used by an adjacency matrix once a sparse graph grows to a million nodes?
Your turn1 of 2
A graph has 697 nodes. Its adjacency matrix representation uses one cell per possible pair of nodes, giving n times n total cells. How many cells does the adjacency matrix for this graph have?Breadth-First Search: Spreading in Rings
- How it worksHow does a queue make breadth-first search visit every neighbor at the current distance before going one step further?
- Worked exampleTrace breadth-first search from node A on a graph with edges A-B, A-C, B-D, C-D and list the visit order.
- Common mistakeWhy doesn't breadth-first search dive down one path as deep as it can before backing up?
- Worked exampleFind the distance from A to D in a graph with edges A-B, B-C, C-D, A-D using breadth-first search.
Your turn1 of 2
Breadth-first search from node A visits every neighbor at the current distance before going one step further. If a graph's shortest path from A to a target node is 14 edges long, how many total distance rings does BFS expand through before finding it, counting the starting node as ring 0?Depth-First Search: Plunging Down One Path
- How it worksHow does a stack, either explicit or through recursion, make depth-first search plunge down one branch first?
- Worked exampleTrace depth-first search from node A on a graph with edges A-B, A-C, B-D, C-D and list the visit order.
- Going furtherWhat happens to depth-first search's visit order once each node's neighbors are explored in reverse?
Your turn1 of 2
Depth-first search from node A commits to one path, going 697 nodes deep before hitting a dead end and backing up. How many nodes deep did this one path go before backing up?BFS Versus DFS Side by Side on the Same Graph
- How it worksHow does swapping a queue for a stack turn the very same traversal skeleton from BFS into DFS?
- Worked exampleTrace both BFS and DFS from node A on a graph with edges A-B, A-C, B-D, C-E and compare the two visit orders.
- Common mistakeWhy doesn't depth-first search guarantee the shortest path the way breadth-first search does on an unweighted graph?
- Going furtherWhat happens to both traversals once the graph contains a cycle that could send them back to an already-visited node?
- Ties togetherHow does the choice between BFS and DFS depend on whether you need the shortest path or just any path at all?
Your turn1 of 2
Both BFS and DFS are run from the same starting node on a graph of 349 nodes, and each traversal visits every one of the n nodes exactly once. How many total node visits occur across both traversals combined?Topological Sort
- How it worksHow does topological sort repeatedly pick a node with no remaining incoming edges to build a valid order?
- Worked exampleTrace a topological sort on the prerequisite graph socks before shoes, shirt before jacket, shoes before nothing else.
- Common mistakeWhy doesn't every graph have a valid topological sort at all?
Your turn1 of 2
A topological sort repeatedly picks a node with no remaining incoming edges to build a valid order, for a graph of 349 nodes. How many total nodes get picked and added to the final order?Shortest Paths with Dijkstra's Algorithm
- How it worksHow does Dijkstra's algorithm always expand the closest unvisited node next, using a priority queue to pick it?
- Worked exampleTrace Dijkstra's algorithm from node A on a graph with edges A-B weight 4, A-C weight 1, C-B weight 1.
- Common mistakeWhy doesn't Dijkstra's algorithm work correctly once a graph contains a negative edge weight?
- Going furtherWhat happens to Dijkstra's chosen path once one edge's weight is lowered after the algorithm already finished?
Your turn1 of 2
Dijkstra's algorithm expands the closest unvisited node next, using a priority queue. For a graph of 349 nodes, how many total nodes does the algorithm expand before every node has been visited?Minimum Spanning Trees
- How it worksHow does Prim's algorithm grow a minimum spanning tree by repeatedly adding the cheapest edge that reaches a new node?
- Worked exampleTrace Prim's algorithm starting at node A on a graph with edges A-B weight 2, A-C weight 3, B-C weight 1.
- Common mistakeWhy isn't a minimum spanning tree the same thing as the shortest path between two particular nodes?
- Ties togetherHow does a minimum spanning tree differ from a shortest-path tree built from the same weighted graph?
Your turn1 of 2
Connecting 697 towns with the cheapest possible set of roads never needs more than n minus 1 roads, forming a minimum spanning tree. How many roads does a minimum spanning tree connecting n towns use?