মডিউল ৫_৪ঃ Cycle Detection Directed গ্রাফে
Previousমডিউল ৫_৩ঃ Cycle Detection Undirected গ্রাফ DFS ইমপ্লিমেন্টশনNextমডিউল ৫_৫ঃ Cycle Detection Directed গ্রাফ DFS ইমপ্লিমেন্টশন
Last updated
Last updated
গ্রাফের ইনপুট 5 5 0 1 1 2 0 4 4 3 3 0
নিচে ইনপুটটি অনুসারে গ্রাফটি আঁকা হল
-> source=0 নিয়ে dfs function কে কল করা হল। 0 নোডকে ভিজিটেড করা হল এবং Pathvisit এ 0 নোডকে true করা হল।
0 নোড থেকে 1 এবং 4 নোডে যাওয়া যায়। এরপর আমরা চেক করবো 1 নোড কি pathvisit এ true কিনা। যদি true হয় তাহলে আমরা বলতে পারবো গ্রাফটিতে cycle আছে। যেহেতু 1 নোডের Pathvisit true নয়, তাই বলা যায় এখন পর্যন্ত গ্রাফে আমরা cycle পায় নি। 1 নোড আনভিজিটেড তাই সেইটি দিয়ে dfs function কে recursive কল করা হল।
-> এখন source=1। এরপর 1 নোডকে ভিজিটেড করা হল এবং Pathvisit এ 1 নোডকে true করা হল।
1 নোড থেকে 2 নোডে যাওয়া যায়। এরপর আমরা চেক করবো 2 নোড কি pathvisit এ true কিনা। যদি true হয় তাহলে আমরা বলতে পারবো গ্রাফটিতে cycle আছে। যেহেতু 2 নোডের Pathvisit true নয়, তাই বলা যায় এখন পর্যন্ত গ্রাফে আমরা cycle পায় নি। 2 নোড আনভিজিটেড তাই সেইটি দিয়ে dfs function কে recursive কল করা হল।
-> এখন source=2 । এরপর 2 নোডকে ভিজিটেড করা হল এবং Pathvisit এ 2 নোডকে true করা হল।
2 নোড থেকে আর কোননোডে যাওয়া যায় নাহ। এখন আমরা ব্যাকট্র্যাক করবো।
ব্যাক করা ফলে Pathvisit এ 2 নোডকে আবার false করে দেয়া হল। এখন 1 নোড থেকে আর কোন আনভিজিটেড নোডে যাওয়া যাচ্ছে তাই আবার আমরা ব্যাকট্র্যাক করবো।
ব্যাক করা ফলে Pathvisit এ 1 নোডকে আবার false করে দেয়া হল। এখন 1 নোড থেকে 4 নোডে যাওয়া যায়। এরপর আমরা চেক করবো 4 নোড কি pathvisit এ true কিনা। যদি true হয় তাহলে আমরা বলতে পারবো গ্রাফটিতে cycle আছে। যেহেতু 4 নোডের Pathvisit true নয়, তাই বলা যায় এখন পর্যন্ত গ্রাফে আমরা cycle পায় নি। 4 নোড আনভিজিটেড তাই সেইটি দিয়ে dfs function কে recursive কল করা হল।
-> এখন source=4। এরপর 4 নোডকে ভিজিটেড করা হল এবং Pathvisit এ 4 নোডকে true করা হল।
4 নোড থেকে 3 নোডে যাওয়া যায়। এরপর আমরা চেক করবো 3 নোড কি pathvisit এ true কিনা। যদি true হয় তাহলে আমরা বলতে পারবো গ্রাফটিতে cycle আছে। যেহেতু 3 নোডের Pathvisit true নয়, তাই বলা যায় এখন পর্যন্ত গ্রাফে আমরা cycle পায় নি। 3 নোড আনভিজিটেড তাই সেইটি দিয়ে dfs function কে recursive কল করা হল।
-> এখন source=3। এরপর 3 নোডকে ভিজিটেড করা হল এবং Pathvisit এ 3 নোডকে true করা হল।
3 নোড থেকে 0 নোডে যাওয়া যায়। এরপর আমরা চেক করবো 0 নোড কি pathvisit এ true কিনা। যদি true হয় তাহলে আমরা বলতে পারবো গ্রাফটিতে cycle আছে। 3 নোডের Pathvisit true, তাই বলা যায় এই গ্রাফে cycle আছে।
এইভাবে আমরা DFS দিয়ে Directed গ্রাফে cycle detection করতে পারি।
