Minimum Spanning Tree

Minimum Spanning Tree

° 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).

---

Kruskal’s Algorithm

• 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.

---

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.