All subjects · Mathematics · WDM11 (D1)

Prim's algorithm on a distance matrix

Prim's algorithm works neatly on a table of distances, which is how it is often programmed. You also need to convert between a network and its matrix.

Matrix and network

In a distance matrix, the entry in row X and column Y is the weight of edge XY. For an undirected network the matrix is symmetrical about the leading diagonal. A dash means no direct edge. To draw the network from a matrix, draw an edge for each entry above the diagonal.

Prim on a matrix

1. Choose the start vertex; cross out its row and number its column 1.

2. Look down all the numbered columns; circle the smallest entry not crossed out.

3. The row of that entry is the new vertex: cross out its row and number its column with the next number.

4. Repeat until every row is crossed out.

Writing the answer

Each circled entry gives an edge: column vertex to row vertex. List the edges in the order chosen and add the weights. The numbers above the columns show the order the vertices joined the tree.

Worked example

Use Prim's algorithm on matrix M, starting at P.

  1. Edge PR (9) added
  2. Edge RT (10) added
  3. Edge TU (7) added
  4. Edge RQ (11) added
  5. Edge QS (8) added

Answer: Order of vertices P, R, T, U, Q, S; edges PR, RT, TU, RQ, QS; weight 45

Key idea: Cross out the row, number the column, choose the smallest entry in the numbered columns, repeat. Read edges as column to row.

Check yourself

  1. Use Prim's algorithm starting at P on matrix M. Find the total weight of the minimum spanning tree.
    Show answer

    45. Edges in order: PR (9), RT (10), TU (7), RQ (11), QS (8). Total 45.

  2. Using Prim's algorithm on matrix M from P, which vertex joins the tree second (after P)?
    • R
    • U
    • Q
    • T
    Show answer

    R. Column P's smallest entry is 9 in row R.

  3. Continuing Prim's algorithm on matrix M from P, which edge is added third?
    • PU
    • RQ
    • TU
    • RU
    Show answer

    TU. Edges so far: PR, RT. The smallest entry in columns P, R and T in rows not crossed out is 7, giving TU.

  4. How many edges does the network drawn from matrix M have? (Every entry above the diagonal is an edge.)
    Show answer

    15. M has an entry for every pair of the 6 vertices, so it is K_6 with 6 × 5/2 = 15 edges.

  5. Why is the distance matrix of an undirected network symmetrical about the leading diagonal?
    • Every vertex has even degree
    • The network is complete
    • The diagonal entries are all zero
    • The weight of XY is the same as the weight of YX
    Show answer

    The weight of XY is the same as the weight of YX. Row X column Y and row Y column X both describe the same edge.

  6. In the matrix form of Prim's algorithm, why is the row of each new vertex crossed out?
    • To show that the column has been used
    • So that no edge into a vertex already in the tree is chosen
    • Because the row is the longest
    • So the matrix becomes symmetrical
    Show answer

    So that no edge into a vertex already in the tree is chosen. Rows represent the vertex being joined. Crossing out a vertex's row stops another edge being chosen to it, which would make a cycle.

Practise with instant feedback

Sources

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