> For the complete documentation index, see [llms.txt](https://phitron.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://phitron.gitbook.io/algorithm/cycle-detection/_-cycle-detection-directed.md).
# মডিউল ৫\_৪ঃ Cycle Detection Directed গ্রাফে
## DFS দিয়ে Directed গ্রাফে cycle detection
গ্রাফের ইনপুট \
**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 করতে পারি।
