মডিউল ৫_১ঃ Cycle Detection Undirected গ্রাফে
Last updated
Last updated
গ্রাফের ইনপুট 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 করে ফেললাম।
গ্রাফের ইনপুট 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 করে ফেললাম।
