In Computer Science, there is a classic problem called the "Minimum Spanning Tree (MST)." It sounds profound, but its core concept is actually quite simple: "How can we connect everyone using the least amount of materials?"
Today, we won't be writing any code. Instead, we are entering a "Muddy City" that has just suffered a heavy rainstorm. We will invite the child to serve as the Mayor. Their mission is to solve the citizens' troubles, and if they can successfully save enough budget, the city will get a brand-new swimming pool!
Phase 1: The Dilemma of Mud vs. The Pool
First, we use a story to create a scenario where "Optimization" becomes an urgent necessity.
- Scenario Setup:
- Bring out the "Muddy City Map" (a drawing with many houses and dotted lines representing possible roads).
- The Story:"Long ago, there was a small city with no paved roads. Every time it rained heavily, the ground turned into a muddy swamp. Cars got stuck, and everyone's shoes got ruined."
- The Mission:"You are the newly elected Mayor. The citizens are begging you to pave the roads so that every house can travel to any other house."
- The Key Conflict:
- "However, paving stones are very expensive! The money in the city treasury was originally intended to build a huge swimming pool."
- "If you pave every single road, the money will run out, and the swimming pool will be canceled. Your challenge is: Connect all the houses using the fewest number of stones possible. The money you save will go toward building the pool!"
Phase 2: Visualizing Cost
Turning "Length" into "Quantity", we need to make abstract distance visible.
- Props Preparation:
- Print out the map. Prepare about 40 black tokens (Go stones, small blocks, or real pebbles).
- Or use the game below.
- Rules Explanation:
- The grid squares between houses on the map represent the length of the road.
- Paving method: Placing tokens to fill the grid squares means the road is paved. The more squares there are, the longer the road, and the more money (stones) it costs.
- The Goal: Ask the child to place tokens on the paper until all houses are "connected," then count how many stones were used.
Phase 3: Kruskal's Paving Magic
Children often connect roads randomly or create circles (loops) at first. This is our chance to introduce the computer scientist's strategy: Kruskal's Algorithm.
- Intuitive Attempt:
- Let the child try once on their own. They might use 25 stones.
- Parent: "25 stones... that seems a bit expensive. We can only build half a pool. Can we be thriftier?"
- Guiding Strategy:
- Parent:"Since we want to save money, should we pave the 'Long Roads' or the 'Short Roads' first?"
- Child: "Short ones! Because they use fewer stones."
- Executing the Magic:
- "Okay! Let's scan the whole map with our eyes. Where is the absolute shortest road?"
- The child finds roads that are only 2 or 3 grids long.
- "Pave it!" (Place the tokens).
- Then find the "Second Shortest" and "Third Shortest" roads, paving them in order.
- Critical Judgment (Cycle Detection):
- When the child wants to pave a specific road, ask them to pause.
- Question："Wait! Can these two houses already reach each other through a different path?"
- Observation： If House A and House B are already connected (even if it's a detour), this new road is a "Wasteful Shortcut."
- Parent's Order: "Since they are already connected, even though this road is short, we won't pave it! Save the money!"
- The Reveal:
- Follow this rule—"Pick the cheapest first, skip if already connected"—until the end.
- Count the total stones (The optimal solution is usually much lower than the random attempt).
- Cheer: "Congratulations, Mayor! You connected the whole city with the minimum stones. The swimming pool is fully funded!"
Phase 4: Concept Connection
- Parent: "The super-thrifty strategy you just used was invented by a man named Kruskal (Kruskal's Algorithm). Besides paving roads, what else do you think needs to be 'connected together but as short as possible'?"
- Guiding Reflection:
- Power Company: Wires must reach every house; shorter wires mean saving money on copper.
- Water Pipes: Pipes must connect the whole city; fewer pipes mean fewer chances for leaks.
- Internet: Computer network cables also need to be efficient.
- Terminology:Computer scientists call the shape you created a "Minimum Spanning Tree (MST)."
- Minimum: Costs the least (shortest total length).
- Spanning:Connects all the dots.
- Tree: Because there are no loops (cycles), it branches out like a tree.
Phase 5: Debug & Challenge
In this phase, we introduce real-world trade-offs. We want the child to understand that sometimes "Saving Money (MST)" does not mean "Convenient" or "Fast."
- Challenge 1: The Budget Backpacker vs. The Layover Nightmare
- Scenario: "Imagine a 'Stingy Airline' decided to fly planes exactly along the 'Minimum Spanning Tree' map we just made to save fuel."
- Question："If you wanted to travel from the city on the far left to the city on the far right, look at the map. What problem do you see?"
- Discovery: The child will notice they have to transfer many times! Because we "saved" (deleted) the direct shortcuts to cut costs, passengers must fly along the winding tree branches.
- Summary:For the airline, this is the cheapest way to build the network (MST); but for a traveler in a rush, it’s not the best route. This is why real-world flight planning balances "Total Cost" with "Convenience."
- Challenge 2: The Pizza Delivery Nightmare (The Travelling Salesman Problem)
- Scenario: "Congratulations Mayor! Now a Pizza Shop has opened. A delivery driver needs to deliver pizza to every house on the map in one trip and return to the shop."
- Experiment: "Use your finger as the motorbike. Try to drive on our 'Money-Saving Roads (MST).' The rule is: Visit every house, but try not to turn back."
- Discovery (The Conflict):The child will find it very difficult! Because the MST has many "Dead Ends" (tips of the branches).
- The driver has to drive in, deliver, and then "U-turn" all the way back out to get to the next branch.
- This saves stones for the Mayor, but wastes gas and time for the driver!
- Summary
- Defining the Problem: This challenge of "how to plan a route that visits every single location and returns to the starting point, while keeping the total distance as short as possible," is what computer scientists call the "Travelling Salesman Problem (TSP)."
- Different：
- MST: Helps the Mayor save paving stones (Just connect them, no loops needed).
- TSP: Helps FedEx/Amazon drivers save gas (Needs an efficient loop).
- Unsolved Mystery: Do you think TSP is hard to draw? Here is a secret: Computer scientists still haven't found a "super formula" that is both fast and guaranteed to be the best for this problem! It is one of the hardest challenges in the computer world (NP-Hard).
Teaching Observation Checklist
| Observation Point | Less Effective Response | More Effective Scaffolding |
| When the child creates a circle (loop) | "Wrong. You can't have circles." | "Look here. If I can already walk from House A to House B using the old road, is paving this new road 'extra'? Mayor, can we save the money from this road to buy a water slide instead?" (Emphasizing Cycle Prevention) |
| When the child asks why we don't pave the shortcut | "Because that uses more stones." | "If you were a traveler, you would really want this shortcut. But you are the Mayor, and this road costs the citizens 500 million dollars. Do you choose 'Convenience for everyone' or 'Lower taxes'? Computer Science is all about making these trade-offs." |
| Explaining why the Delivery Truck can't use this map efficiently | "Because tree graphs have dead ends." | "Try driving your finger like a truck. You notice you constantly have to 'Reverse' to get out, right? So, the Delivery Route (TSP) and the Paving Route (MST) are two very different math problems!" |