Minimum Spanning Tree (MST)
Minimum Spanning Tree (MST) एक ऐसा subtree है, जो किसी connected, undirected, weighted graph के सभी vertices को minimum possible total weight के साथ connect करता है — और जिसमें किसी भी तरह की cycle नहीं होती।
Key Points
- Graph का प्रकार : Graph हमेशा Connected + Undirected + Weighted होना चाहिए।
- Edges की संख्या : MST में हमेशा V – 1 edges होते हैं (जहाँ V = number of vertices)।
- Minimum Total Weight : MST पूरे graph को सबसे कम possible weight में connect करता है।
- No Cycles : MST हमेशा acyclic (cycle-free) होता है।
- Algorithms to Find MST : Two most popular algorithms –
- Prim’s Algorithm
- Kruskal’s Algorithm
Why MST Matters? (MST क्यों ज़रूरी है?)
Minimum Spanning Tree (MST) इसलिए ज़रूरी है, क्योंकि यह किसी भी network या graph-based system को minimum cost, minimum resources, और zero wastage के साथ connect करने का सबसे efficient तरीका देता है।
1. Cost-Optimized Network Construction
- MST किसी भी connected, weighted graph के लिए ऐसा structure प्रदान करता है जो सभी vertices को minimum total weight के साथ जोड़ता है।
- यह network design में optimal cost efficiency सुनिश्चित करता है।
2. Reduces Redundant Connections
- MST graph से सभी unnecessary edges (cycles) हटाकर एक minimal, acyclic structure बनाता है।
- इससे network की structural simplicity और efficiency बढ़ती है।
3. Optimal Infrastructure Layout Generation
- MST large-scale infrastructures (जैसे transportation, pipeline, communication networks) के लिए minimum-edge layout तैयार करने का आधार प्रदान करता है, जो mathematical रूप से cost-efficient होता है।
4. Ensures Loop-Free Topology
- MST का acyclic nature इसे ऐसे systems के लिए आदर्श बनाता है, जहाँ loop-free connectivity आवश्यक होती है, जैसे विभिन्न communication और routing systems।
5. Underlying Principle in Network Protocols
- Several networking frameworks (जैसे STP protocols) MST के सिद्धांत पर आधारित होते हैं, जिससे network में loop prevention और reliable communication सुनिश्चित किया जा सके।
MST Terminology
| Term (शब्द) | Meaning / Definition |
|---|---|
| Spanning Tree | यह Graph का ऐसा subset होता है जिसमें सभी Vertices शामिल होते हैं, Edges = V – 1 होती हैं और कोई Cycle नहीं बनती। यानी पूरा graph बिना loop के connect होता है। |
| Minimum Spanning Tree (MST) | वह Spanning Tree जिसका Total Weight Minimum हो। यानी सबसे कम cost में सभी vertices को connect करने वाला tree। |
| Cut | किसी Graph को दो भागों में विभाजित करने की प्रक्रिया को Cut कहते हैं। MST algorithms में यह concept बहुत important है। |
| Cut-Set | Cut बनने पर उन सभी Edges का सेट जो दोनों हिस्सों को आपस में जोड़ सकती हैं, उसे Cut-Set कहते हैं। |
| Safe Edge | वह Edge जिसे current Tree में जोड़ने पर Cycle नहीं बनती और जो MST को सही दिशा में आगे बढ़ाने में मदद करती है। Kruskal और Prim दोनों algorithms Safe Edge को चुनते हैं। |
How Minimum Spanning Tree (MST) Works?
MST कैसे काम करता है?
1. Identify All Edges
- Graph के सभी vertices + edges को observe किया जाता है।
- हर edge के साथ उसका weight दिया होता है (cost, distance, time आदि)।
- यही MST बनाने की initial base information होती है।
2. Select Minimum-Weight Edge
- सबसे पहले हमेशा minimum weight edge pick की जाती है।
- यह MST का main greedy rule है।
- Reason : कम weight चुनने से overall network cost minimize हो जाता है।
3. Cycle Checking
- हर चुनी गई edge को add करने से पहले check किया जाता है कि cycle बनेगी या नहीं।
- If Cycle = YES → Reject Edge
- If Cycle = NO → Accept Edge (Safe Edge)
- Cycle detection के लिए अक्सर Union–Find / Disjoint Set का use किया जाता है।
4. Add Safe Edge
- जो edge cycle नहीं बनाती, उसे Safe Edge कहा जाता है।
- Safe Edge को MST में add किया जाता है।
- MST हमेशा Tree होना चाहिए → इसलिए loop/cycle कभी allow नहीं है।
5. Repeat Until MST is Complete
- अगली minimum-weight edge pick करो → cycle check करो → safe हो तो add करो।
- यह process तब तक चलता है जब तक MST में (V – 1) edges न हो जाएँ।
- जैसे ही V – 1 edges complete → MST ready।
MST Algorithms
MST बनाने के दो सबसे popular algorithms हैं :
- Kruskal’s Algorithm
- Prim’s Algorithm
1. Kruskal’s Algorithm
“Kruskal’s Algorithm एक Greedy algorithm है, जो किसी connected, undirected और weighted graph का Minimum Spanning Tree (MST) बनाता है। यह algorithm सभी edges को ascending order (छोटे से बड़े weight) में sort करके काम करता है और cycle detect करने के लिए Disjoint Set (Union–Find) structure का उपयोग करता है।”
Step-by-Step Process
Step 1 : List All Edges
Graph की सभी edges को उनकी weight सहित लिखें।
Step 2 : Sort Edges by Weight
सभी edges को ascending order में sort करें।
Step 3 : Initialize Disjoint Set / Union-Find
- हर vertex को अलग-अलग set मानते हैं।
- यह cycle detect करने में मदद करता है।
Step 4 : Pick Smallest Edge (One-by-One)
- Sorted list में से सबसे छोटी weight वाली edge चुनें।
- Check करें :
- अगर cycle नहीं बनती → Add to MST
- अगर cycle बनती → Skip (Reject)
Step 5 : Apply Union Operation
Accepted edge होने पर दोनों vertices को union() करके same set में merge करें।
Step 6 : Stop Condition (English)
जब MST में V – 1 edges हो जाएँ → Stop.
(V = number of vertices)
Example with Diagram
(A)
/ \
6 / \ 2
/ \
(B) —3— (C)
| |
1 5
| |
(D) —2— (E)
Edges (with weights) :
- (B, D, 1)
- (A, C, 2)
- (D, E, 2)
- (B, C, 3)
- (C, E, 5)
- (A, B, 6)
Sorted edges (ascending)
- (B, D) — 1
- (A, C) — 2
- (D, E) — 2
- (B, C) — 3
- (C, E) — 5
- (A, B) — 6
Iterations (step-by-step)
- Step 1 : Pick (B, D,1).
find(B)!= find(D)→ accept. MST edges : {(B,D)} - Step 2 : Pick (A, C,2).
find(A)!= find(C)→ accept. MST : {(B,D),(A,C)} - Step 3 : Pick (D, E,2).
find(D)= B,find(E)= E→ accept. MST : {(B,D),(A,C),(D,E)} - Step 4 : Pick (B, C,3).
find(B)= B,find(C)= A→ different → accept. MST now has 4 edges.- If V = 5 → need V−1 = 4 edges → stop.
- Final MST edges : (B,D,1), (A,C,2), (D,E,2), (B,C,3)
- Total weight = 1 + 2 + 2 + 3 = 8
2. Prim’s Algorithm
Prim’s Algorithm एक Greedy Algorithm है, जो MST बनाने के लिए vertex-based approach अपनाता है। यह algorithm graph के किसी भी एक vertex से start करता है। इसके बाद यह एक-एक करके सबसे नज़दीकी (minimum-weight) edge को add करता जाता है, जब तक सभी vertices connect न हो जाएँ।
Step-by-Step Process
Step 1. Select Any Start Vertex (Start Node चुनें)
- Graph के किसी भी एक vertex से algorithm शुरू होता है।
- इस vertex को Visited Set (VS) में add कर दिया जाता है।
Step 2. Collect All Adjacent Edges (Nearby Edges List करें)
- Visited vertex(s) से जुड़ी सभी adjacent edges को consider करें।
- सिर्फ वही edges valid हैं जो किसी Unvisited vertex की ओर जाती हों।
Step 3. Choose Minimum Weight Edge
- सभी valid adjacent edges में से minimum-weight edge choose करें।
- यह हमेशा एक Safe Edge होती है क्योंकि यह cycle नहीं बनाती।
Step 4. Add Selected Edge to MST
- चुनी गई edge को MST में add करें।
- जिस vertex तक यह edge जाती है उसे Visited Set में include करें।
Step 5. Update Edge List
- Newly added vertex से निकलने वाली edges को edge list में add करें।
- Already-visited nodes की ओर जाने वाली edges को ignore कर दें।
Step 6. Repeat Until All Vertices Are Covered
- Minimum edge → Add to MST → Add vertex → Update list
- यह loop तब तक चलता है जब तक सभी vertices Visited न हो जाएँ।
Step 7. Stop Condition – (V – 1 edges)
जब MST में V – 1 edges complete हो जाएँ →
Prim’s Algorithm stop हो जाता है।
Example with Diagram
A
2 / \ 3
B——C
1 \ / 4
D
Edges with weights :
- A–B = 2
- A–C = 3
- B–C = 2
- B–D = 1
- C–D = 4
Step-by-Step
Step 1 : Start at A
- Visited Set = {A}
- Adjacent edges: A–B = 2, A–C = 3
- Pick minimum edge → A–B (2)
A
\
B
Step 2 : Update Visited = {A, B}
- New edges : B – C = 2, B – D = 1, A – C = 3
- Pick minimum edge → B – D (1)
A
\
B
\
D
Step 3 : Update Visited = {A, B, D}
- New edges : D – C = 4, B – C = 2, A – C = 3
- Pick minimum edge → B – C (2)
A
\
B
/ \
D C
Step 4 : MST Complete
- Visited = {A, B, C, D}
- Number of edges = V – 1 = 3 (V=4)
- Stop
Final MST edges :
- A – B = 2
- B – D = 1
- B – C = 2
Total Weight = 5
Applications (उपयोग)
- Network Design : MST का उपयोग telecommunication networks, computer networks, electrical grids आदि के लिए किया जाता है।
- Road and Railway Construction : Cities या towns को minimum length of roads/railways से connect करने के लिए MST use होता है।
- Electrical Circuit / Power Grid DesignDefinition : Power stations और consumers को minimum wiring/cable cost में connect करने के लिए MST apply किया जाता है।
- Clustering in Data Mining : Data points को group करने के लिए graph में MST बनाकर similar nodes cluster किए जाते हैं।
- Approximation Algorithms : MST का use Traveling Salesman Problem (TSP) जैसे complex problems के approximate solution में होता है।
- Network Reliability and Optimization : MST से redundancy कम करके reliable network design किया जा सकता है।
- Computer Graphics / Image Processing : MST का use image segmentation और object recognition में किया जाता है।
Advantages (लाभ)
1. Cost Reduction
- MST का main benefit है, कि network को minimum cost में connect किया जा सकता है।
- Example : Telecom, Electrical wiring, Road network।
2. Efficient Network Design (Efficient नेटवर्क डिजाइन)
- MST से network design efficient और optimized बनता है।
- कम redundant connections, केवल necessary edges connect होती हैं।
3. Simplicity
- MST simple graph structure देता है : connected + cycle-free।
- Network planning और resource allocation आसान हो जाता है।
4. Basis for Other Algorithms
- MST को use करके approximation algorithms जैसे Traveling Salesman Problem (TSP) solve किया जा सकता है।
- Clustering, image processing, network optimization में भी MST foundational है।
5. Reliability & Predictability
- MST structured और minimal design होने के कारण network predictable और reliable रहता है।
Disadvantages (सीमाएँ)
1. Single Solution Limitation
- MST हमेशा minimum cost वाला tree देता है।
- अगर network में multiple objectives हों (like redundancy, load balancing), MST पूरा satisfy नहीं करता।
2. Not Fault – Tolerant
MST में redundant paths नहीं होते → किसी edge failure से network break हो सकता है।
3. Static Network Assumption
- MST assume करता है कि graph static है।
- Dynamic networks (like mobile networks) में MST बार-बार update करना पड़ेगा।
4. Ignores Other Factors
- MST केवल weight/cost पर focus करता है।
- Real-life में distance, bandwidth, terrain, maintenance cost जैसे factors भी matter करते हैं।
5. Not Always Unique
- अगर कुछ edges का weight equal हो, तो multiple MSTs possible हैं।
- Practical planning में ambiguity create कर सकता है।
