All subjects · Mathematics · WDM11 (D1)

Minimum spanning trees: Prim's algorithm

Prim's algorithm grows one tree outwards from a starting vertex. It gives a minimum spanning tree of the same total weight as Kruskal's.

Prim's algorithm

1. Choose a starting vertex.

2. Look at every edge joining a vertex in the tree to a vertex not yet in the tree. Add the shortest such edge (and its new vertex).

3. Repeat until every vertex is in the tree.

Show your working

List the edges in the order they are added, for example AC, CB, CD, ... The order of selection is what earns the marks. If two edges tie, either may be chosen; the total weight does not change.

No cycle check needed

Because Prim only ever joins a new vertex, it can never make a cycle. Do not write 'reject' in Prim: that is a Kruskal idea, and mixing them is a common error. Also do not confuse Prim with nearest neighbour, which only extends from the last vertex added.

Worked example

Use Prim's algorithm on network N, starting at A.

  1. Add AC (5)
  2. Add CB (6)
  3. Add CD (8)
  4. Add DE (4)
  5. Add EF (3)
  6. Add FG (8)

Answer: Order: AC, CB, CD, DE, EF, FG; total weight 34

Key idea: Grow one tree: add the shortest edge from the tree to a new vertex; no cycles can form; list edges in the order chosen.

Check yourself

  1. Use Prim's algorithm on network N starting at A. In what order are the edges added?
    • EF, DE, AC, BC, CD, FG
    • AC, AB, CD, DE, EF, FG
    • AC, CB, BE, EF, DE, FG
    • AC, CB, CD, DE, EF, FG
    Show answer

    AC, CB, CD, DE, EF, FG. From A: AC (5). Then the shortest edge out of {A, C} is CB (6), then CD (8), DE (4), EF (3), FG (8).

  2. Using Prim's algorithm on network N starting at G, what is the weight of the third edge added?
    Show answer

    4. From G the edges are added in the order GF (8), FE (3), ED (4), DC (8), CA (5), CB (6).

  3. Prim's algorithm on network N is started at G instead of A. What is the total weight of the tree?
    Show answer

    34. The minimum spanning tree weight does not depend on the starting vertex (it can only change which tree is found if there are ties).

  4. How does Prim's algorithm choose the next edge?
    • The shortest edge joining a vertex in the tree to a vertex not in the tree
    • The shortest edge in the network not yet used
    • The shortest edge from the last vertex added
    • The shortest edge that does not make a cycle anywhere
    Show answer

    The shortest edge joining a vertex in the tree to a vertex not in the tree. Prim considers every edge leaving the current tree.

  5. Why does Prim's algorithm never need to check for cycles?
    • It always uses the shortest edges
    • It starts at the smallest edge
    • Each new edge joins the tree to a vertex not yet in it
    • Networks used with it have no cycles
    Show answer

    Each new edge joins the tree to a vertex not yet in it. An edge from the tree to a brand new vertex cannot close a loop.

  6. Prim's algorithm is applied to a network with 9 vertices. How many times is an edge added?
    Show answer

    8. Each step adds one new vertex; the first vertex is free, so 8 edges are added.

Practise with instant feedback

Sources

Last updated 7 November 2026. Spotted a mistake? Tell us.