> For the complete documentation index, see [llms.txt](https://phitron.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://phitron.gitbook.io/algorithm/dsu-cycle-detection-mst/_-mst-kruskals-algorithm.md).

# মডিউল ১১\_৪ঃ MST এর জন্য Kruskals Algorithm

Kruskals Algorithm দিয়ে বের করবো কোন একটি গ্রাফের Minimum Spanning Tree। 

Undirected weighted গ্রাফের ইনপুট

**5 7**\ <mark style="color:blue;">0 2 3</mark>\ <mark style="color:blue;">0 1  2</mark>\ <mark style="color:blue;">3 4 6</mark>\ <mark style="color:blue;">0 3 3</mark>\ <mark style="color:blue;">2 1 7</mark>\ <mark style="color:blue;">2 4 9</mark>\ <mark style="color:blue;">1 4 5</mark>

গ্রাফটি দেখতে এমন হবেঃ&#x20;

<figure><img src="/files/X4smSxba6AfZTpfnq6tO" alt="" width="375"><figcaption></figcaption></figure>

প্রথমে আমরা সব edge গুলোকে sort করে নিব weight এর ভিত্তিতে। তখন আমাদের edge list টি এইরকম হবে।&#x20;

<figure><img src="/files/qMLaXKYY7mp6EdjjOoyM" alt="" width="268"><figcaption></figcaption></figure>

**শুরুতে গ্রাফ এবং গ্রুপগুলোর অবস্থা এইরকম হবেঃ**

<figure><img src="/files/BSx31vtLjLT7ROxyUE0x" alt=""><figcaption></figcaption></figure>

***

এখন  0 , 1 cost=2 edge এর  0 এর লিডার হচ্ছে  0 এবং 1  এর লিডার হচ্ছে 1 । যেহেতু লিডার অমিল তাই  0 , 1 কে union করতে পারবো।&#x20;

<figure><img src="/files/fkrFWvnupApFC50GSSmp" alt=""><figcaption></figcaption></figure>

***

এখন  0 , 2 cost=3 edge এর  0 এর লিডার হচ্ছে  0 এবং 2  এর লিডার হচ্ছে 2 । যেহেতু লিডার অমিল তাই  0 , 2 কে union করতে পারবো।&#x20;

<figure><img src="/files/NPtvQv3aSoNFiSJTmLnE" alt=""><figcaption></figcaption></figure>

***

এখন  0 , 3 cost=3 edge এর  0 এর লিডার হচ্ছে  0 এবং 3  এর লিডার হচ্ছে 3 । যেহেতু লিডার অমিল তাই  0 , 3 কে union করতে পারবো।&#x20;

<figure><img src="/files/OAkwfnIWtppymODSytrB" alt=""><figcaption></figcaption></figure>

***

এখন  1 , 4 cost=5 edge এর  1 এর লিডার হচ্ছে  0 এবং 4  এর লিডার হচ্ছে 4 । যেহেতু লিডার অমিল তাই  1 , 4 কে union করতে পারবো।&#x20;

<figure><img src="/files/G5z8HVKs7oR089eDUkh3" alt=""><figcaption></figcaption></figure>

***

এখন  3 , 4 cost=6 edge এর  3 এর লিডার হচ্ছে  0 এবং 4  এর লিডার হচ্ছে 0 । যেহেতু লিডার মিল তাই  3 , 4 কে union করতে পারবো না।&#x20;

<figure><img src="/files/WVoFQXOuzP7Qd7kYSS27" alt=""><figcaption></figcaption></figure>

***

এখন  2 , 1 cost=7 edge এর  2 এর লিডার হচ্ছে  0 এবং 1  এর লিডার হচ্ছে 0 । যেহেতু লিডার মিল তাই  2 , 1 কে union করতে পারবো না।&#x20;

<figure><img src="/files/itS61qDtlsrwneKEdyfl" alt=""><figcaption></figcaption></figure>

***

এখন  2 , 4 cost=9 edge এর  2 এর লিডার হচ্ছে  0 এবং 4  এর লিডার হচ্ছে 0 । যেহেতু লিডার মিল তাই  2 , 4 কে union করতে পারবো না।&#x20;

<figure><img src="/files/3LYH9XsNtMYDTI6YuIYs" alt=""><figcaption></figcaption></figure>

Minimum Spanning Tree টি হবে।

<figure><img src="/files/EqSJR4yzVXogAk5tRu9V" alt=""><figcaption></figcaption></figure>

এইভাবে Kruskals Algorithm ব্যবহার করে DSU সাহায্যে Minimum Spanning Tree বানানো যায়।&#x20;