মডিউল ১১_১ঃ DSU দিয়ে Cycle Detection Undirected গ্রাফে
এখন আমরা DSU ব্যবহার করে undirected graph এ cycle detect করবো।
প্রথমে প্রশ্ন আসে কেন শুধু undirect graph এর cycle detect করতে পারে DSU, কেন directed graph এর cycle detect করতে পারে না, এইটি জানার জন্য আগে আমাদের জানতে হবে undirect graph এ কিভাবে DSU cycle detect করে।
Undirect graph এর cycle detect DSU দিয়ে
Undirected গ্রাফের ইনপুট
6 6 0 1 0 4 0 2 2 3 2 5 5 3
DSU তে প্রথমে প্রতিটি নোডই নিজেই লিডার হিসেবে থাকে, আমরা এইখানে প্রতিটি edge এ পাওয়া প্রতিটি নোডকে union করে দিব।
শুরুতে গ্রাফ এবং গ্রুপগুলোর অবস্থা এইরকম হবেঃ
১ম edge: 0 এর লিডার 0 নিজে এবং 1 এর লিডার 1 লিজেই, যেহেতু তাদের লিডারগুলো ভিন্ন তাই কোন cycle detect হয় নি। ১ম edge: 0 1 এর union করা পর
0 1 কে union করা পর, 0 এর লিডার হচ্ছে 0 নিজেই এবং 1 এর লিডার হচ্ছে 0।
২য় edge: 0 এর লিডার 0 নিজে এবং 4 এর লিডার 4 লিজেই, যেহেতু তাদের লিডারগুলো ভিন্ন তাই কোন cycle detect হয় নি। ২য় edge: 0 4 এর union করা পর
0 4 কে union করা পর, 0 এর লিডার হচ্ছে 0 নিজেই এবং 4 এর লিডার হচ্ছে 0।
৩য় edge: 0 এর লিডার 0 নিজে এবং 2 এর লিডার 2 লিজেই, যেহেতু তাদের লিডারগুলো ভিন্ন তাই কোন cycle detect হয় নি। ৩য় edge: 0 2 এর union করা পর
0 2 কে union করা পর, 0 এর লিডার হচ্ছে 0 নিজেই এবং 2 এর লিডার হচ্ছে 0।
৪র্থ edge: 2 এর লিডার 0 এবং 3 এর লিডার 3 লিজেই, যেহেতু তাদের লিডারগুলো ভিন্ন তাই কোন cycle detect হয় নি। ৪র্থ edge: 2 3 এর union করা পর
2 3 কে union করা পর, 2 এর লিডার হচ্ছে 0 নিজেই এবং 3 এর লিডার হচ্ছে 0।
৫ম edge: 2 এর লিডার 0 এবং 5 এর লিডার 5 লিজেই, যেহেতু তাদের লিডারগুলো ভিন্ন তাই কোন cycle detect হয় নি। ৫ম edge: 2 5 এর union করা পর
2 5 কে union করা পর, 2 এর লিডার হচ্ছে 0 নিজেই এবং 5 এর লিডার হচ্ছে 0।
৬ষ্ট edge: 5 এর লিডার 0 এবং 3 এর লিডার 0, যেহেতু তাদের লিডারগুলো মিলে গিয়েছে তাই cycle detect হয়েছে।
এইভাবে DSU ব্যবহার করে Undirected graph এর মধ্যে Cycle Detection করা যায়।
কেন directed graph এর cycle detect করতে পারে না
Directed গ্রাফের ইনপুট
3 3 0 1 0 2 1 2
DSU তে প্রথমে প্রতিটি নোডই নিজেই লিডার হিসেবে থাকে, আমরা এইখানে প্রতিটি edge এ পাওয়া প্রতিটি নোডকে union করে দিব।
শুরুতে গ্রাফ এবং গ্রুপগুলোর অবস্থা এইরকম হবেঃ
১ম edge: 0 এর লিডার 0 নিজে এবং 1 এর লিডার 1 লিজেই, যেহেতু তাদের লিডারগুলো ভিন্ন তাই কোন cycle detect হয় নি। ১ম edge: 0 1 এর union করা পর
0 1 কে union করা পর, 0 এর লিডার হচ্ছে 0 নিজেই এবং 1 এর লিডার হচ্ছে 0।
২য় edge: 0 এর লিডার 0 নিজে এবং 2 এর লিডার 2 লিজেই, যেহেতু তাদের লিডারগুলো ভিন্ন তাই কোন cycle detect হয় নি। ২য় edge: 0 2 এর union করা পর
0 2 কে union করা পর, 0 এর লিডার হচ্ছে 0 নিজেই এবং 2 এর লিডার হচ্ছে 0।
৩য় edge: 1 এর লিডার 0 এবং 2 এর লিডার 0, যেহেতু তাদের লিডারগুলো মিলে গিয়েছে তাই cycle detect হওয়ার কথা , কিন্তু এই গ্রাফটি একটি directed গ্রাফ আর এই গ্রাফটিতে স্পষ্টভাবে দেখা যাচ্ছে কোন cycle নাই।
DSU দিয়ে আমরা যেইভাবে undirected গ্রাফের cycle detect করছি, সেইভাবে করতে গেলে direct গ্রাফে cycle না থাকা স্বতেও cycle detect হয়ে যাচ্ছে, কারণ DSU শুধ চেক করে কোন একটা নোডের মধ্যে edge আছে কিনা , DSU direct চেক করে নাহ। তাই DSU দিয়ে Directed graph এ cycle detection করা সম্ভব নয়।
Last updated