# মডিউল ১১\_৪ঃ 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="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2FCWrvWDW8QWDnTh0hMvv6%2Fimage.png?alt=media&#x26;token=2e702a05-4045-404d-bce8-23215c38b3c6" alt="" width="375"><figcaption></figcaption></figure>

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2FdTsgpKJwwJ5aJjt5GPVS%2Fimage.png?alt=media&#x26;token=1979ba8d-38f8-48a6-b224-287a800587b0" alt="" width="268"><figcaption></figcaption></figure>

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2Fp7rEb9l4z7b2OqV04NrN%2Fimage.png?alt=media&#x26;token=deae1658-acbc-4b33-a341-d18dfb057de5" alt=""><figcaption></figcaption></figure>

***

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2FzTvISLCkamaiQpOTQmbd%2Fimage.png?alt=media&#x26;token=9a85de94-2566-45b2-b440-3f4762314e0d" alt=""><figcaption></figcaption></figure>

***

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2FH1HiuSIU4AiRKPsf9btR%2Fimage.png?alt=media&#x26;token=209fc3f5-d9d8-4689-a345-8232a0a30e0b" alt=""><figcaption></figcaption></figure>

***

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2FtAJIbGA46CXaKv90noxS%2Fimage.png?alt=media&#x26;token=5d4f9799-30e3-44e6-9eb4-169784e0e699" alt=""><figcaption></figcaption></figure>

***

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2FlKOVeG3FhNtiOPRJ5Ddc%2Fimage.png?alt=media&#x26;token=a77bbd4b-19f6-494e-868c-3e2b80361959" alt=""><figcaption></figcaption></figure>

***

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2FHjgOxrzA69UpwnPf8rAq%2Fimage.png?alt=media&#x26;token=1f6d30cd-016c-4ccc-bb92-6d3eed088fc1" alt=""><figcaption></figcaption></figure>

***

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2F1kFxXqUmGhFlYLzmUbNQ%2Fimage.png?alt=media&#x26;token=5156f945-097f-4216-9ec6-509eaf328752" alt=""><figcaption></figcaption></figure>

***

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

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2F3KFSmaHZ7kGYi0zHwLaG%2Fimage.png?alt=media&#x26;token=afd88a46-30d2-47eb-a87b-7e85c2e5a0cc" alt=""><figcaption></figcaption></figure>

Minimum Spanning Tree টি হবে।

<figure><img src="https://1548341763-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjliRFwU9cGQFGljHYgOZ%2Fuploads%2FGFuW5CbuDJPqOdo0bJVi%2Fimage.png?alt=media&#x26;token=77090471-64e0-4023-a240-e9b2301b0fd1" alt=""><figcaption></figcaption></figure>

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