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.Ordinary 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=7, AC=17, BC=9, BD=11, CD=20 and no other edges. Find the resulting tree weight.

An undirected graph has AB = 7, AC = 17, BC = 9, BD = 11 and CD = 20, 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 and five edges: AB 7, AC 17, BC 9, BD 11, CD 20. No other edges: there is no AD.
  • How must I do it? Prim's algorithm, starting at A. The method is named, so the page 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

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

Prim's Algorithm

Prim's algorithm grows one tree by repeatedly choosing the cheapest edge joining a vertex already in the tree to a new vertex.

Why it matters

Tracking the growing vertex set prevents you from confusing Prim's rule with Kruskal's global edge ordering.

The worked example

An undirected graph has AB = 7, AC = 17, BC = 9, BD = 11 and CD = 20, 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 and five edges: AB 7, AC 17, BC 9, BD 11, CD 20. No other edges: there is no AD.
    • How must I do it? Prim's algorithm, starting at A. The method is named, so the page 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 on top and C, D below. Join only the five given edges. BC runs across the middle.
    • A tree joining all 4 has 4 − 1 = 3 edges. Try AB, AC, CD: 7 + 17 + 20 = 44.
  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. After 3 rounds all 4 are in. W is the total.
  4. Solve

    • Round 1: from A.
    • Tree {A}. Edges out: AB = 7, AC = 17.
    • Take AB = 7. Tree {A, B}. Total 7.
  5. Check

    • Is it right?
    • Kruskal as a second route: sorted 7, 9, 11, 17, 20. Accept AB, BC, BD. Total 27. ✓
    • Left out: AC would close A–B–C–A; CD would close B–C–D–B. ✓