The graph below represents the walking trails between landmarks in a national park. The weights are the lengths of the trails in kilometres.

The park authorities want to pave sections of the trails to enable wheelchair access. The paved trails must connect all of the landmarks in the park in a way that minimises the paving required.

This problem is an example of finding a minimum spanning tree, i.e. the spanning tree which has the minimum weight. We consider two algorithm’s to acheive this, Kruskal’s Algorithm and Prim’s Algorithm.

Kruskal’s Algorithm (for a graph with n vertices)

• Step 1: Select the edge with the least weight (if there are several such edges, choose one at random);
• Step 2: Choose the least weight edge remaining that does not complete a cycle (if there are several such edges, choose one at random);
• Step 3: Repeat Step 2 until n-1 edges have been chosen

Worked Example 1

Use Kruskal’s algorithm to find the minimum spanning tree of the following graph:

Exercise (note that the notes continue after this exercise with the other algorithm)

Answers

Prim’s Algorithm

• Step 1: Start with any vertex;
• Step 2: Join this vertex to the nearest vertex (if more than one vertices are an equal distance away, choose one at random);
• Step 3: Join the vertex which is nearest to either of those already connected.
• Step 4: Continue joining connected vertices to the nearest unconnected vertex until all vertices are connected.

Worked Example 2

Find the minimum spanning tree for the graph below:

We can also apply Prim’s algorithm to a weighted adjacency table, using the following steps (applied to the table shown directly below):

• Step 1: Select any vertex at random (e.g. vertex E);
• Step 2: Delete the row of the chosen vertex;
• Step 3: Number the column of the chosen vertex;
• Step 4: Circle the lowest undeleted entry in any of the numbered columns (if more that one are lowest, pick one at random). The row of teh circled entry gives us the new chosen vertex;
• Step 5: Repeat steps 2 to 4 until all rows are deleted. The circled entries give the edges of the minium spanning tree.

Exercise

Answers