ক্রাসকাল'স অ্যালগরিদম (Kruskal’s Algorithm)
ক্রাসকাল'স অ্যালগরিদম একটি জনপ্রিয় গ্রাফ অ্যালগরিদম যা একটি গাছের (tree) মতো কাঠামো তৈরি করার জন্য ব্যবহৃত হয়, যা মিনিমাম স্প্যানিং ট্রি (MST) নির্মাণ করে। এটি মূলত একটি ওজনযুক্ত গ্রাফের জন্য কাজ করে এবং সমস্ত ভেরটেক্সকে অন্তর্ভুক্ত করে, যখন মোট এজের ওজন সর্বনিম্ন হয়।
অ্যালগরিদমের কাজ করার পদ্ধতি
- এজ নির্বাচন:
- গ্রাফের সমস্ত এজগুলিকে তাদের ওজনের ভিত্তিতে সাজান (ছোট থেকে বড়)।
- সংযোগ:
- প্রতিটি এজ নিয়ে কাজ করুন এবং এটি MST-তে যুক্ত করুন যদি এটি কোনও সাইকেল তৈরি না করে।
- সংযুক্ত কম্পোনেন্ট ট্র্যাকিং:
- একটি ইউনিয়ন-ফাইন্ড ডেটা স্ট্রাকচার ব্যবহার করে, সংযুক্ত কম্পোনেন্টগুলি ট্র্যাক করুন, যাতে সাইকেল তৈরি না হয়।
- শেষ:
- সমস্ত ভেরটেক্স অন্তর্ভুক্ত হলে অ্যালগরিদম শেষ হবে এবং MST তৈরি হবে।
Pseudocode for Kruskal’s Algorithm
উদাহরণ
ধরি, আমাদের একটি গ্রাফ আছে:
- ভেরটেক্স: A, B, C, D
- এজ:
- A-B (2)
- A-C (1)
- B-D (3)
- C-D (4)
ক্রাসকাল'স অ্যালগরিদমের প্রক্রিয়া:
- প্রথমে সব এজ ওজনের ভিত্তিতে সাজানো হবে:
- A-C (1), A-B (2), B-D (3), C-D (4)
- A-C (1) যুক্ত করুন:
- MST: {A-C}
- A-B (2) যুক্ত করুন:
- MST: {A-C, A-B}
- B-D (3) যুক্ত করুন:
- MST: {A-C, A-B, B-D}
- C-D (4) যুক্ত না করুন, কারণ এটি সাইকেল তৈরি করবে।
সুবিধা
- সরলতা: ক্রাসকাল'স অ্যালগরিদম সরল এবং সহজে বুঝতে পারে।
- দ্রুত: এটি স্পর্শকাতর গ্রাফের জন্য কার্যকরী।
অসুবিধা
- এজ সজ্জার প্রয়োজন: এজগুলিকে ওজনের ভিত্তিতে সাজাতে সময় লাগতে পারে (O(E log E))।
- প্রাথমিক ডেটা স্ট্রাকচার: ইউনিয়ন-ফাইন্ড ডেটা স্ট্রাকচার ব্যবহার না করলে সাইকেল শনাক্ত করা কঠিন হতে পারে।
সারসংক্ষেপ
ক্রাসকাল'স অ্যালগরিদম একটি শক্তিশালী পদ্ধতি যা একটি ওজনযুক্ত গ্রাফের জন্য মিনিমাম স্প্যানিং ট্রি তৈরি করতে ব্যবহৃত হয়। এটি সরল, কার্যকরী এবং নেটওয়ার্ক ডিজাইন এবং অপ্টিমাইজেশনের জন্য গুরুত্বপূর্ণ।
Content added By
Read more
