Computer Science
Grade 11
20 min
Graph Algorithms: Minimum Spanning Trees (Prim's and Kruskal's)
Implement and analyze Prim's and Kruskal's algorithms for finding the minimum spanning tree in a graph, understanding their time complexities and applications.
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Define a graph, spanning tree, and Minimum Spanning Tree (MST).
Explain the greedy approach used by both Prim's and Kruskal's algorithms.
Trace the step-by-step execution of Prim's algorithm on a given weighted, undirected graph.
Trace the step-by-step execution of Kruskal's algorithm on a given weighted, undirected graph.
Identify and avoid common errors, such as creating cycles or choosing a non-optimal edge.
Compare the data structures and time complexities of Prim's and Kruskal's algorithms.
Analyze real-world problems that can be modeled and solved using MST algorithms.
Imagine you're designing a new city's fiber optic network. How would you connect every neighborhood with the least amount of expensive cable...
2
Key Concepts & Vocabulary
TermDefinitionExample
Weighted Undirected GraphA collection of vertices (nodes) connected by edges, where each edge has a numerical value (weight or cost) and the connections have no direction.A map of cities (vertices) where the edges are roads and the weights are the distances between cities.
Spanning TreeA subgraph that includes all the vertices of the original graph and is a tree (i.e., it has no cycles).For a graph of 4 cities (A, B, C, D), a set of 3 roads that connects all of them without creating a loop, like A-B, B-C, C-D.
Minimum Spanning Tree (MST)A spanning tree of a weighted graph that has the minimum possible sum of edge weights.From all possible ways to connect the 4 cities, the MST is the set of 3 roads with the smallest total distance.
Greedy AlgorithmAn algorithmic parad...
3
Core Syntax & Patterns
Prim's Algorithm Logic
Start with any vertex. At each step, add the cheapest edge that connects a vertex inside the growing tree to a vertex outside the tree.
Use this when you want to grow your MST from a single source. It's like a single amoeba expanding to consume the entire graph. It's efficient on dense graphs (graphs with many edges).
Kruskal's Algorithm Logic
Sort all edges by weight from smallest to largest. Iterate through the sorted edges, adding an edge to the tree only if it does not form a cycle.
Use this when you want to build the MST like a forest of trees that eventually merge into one. It's very efficient on sparse graphs (graphs with fewer edges).
The V-1 Edges Rule
A spanning tree for a graph with V vertices will always have...
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
If a connected, weighted, undirected graph has the property that all of its edge weights are unique, what can be said about its Minimum Spanning Tree?
A.The graph will have multiple different MSTs.
B.The graph will have exactly one, unique MST.
C.It is impossible to find an MST for such a graph.
D.The MST will be identical to the shortest path between any two nodes.
Challenging
What is the result of running Kruskal's algorithm on a graph that is not connected (i.e., it consists of two or more separate components)?
A.The algorithm will fail and produce an error.
B.The algorithm will produce a spanning tree for only the largest component.
C.The algorithm will connect the components using the cheapest possible edges between them.
D.The algorithm will produce a Minimum Spanning Forest, which is a collection of MSTs, one for each component.
Challenging
You have already computed the MST for a graph. Now, you take an edge that is ALREADY part of the MST and DECREASE its weight. What happens to the MST?
A.The MST will definitely change, and the algorithm must be re-run.
B.The MST might change, depending on how much the weight was decreased.
C.The MST will not change.
D.The graph might no longer have a valid MST.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free