Minimum Spanning Tree

Spanning Tree

It is a subgraph that connects all vertuces of the graph with no cycles and exactly n-1 edges.

Points to Remember:

• All Nodes
• Connected
• No Cycles
• (n-1) edges

Cost: 7 + 2 + 6 + 3 + 8 = 26

Minimum Spanning Tree

Spaaning Tree

Minimum Cost Spanning Tree:5 + 1 + 2 + 3 + 8 = 19

Why Minimum Spanning Tree?

• Minimum edges to connect a network.
• No Cycles.
• Simplify the Structure.

Use Case:

• Network
• Routing
• Broadcasting
• Infrastructure design (roads, pipes, electricity)

Minimum Spanning Tree Algorithms

This will be covered in upcoming videos

• Prim's Algorithm
• Kruskal's Algorithm