Skip to main content

Courses About Pricing Educators

Sign in Get started

Courses About Pricing Educators

Get started Sign in

Loading courses

Loading lessons

Weighted Graphs and Union-Find: Data Structures and Algorithms: Uncharted

Courses Data Structures and AlgorithmsWeighted Graphs and Union-Find

Weighted Graphs and Union-FindPro

Route by total cost, reconstruct paths, compress connectivity, and span a network cheaply.

Data Structures and Algorithms
Unit 12 of 16
20 lessons
130 min
420 XP

This unit is part of Pro. Upgrade to open every lesson in it.

Lessons

20 total

1When Hops LieCompare routes by total edge weight and explain when fewest hops gives the wrong answer.ProInteractiveConcept6 min20 XPOpen
2Weighted ListsApply weighted edge-list to adjacency-list conversion to building neighbor lists that carry a cost beside every destination.ProCodeConcept6 min20 XPOpen
3Why BFS Fails HereConstruct a weighted counterexample where a longer path costs less than the BFS path.ProInteractiveConcept6 min20 XPOpen
4Dijkstra, AssembledApply min-heap distance relaxation to driving distance relaxation with the smallest queued tentative distance.ProCodeConcept6 min20 XPOpen
5Dijkstra's PathsApply Dijkstra parent-map reconstruction to reconstructing the fastest map route from predecessor links.ProCodeConcept6 min20 XPOpen
6Predict DijkstraTrace tentative distances, relaxations, and nonstale priority entries in Dijkstra's algorithm.ProInteractiveConcept6 min20 XPOpen
7The Stale EntryApply lazy stale-priority deletion to skipping an outdated heap entry after a shorter route reaches the same node.ProCodeConcept6 min20 XPOpen
8Negative Edges Break ItExplain why a negative edge invalidates Dijkstra's settled-distance guarantee and calls for another algorithm.ProInteractiveConcept6 min20 XPOpen
9Dijkstra DrillsApply one Dijkstra pass for many destination queries to running one city-network search and answering several destination queries.ProCodePractice8 min20 XPOpen
10Who Is Connected?Apply parent-array union-find by walking to walking parent pointers to answer connectivity queries.ProCodeConcept6 min20 XPOpen
11Union by SizeApply attach-smaller-tree union-find to attaching each smaller parent tree beneath the larger root.ProCodeConcept6 min20 XPOpen
12Path CompressionApply path-compressing root lookup to flattening every visited parent path directly under its root.ProCodeConcept6 min20 XPOpen
13Predict the ForestTrace union-find roots, sizes, and path compression without changing component membership.ProInteractiveConcept6 min20 XPOpen
14Friend CirclesApply union-find component counting to unioning direct friendships and counting distinct roots.ProCodePractice8 min20 XPOpen
15The Cheapest CablesApply Kruskal safe-edge selection to accepting the cheapest cable that joins two previously separate building groups.ProCodeConcept6 min20 XPOpen
16Kruskal, CompleteApply complete Kruskal minimum spanning tree to building a complete minimum spanning tree and reporting its total cable cost.ProCodeConcept6 min20 XPOpen
17Prim, in ContrastContrast Prim's seed-grown frontier with Kruskal's globally sorted safe edges.ProInteractiveConcept6 min20 XPOpen
18The Redundant ConnectionApply union-find first-cycle edge detection to returning the first edge whose endpoints already share a union-find root.ProCodePractice8 min20 XPOpen
19Which Tool for the Map?Choose BFS, Dijkstra, or union-find according to whether a map brief asks for hops, weighted cost, or connectivity.ProInteractiveConcept6 min20 XPOpen
20Weighted Graphs Mastery CheckApply Dijkstra and Kruskal synthesis to combining shortest weighted distances with a minimum spanning cable cost.ProCodeMastery check10 min40 XPOpen

Graphs Dynamic Programming