> 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-undirected.md).
# মডিউল ৫\_১ঃ Cycle Detection Undirected গ্রাফে
## BFS দিয়ে Undirected গ্রাফে cycle detection
গ্রাফের ইনপুট \
**4 4**\ 0 1\ 1 2\ 2 3\ 3 1
নিচে ইনপুটটি অনুসারে গ্রাফটি আঁকা হল
***
-> source = 0 ধরে BFS শুরু করছি। 0 নোডকে queue তে পুশ করা হয়েছে BFS চালানোর জন্য। 0 নোডকে\
ভিজিটেড করা হল। \
**তাহলে এখন queue তে ( 0 ) আছে।**
লুপের প্রবেশ করা হল এবং Queue থেকে 0 নোডকে বের করা হল ।
0 নোডের সাথে connected কিন্তু ভিজিটেড এবং Parent\[0] != child কিনা চেক করা হল, যদি এমনটি পাওয়া যেত তাহলে আমরা বলে ফেলতে পারতাম গ্রাফের মধ্যে cycle আছে।
এরপর 0 নোডের সাথে connected এবং এখনো আনভিজিটেড এমন নোড 1 এবং 3 নোডকে ভিজিটেড করা হল। 1 এবং 3 কে queue তে পুশ করা হল এবং তাদের parent 0 করা হল।
**তাহলে এখন queue তে ( 3, 1 ) আছে।**
***
-> Queue যেহেতুল empty হয় নি, তাই লুপটি আবার চলবে। Queue থেকে 1 নোডকে বের করা হল ।\
**তাহলে এখন queue তে ( 3 ) আছে।**
1 সাথে connected এবং ভিজিটেড নোড 0 আছে কিন্তু Parent\[1] != 0 (child) এই conditions টি পরিপূর্ণ না হওয়াই আমরা বলতে পারি না যে এই গ্রাফটিতে cycle আছে।
এরপর 1 নোডের সাথে connected এবং এখনো আনভিজিটেড এমন নোড 2 কে ভিজিটেড করা হল। 2 নোডকে queue তে পুশ করা হল এবং 2 নোডের parent 1 করা হল। \
**তাহলে এখন queue তে ( 2, 3 ) আছে।**
***
-> Queue যেহেতু empty হয় নি, তাই লুপটি আবার চলবে। Queue থেকে 3 নোডকে বের করা হল । \
**তাহলে এখন queue তে ( 2 ) আছে।**
3 সাথে connected এবং ভিজিটেড নোড 0 , 2 আছে ,
* 0 নোড Parent\[3] != 0 (child) এই conditions টি পরিপূর্ণ না হওয়াই আমরা বলতে পারি না যে এই গ্রাফটিতে cycle আছে।
* **কিন্তু 2 নোড Parent\[3] != 2 (child) এই conditions টি পরিপূর্ণ করাই আমরা বলতে পারি যে এই গ্রাফটিতে cycle আছে।**
এরপর 3 নোডের সাথে connected এবং এখনো আনভিজিটেড এমন কোন নোড পাওয়া যায় নি।
এইভাবে আমরা BFS দিয়ে undirected গ্রাফে cycle detect করে ফেললাম।
## DFS দিয়ে Undirected গ্রাফে cycle detection
গ্রাফের ইনপুট \
**4 4**\ 0 1\ 1 2\ 2 3\ 3 1
নিচে ইনপুটটি অনুসারে গ্রাফটি আঁকা হল
***
-> source = 0 ধরে DFS শুরু করছি। 0 নোডকে ভিজিটেড করা হল। \
কিন্তু 2 নোড Parent\[3] != 0 (child) এই conditions টি পরিপূর্ণ করাই আমরা বলতে পারি যে এই গ্রাফটিতে cycle আছে।
0 নোডের সাথে connected আছে 1 এবং 2 নোড।
0 নোডের সাথে connected কিন্তু ভিজিটেড এবং Parent\[0] != child কিনা চেক করা হল, কিন্তু এমন নোড পাওয়ার যায় নি। যদি এমনটি পাওয়া যেত তাহলে আমরা বলে ফেলতে পারতাম গ্রাফের মধ্যে cycle আছে।
0 নোডের সাথে connected এবং এখনো আনভিজিটেড এমন নোড হল 1 এবং 2। এখন 0 নোডকে 1 নোডের parent করা হল এবং DFS function কে recursive করা হল source = 1 ধরে।
***
-> এখন source = 1 হল এবং 1 নোডকে ভিজিটেড করা হল।
1 নোডের সাথে connected আছে 0 এবং 2 নোড।
1 সাথে connected এবং ভিজিটেড নোড 0 আছে কিন্তু Parent\[1] != 0 (child) এই conditions টি পরিপূর্ণ না হওয়াই আমরা বলতে পারি না যে এই গ্রাফটিতে cycle আছে।
1 নোডের সাথে connected এবং এখনো আনভিজিটেড এমন নোড হল 2। এখন 1 নোডকে 2 নোডের parent করা হল এবং DFS function কে recursive করা হল source = 2 ধরে। \
***
-> এখন source = 2 হল এবং 2 নোডকে ভিজিটেড করা হল।
2 নোডের সাথে connected আছে 1 এবং 3 নোড।
2 সাথে connected এবং ভিজিটেড নোড 1 আছে কিন্তু Parent\[2] != 1 (child) এই conditions টি পরিপূর্ণ না হওয়াই আমরা বলতে পারি না যে এই গ্রাফটিতে cycle আছে।
2 নোডের সাথে connected এবং এখনো আনভিজিটেড এমন নোড হল 3। এখন 2 নোডকে 3 নোডের parent করা হল এবং DFS function কে recursive করা হল source = 3 ধরে।
***
-> এখন source = 3 হল এবং 3 নোডকে ভিজিটেড করা হল।
3 নোডের সাথে connected আছে 2 এবং 0 নোড।
3 সাথে connected এবং ভিজিটেড নোড 2 এবং 0,
* 2 নোড Parent\[3] != 2 (child) এই conditions টি পরিপূর্ণ না হওয়াই আমরা বলতে পারি না যে এই গ্রাফটিতে cycle আছে।
* **কিন্তু 0 নোড Parent\[3] != 2 (child) এই conditions টি পরিপূর্ণ করাই আমরা বলতে পারি যে এই গ্রাফটিতে cycle আছে।**
এইভাবে আমরা DFS দিয়ে undirected গ্রাফে cycle detect করে ফেললাম।
