Step 4 of 8 · Worked example · TEACH

← Algorithms, Optimisation & Project Scheduling

0 of 3 done

Work through the example to CHECK to open the problems.

Reach CHECK to open the problems.Higher Level · Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 4

Follow the worked example and explain why each modelling and calculation step is valid.

Use Prim’s algorithm starting at A. The undirected graph has AB=3, AC=13, BC=5, BD=7, CD=16 and no other edges. Find the resulting tree weight.

An undirected graph has AB = 3, AC = 13, BC = 5, BD = 7 and CD = 16, and no other edges.

Use Prim's algorithm starting at A. Find the resulting tree weight W.

Read it once, slowly. Then copy it onto your page.
  • What is fixed? Four vertices, A, B, C, D, and five weighted edges: AB 3, AC 13, BC 5, BD 7, CD 16. No other edges: there is no AD.
  • How must I do it? Prim's algorithm, starting at A. The method is named, so the working must show Prim's steps in order.
  • What do they want? The weight W of the tree Prim builds: its edges added up. No units are given.
Céim

Higher Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 4 of 8

Prim's Algorithm

Prim’s algorithm builds a minimum spanning tree by repeatedly choosing the cheapest edge joining the current tree to a new vertex.

Why it matters

Recording the growing vertex set makes your exam working clear and prevents you from using Kruskal’s global edge-selection rule instead.

The worked example

An undirected graph has AB = 3, AC = 13, BC = 5, BD = 7 and CD = 16, and no other edges. Use Prim's algorithm starting at A. Find the resulting tree weight W.

How the worked example goes

  1. Read

    • What is fixed? Four vertices, A, B, C, D, and five weighted edges: AB 3, AC 13, BC 5, BD 7, CD 16. No other edges: there is no AD.
    • How must I do it? Prim's algorithm, starting at A. The method is named, so the working must show Prim's steps in order.
    • What do they want? The weight W of the tree Prim builds: its edges added up. No units are given.
  2. Understand

    • How do I picture it?
    • Draw A, B, C, D as a square with A top left, B top right, C bottom left, D bottom right. Join only the five given edges.
    • AB = 3, AC = 13, BC = 5
  3. Reduce

    • Where do I start?
    • At A. Write the tree as a set and grow it: {A}, then one more vertex each round.
    • Each round, list the edges leaving the tree and take the cheapest. Stop when all 4 are in, after 3 edges. W is their total.
  4. Solve

    • Round 1: from A.
    • Why this works: the cheapest edge from the tree to the rest always belongs to some minimum tree, so each choice is safe.
    • Tree {A}. Edges out: AB = 3, AC = 13.
  5. Check

    • Is it right?
    • Second route, Kruskal: sorted 3, 5, 7, 13, 16. Accept AB, BC, BD: no cycle, all 4 joined. Total 15. ✓
    • Edges left out: AC = 13 would close A–B–C–A; CD = 16 would close B–C–D–B. ✓