Minimum Spanning Tree (MST) - Kruskal और Prim’s Algorithms

Graphs में Minimum Spanning Tree (MST) एक बहुत ही महत्वपूर्ण concept है, जिसका उपयोग weighted undirected graphs में किया जाता है। एक MST एक ऐसा subgraph होता है जिसमें सभी vertices connected होते हैं और इसका कुल edge weight सबसे कम होता है।

दो सबसे popular algorithms जो Minimum Spanning Tree बनाने के लिए इस्तेमाल होते हैं, वे हैं Kruskal’s Algorithm और Prim’s Algorithm। आइए इन दोनों algorithms को detail में समझते हैं।

Minimum Spanning Tree (MST) क्या है?

Minimum Spanning Tree एक spanning tree है जो graph के सभी vertices को connect करता है और इसका total weight minimum होता है।

1. Graph में N nodes होते हैं, तो spanning tree में N-1 edges होंगे।

2. एक graph में कई spanning trees हो सकते हैं, लेकिन MST वह spanning tree है जिसका edge weight सबसे कम है।

Kruskal’s Algorithm in Hindi

Kruskal’s Algorithm MST बनाने के लिए एक greedy algorithm है। यह सभी edges को उनके weight के आधार पर sort करता है और सबसे छोटे weight वाली edges को select करता है, जब तक कि N-1 edges select नहीं हो जाते।

Kruskal’s Algorithm की Process:

1. Sort सभी edges को ascending order में उनके weight के अनुसार।

2. एक-एक करके सबसे छोटा edge select करें।

3. यदि selected edge cycle नहीं बनाता है, तो उसे spanning tree में add करें।

4. यह process तब तक जारी रहती है, जब तक N-1 edges select नहीं हो जाते।

Kruskal’s Algorithm का Example:

मान लीजिए हमारे पास एक weighted graph है:

A --3-- B

|           |

2          4

|           |

C --1-- D

Step-by-step Kruskal’s Algorithm:

1. Sort edges by weight: (C-D, 1), (A-C, 2), (A-B, 3), (B-D, 4)

2. Add edges: (C-D) → (A-C) → (A-B)

Final MST:

A --3-- B

|       

2       

|       

C --1-- D

Kruskal’s Algorithm के Advantages:

1. Simple और आसानी से implement किया जा सकता है।

2. Sparse graphs में अच्छा काम करता है।

Kruskal’s Algorithm के Disadvantages:

1. Sorting की वजह से इसका time complexity O(E log E) होती है, जहां E edges की संख्या है।

Prim’s Algorithm in Hindi

Prim’s Algorithm भी एक greedy approach को follow करता है, लेकिन यह vertex-based है। यह एक vertex से शुरू करता है और हमेशा connected components से सबसे कम weight वाला edge जोड़ता है।

Prim’s Algorithm की Process:

1. एक random vertex से शुरू करें।

2. Minimum weight वाला edge चुनें जो MST में already शामिल नहीं है।

3. इस process को तब तक दोहराएं, जब तक सभी vertices MST में शामिल नहीं हो जाते।

Prim’s Algorithm का Example:

उसी weighted graph का उपयोग करें:

A --3-- B

|           |

2         4

|           |

C --1-- D

Prim’s Algorithm का process:

1. Start with vertex A.

2. Select edge (A-C, 2).

3. Select edge (C-D, 1).

4. Select edge (A-B, 3).

Final MST:

A --3-- B

|       

2       

|       

C --1-- D

Prim’s Algorithm के Advantages:

1. Dense graphs में बेहतर performance देता है।

2. Graph की connectivity maintain करते हुए step-by-step MST को build करता है।

Prim’s Algorithm के Disadvantages:

1. Sparse graphs में Kruskal’s algorithm से slow हो सकता है।

Conclusion

Minimum Spanning Tree बनाना Kruskal और Prim’s Algorithms के जरिए आसान हो जाता है। Kruskal’s algorithm edge-based approach को follow करता है और sparse graphs में अच्छा काम करता है, जबकि Prim’s algorithm vertex-based approach अपनाता है और dense graphs में efficient है। आपकी graph की requirements और characteristics के आधार पर आप सही algorithm का चयन कर सकते हैं।