মডিউল ১১_৪ঃ MST এর জন্য Kruskals Algorithm
Kruskals Algorithm দিয়ে বের করবো কোন একটি গ্রাফের Minimum Spanning Tree।
Undirected weighted গ্রাফের ইনপুট
5 7 0 2 3 0 1 2 3 4 6 0 3 3 2 1 7 2 4 9 1 4 5
গ্রাফটি দেখতে এমন হবেঃ
প্রথমে আমরা সব edge গুলোকে sort করে নিব weight এর ভিত্তিতে। তখন আমাদের edge list টি এইরকম হবে।
শুরুতে গ্রাফ এবং গ্রুপগুলোর অবস্থা এইরকম হবেঃ
এখন 0 , 1 cost=2 edge এর 0 এর লিডার হচ্ছে 0 এবং 1 এর লিডার হচ্ছে 1 । যেহেতু লিডার অমিল তাই 0 , 1 কে union করতে পারবো।
এখন 0 , 2 cost=3 edge এর 0 এর লিডার হচ্ছে 0 এবং 2 এর লিডার হচ্ছে 2 । যেহেতু লিডার অমিল তাই 0 , 2 কে union করতে পারবো।
এখন 0 , 3 cost=3 edge এর 0 এর লিডার হচ্ছে 0 এবং 3 এর লিডার হচ্ছে 3 । যেহেতু লিডার অমিল তাই 0 , 3 কে union করতে পারবো।
এখন 1 , 4 cost=5 edge এর 1 এর লিডার হচ্ছে 0 এবং 4 এর লিডার হচ্ছে 4 । যেহেতু লিডার অমিল তাই 1 , 4 কে union করতে পারবো।
এখন 3 , 4 cost=6 edge এর 3 এর লিডার হচ্ছে 0 এবং 4 এর লিডার হচ্ছে 0 । যেহেতু লিডার মিল তাই 3 , 4 কে union করতে পারবো না।
এখন 2 , 1 cost=7 edge এর 2 এর লিডার হচ্ছে 0 এবং 1 এর লিডার হচ্ছে 0 । যেহেতু লিডার মিল তাই 2 , 1 কে union করতে পারবো না।
এখন 2 , 4 cost=9 edge এর 2 এর লিডার হচ্ছে 0 এবং 4 এর লিডার হচ্ছে 0 । যেহেতু লিডার মিল তাই 2 , 4 কে union করতে পারবো না।
Minimum Spanning Tree টি হবে।
এইভাবে Kruskals Algorithm ব্যবহার করে DSU সাহায্যে Minimum Spanning Tree বানানো যায়।
Last updated