Minimum Spanning Tree Algorithms

A tree is a connected graph without cycles.

Properties of Trees

° A graph is a tree if and only if there is one and only one path joining any two of its vertices.

° A connected graph is a tree if and only if every one of its edges is a bridge.

° A connected graph is a tree if and only if it has N vertices and N; 1 edges.

° A subgraph that spans (reaches out to ) all vertices of a graph is called a spanning subgraph.

° A subgraph that is a tree and that spans (reaches out to ) all vertices of the original graph is called a spanning tree.

° Among all the spanning trees of a weighted and connected graph, the one (possibly more) with the least total weight is called a minimum spanning tree (MST).

• Step 1

  Find the cheapest edge in the graph (if there is more than one, pick one at random). Mark it with any given colour, say red.

• Step 2

  Find the cheapest unmarked (uncoloured) edge in the graph that doesn't close a coloured or red circuit. Mark this edge red.

• Step 3

  Repeat Step 2 until you reach out to every vertex of the graph (or you have N ; 1 coloured edges, where N is the number of Vertices.) The red edges form the desired minimum spanning tree.

• Kruskal Step by Step
• Tutorial Kruskal
• Interactive Kruskal's Algorithm

---

Prim's Algorithm

• Step 0

  Pick any vertex as a starting vertex. (Call it S). Mark it with any given colour, say red.

• Step 1

  Find the nearest neighbour of S (call it P₁). Mark both P₁ and the edge SP₁ red. cheapest unmarked (uncoloured) edge in the graph that doesn't close a coloured circuit. Mark this edge with same colour of Step 1.

• Step 2

  Find the nearest uncoloured neighbour to the red subgraph (i.e., the closest vertex to any red vertex). Mark it and the edge connecting the vertex to the red subgraph in red.

• Step 3

  Repeat Step 2 until all vertices are marked red. The red subgraph is a minimum spanning tree.

• Interactive Prim's Algorithm

 

Given the graph G below

---

1. Find a spanning subgraph of G and draw it below.

  

 

2. Draw all the different spanning trees of G

 

 

 

 

3. Of those you had in # 2, which one(s) is (are) minimum spanning trees. (i.e., those that have a minimum sum of their weighted edges.)

 

 

---

Given the weighted graph below:

---

1. Use Kruskal's algorithm to find a minimum spanning tree and indicate the edges in the graph shown below: Indicate on the edges that are selected the order of their selection.

 

 

 

 

 

2. Use Prim's algorithm to find the minimum spanning tree and indicate the edges in the graph shown below. Indicate on the edges that are selected the order of their selection.