[go: up one dir, main page]
Scribd
Upload
86 views28 pages

DAA PPT -Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subgraph that connects all vertices of a weighted graph with the minimum total edge weight, applicable in various fields such as network design and clustering. Two primary algorithms for finding an MST are Kruskal's, which avoids cycles by selecting the smallest edges, and Prim's, which builds the tree incrementally by adding the minimum weight edge from the existing tree. Both algorithms differ in their approach and efficiency based on the graph's density and structure.

Uploaded by

Fire Ice Yt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
86 views28 pages

DAA PPT -Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subgraph that connects all vertices of a weighted graph with the minimum total edge weight, applicable in various fields such as network design and clustering. Two primary algorithms for finding an MST are Kruskal's, which avoids cycles by selecting the smallest edges, and Prim's, which builds the tree incrementally by adding the minimum weight edge from the existing tree. Both algorithms differ in their approach and efficiency based on the graph's density and structure.

Uploaded by

Fire Ice Yt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 28

Minimum Spanning Tree

Introduction to Minimum
Spanning Tree (MST)
 A tree is a connected graph with no cycles.
 A Spanning Tree is a subgraph of G that has all
vertices of G & is a tree.
 A Minimum Spanning Tree of a weighted Grapg G
is a Spanning Tree of G whose edges sum to
minimum weight.

 Graph : G(V,E)
 Spanning Tree : G’(V, E’)
Introduction to Minimum
Spanning Tree (MST)
 A Minimum Spanning Tree (MST) of a graph is
a spanning tree with the minimum total edge
weight.
 Applicable in network design, clustering, and
approximation algorithms.
 A graph can have multiple MSTs but with the
same total weight.
 MST is formed from a connected, undirected,
and weighted graph.
Properties of MST
 The MST of a graph connects all
vertices with the minimum possible
total edge weight.
 No cycles are allowed & it can’t be
disconnected
 The number of edges in MST = V - 1
(where V is the number of vertices).
 It follows Greedy Strategy.
MST Algorithms
 Kruskal's Algorithm

 Prim's Algorithm
A Networking Problem

Problem: The vertices represent 8 regional data centers which


need to be connected with high-speed data lines. Feasibility
studies show that the links illustrated above are possible, and the
cost in millions of dollars is shown next to the link. Which links
should be constructed to enable full communication (with relays
allowed) and keep the total cost minimal.
Kruskal’s Algorithm (Avoid Cycles)

 Sort all edges in ascending order of


weight.
 Pick the smallest edge that does not
form a cycle.
 Repeat until MST contains V - 1 edges.
Kruskal – Step 1
Kruskal – Step 2
Kruskal – Step 3
Kruskal – Step 4
Kruskal – Step 5
Kruskal – Step 6
Why Avoiding Cycles Matters

Up to this point, we have simply taken the


edges in order of their weight. But now we
will have to reject an edge since it forms a
cycle when added to those already chosen.
Forms a Cycle

So we cannot take the blue edge having weight 55.


Kruskal – Step 7 DONE!!

Weight (T) = 23 + 29 + 31 + 32 + 47 + 54 + 66 = 282


Prim’s Algorithm (Build Tree)

 Start with any vertex.

 Select the minimum weight edge connecting


an included vertex to an excluded vertex.

 Add the new vertex to the MST.

 Repeat until all vertices are included.


Prim’s Algorithm (Build Tree)

 Build a tree one vertex at a time.


 Start with a trivial one point tree T.
 Then add the edge of minimum weight among those with
one endpoint in T and the other not in T.
Prim – Step 1
Prim – Step 2
Prim – Step 3
Prim – Step 4
Prim – Step 5
Prim – Step 6
Prim – Step 7 Done!!

Weight (T) = 23 + 29 + 31 + 32 + 47 + 54 + 66 = 282


Comparison of Prim’s and
Kruskal’s Algorithm
Kruskal’s
Feature Prim’s Algorithm
Algorithm
Approach Greedy Greedy
Best for Dense Graphs Sparse Graphs
Data Structure
Priority Queue Disjoint Set
Used
Complexity O(E logV) O(E logE)
Selects minimum
Selects the
edge connecting
Selection Criteria smallest edge
MST to a new
globally
vertex
Works like Works like sorting
Execution Style
Dijkstra’s Algorithm edges first
Comparison of Prim’s and
Kruskal’s Algorithm
Kruskal’s
Feature Prim’s Algorithm
Algorithm
Graphs with many Graphs with fewer
Works Well On
edges edges
No cycle formation Requires cycle
Cycle Formation as it grows tree checking with
incrementally union-find
Processes edges Processes edges in
Edge Processing
connected to MST sorted order
Note: Add Example
for both
Data Structure and
Computational Issues

 Implementing Kruskal’s Algorithm seems to require


sorting the edges by weight as a preliminary step. Are
there alternatives?
 Implementing Prim’s algorithm seems to require
keeping track of the edge of minimum weight with one
endpoint in a component, but the components are
changing. How does one do this?

You might also like