AURORA DEEMED UNIVERSITY
Design and Analysis of Algorithms
LEARNING GROUP- 3
Demonstration of Minimum Spanning Tree
Presented By:
Course Instructor: P. Ramesh, 231U1R2001, AIML 3A
Dr. Chandrashekar K, Associate Professor S. Lakshmi Priya, 231U1R2005, AIML 3A
Department of Computer Science Engineering K.Shritha sri, 231U1R2018, AIML 3A
Outline ✓ Introduction
✓ Definition of Spanning Tree
✓ Properties and Example
✓ Minimum Spanning Tree (MST) &
Example
✓ Algorithms for MST (Prim’s & Kruskal’s)
✓ Comparison of Prim’s vs Kruskal’s
✓ Applications of Spanning Tree
✓ Conclusion
Introduction
• Undirected Graph
An undirected graph is a collection of points (vertices) connected by lines (edges)
that do not have a specific direction, meaning each connection can be traversed in
both directions.
• Connected Graph
A connected graph is a graph where a path exists between any two vertices, allowing
travel from any point to any other point by following the edges
Spanning Tree
What is a Spanning Tree?
A spanning tree is a subset of Graph G, such that all the vertices are connected using
minimum possible number of edges. Hence, a spanning tree does not have cycles and a
graph may have more than one spanning tree.
Properties of Spanning Tree
•A spanning tree is a subset of a connected graph G.
•A spanning tree does not exist for a disconnected graph.
•A spanning tree always has n − 1 edges, where n = number of vertices.
•A spanning tree does not contain any cycle or loop.
•A spanning tree is minimally connected → removing one edge disconnects the graph.
•A spanning tree is maximally acyclic → adding one more edge creates a cycle.
•There can be more than one spanning tree for a connected graph.
•For a complete graph with n vertices:
•The maximum number of spanning trees = n^(n−2) (Cayley’s formula).
•Example: n = 5
→ Number of spanning trees = 5^(5−2)
→ 5^3 = 125 spanning trees
A spanning tree can be constructed by removing (E − n + 1) edges, where E = number
of edges.
Example of Spanning Tree
Minimum Spanning Tree (MST)
A minimum spanning tree is a subgraph of an undirected weighted graph
G, such that
• it is a tree (i.e., it is acyclic)
• it covers all the vertices V
• contains |V| - 1 edges
• the total cost associated with tree edges is the
minimum among all possible spanning trees
• not necessarily unique.
Minimum-cost spanning trees
• Suppose you have a connected undirected graph with a weight (or cost)
associated with each edge.
• The cost of a spanning tree would be the sum of the costs of its edges.
• A minimum-cost spanning tree is a spanning tree that has the lowest cost.
Finding minimum spanning trees
• There are two basic algorithms for finding minimum-cost spanning
trees, and both are greedy algorithms.
• Kruskal’s algorithm: Start with no nodes or edges in the spanning tree,
and repeatedly add the cheapest edge that does not create a cycle
• Here, we consider the spanning tree to consist of edges only
• Prim’s algorithm: Start with any one node in the spanning tree, and
repeatedly add the cheapest edge, and the node it leads to, for which the
node is not already in the spanning tree.
• Here, we consider the spanning tree to consist of both nodes and edges
Prim’s Algorithm
Steps of Prim’s Algorithm
1.Start with any vertex as the root of the spanning tree.
2.From the vertices included in the tree, choose the edge with the smallest
weight that connects to a new vertex.
3.Add that edge and vertex to the spanning tree.
4.If the chosen edge creates a cycle, discard it and pick the next smallest edge.
5.Repeat steps 2–4 until all vertices are included and the spanning tree has (n −
1) edges.
Kruskal’s algorithm
Steps of Kruskal’s Algorithm
1.Sort all edges of the graph in non-decreasing order of their weights.
2.Pick the smallest edge. If it does not form a cycle with already selected
edges, include it in the spanning tree.
3.If adding the edge forms a cycle, discard it.
4.Repeat steps 2 and 3 until the spanning tree contains exactly (n − 1)
edges, where n is the number of vertices.
After Applying Kruskal's Algorithm
Kruskal’s vs Prim’s Algorithm
Point Kruskal’s Algorithm Prim’s Algorithm
Based on Works on edges Works on vertices
Approach Greedy by choosing smallest edge Greedy by growing from a vertex
Can work on disconnected graphs (gives
Graph type Needs connected graph
forest)
Data Structure Disjoint Set / Union-Find Priority Queue / Min Heap
Sorting Needs edge sorting No sorting needed
Best for Sparse graphs (few edges) Dense graphs (many edges)
O(E log V) (with heap) or O(V²) (with
Time Complexity O(E log V)
adjacency matrix)
Applications
Cluster analysis using MST in ML
computer networks diagram
road network
Conclusion
•A Spanning Tree connects all vertices of a graph with the minimum number of edges and no cycles.
•A Minimum Spanning Tree (MST) further ensures the lowest possible total edge weight, making it very
useful in real-life optimization problems.
•Prim’s and Kruskal’s algorithms are two efficient methods to find MST, and both guarantee the same result.
•MST has wide applications in network design, transportation, clustering, and optimization problems,
proving its importance in both computer science and real-world systems.
THANK YOU
