Tree

Minimum Spanning Tree Algorithms

---

Definition:-

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.

---

Definitions:-

° 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 1Find 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 2Find the cheapest unmarked (uncoloured) edge in the graph that doesn't close a coloured or red circuit. Mark this edge red.
• Step 3Repeat 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 0Pick any vertex as a starting vertex. (Call it S). Mark it with any given colour, say red.
• Step 1Find 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 2Find 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 3Repeat Step 2 until all vertices are marked red. The red subgraph is a minimum spanning tree.


• Interactive Prim's Algorithm