ডেপথ ফার্স্ট সার্চ (DFS) ট্রাভার্সাল অ্যালগরিদম ব্যবহার করে একটি ডায়রেক্টেড গ্রাফে সাইকেল শনাক্ত করা যায়। যদি কোনো নোডে সেলফ-লুপ থাকে, তবে সেটিকে একটি সাইকেল মाना হবে। অন্যথায়, যখন চাইল্ড নোডের অন্য কোনো এজ থাকে তার প্যারেন্টের সাথে সংযুক্ত হতে, তবে সেটিও একটি সাইকেল।
অসংযুক্ত গ্রাফের জন্য, ভিন্ন ভিন্ন ট্রি উপস্থিত থাকতে পারে, যাদেরকে আমরা একটি ফরেস্ট বলি। এখন আমাদের ফরেস্টের সব ট্রির জন্য সাইকেল শনাক্ত করতে হবে।
এই পদ্ধতিতে, আমরা নোডগুলোকে DFS ট্রাভার্সাল করার জন্য তিনটি ভিন্ন সেটে ভাগ করব: হোয়াইট (White), গ্রে (Grey) এবং ব্ল্যাক (Black)। প্রাথমিকভাবে সব নোড হোয়াইট সেটে থাকবে। যখন একটি নতুন নোড ট্রাভার্স করা হবে, তবে সেটিকে গ্রে সেটে রাখা হবে এবং হোয়াইট সেট থেকে সরিয়ে দেওয়া হবে। এবং ব্যাকট্র্যাকিং সম্পূর্ণ হলে, যখন সেই নোডের কাজ শেষ হয়ে যায়, তখন সেটিকে গ্রে থেকে ব্ল্যাক সেটে সরিয়ে দেওয়া হবে।
ইনপুট এবং আউটপুট
ইনপুট: অ্যাডজেসেন্সি ম্যাট্রিক্স। 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 আউটপুট: গ্রাফটিতে সাইকেল আছে।
এলগরিদম
dfs(curr, wSet, gSet, bSet)
ইনপুট: বর্তমান নোড, হোয়াইট, গ্রে এবং ব্ল্যাক সেট।
আউটপুট: সাইকেল থাকলে true।
শুরু
curr কে হোয়াইট সেট থেকে মুছে গ্রে সেটে যোগ করুন
curr-র সাথে সংযুক্ত গ্রাফের সব নোড v এর জন্য, করুন
যদি v ব্ল্যাক সেটে থাকে, তবে
পরবর্তী অংশ স্কিপ করুন, এবং পরবর্তী ইটারেশনের জন্য যান
যদি v গ্রে সেটে থাকে, তবে
return true
যদি dfs(v, wSet, gSet, bSet) true হয়, তবে
return true
শেষ লুপ
curr কে গ্রে সেট থেকে মুছে ব্ল্যাক সেটে যোগ করুন
return false
শেষ
hasCycle(graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: গ্রাফে সাইকেল থাকলে true।
শুরু
প্রাথমিকভাবে সব নোডকে হোয়াইট সেটে যোগ করুন
যতক্ষণ হোয়াইট সেটে কিছু উপাদান থাকে, করুন
গ্রাফের সব নোড v এর জন্য, করুন
যদি v হোয়াইট সেটে না থাকে, তবে
যদি dfs(v, wSet, gSet, bSet), তবে
return true
শেষ শর্ত
শেষ লুপ
শেষ লুপ
return false
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <set>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 0},
{1, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 0, 1, 0, 0}
};
bool dfs(int curr, set<int> &wSet, set<int> &gSet, set<int> &bSet) {
// curr কে হোয়াইট সেট থেকে গ্রে সেটে সরানো
wSet.erase(wSet.find(curr));
gSet.insert(curr);
for(int v = 0; v < NODE; v++) {
if(graph[curr][v] != 0) { // সব সন্নিহিত ভার্টেক্সের জন্য
if(bSet.find(v) != bSet.end()) // যদি ভার্টেক্সগুলো ব্ল্যাক সেটে থাকে
continue;
if(gSet.find(v) != gSet.end()) // এটি একটি সাইকেল
return true;
if(dfs(v, wSet, gSet, bSet)) // সাইকেল পাওয়া গেলে
return true;
}
}
// v কে গ্রে সেট থেকে ব্ল্যাক সেটে সরানো
gSet.erase(gSet.find(curr));
bSet.insert(curr);
return false;
}
bool hasCycle() {
set<int> wSet, gSet, bSet; // তিনটি সেট: হোয়াইট, গ্রে এবং ব্ল্যাক
for(int i = 0; i < NODE; i++)
wSet.insert(i); // প্রাথমিকভাবে সব নোডকে হোয়াইট সেটে যোগ করুন
while(wSet.size() > 0) {
for(int current = 0; current < NODE; current++) {
if(wSet.find(current) != wSet.end())
if(dfs(current, wSet, gSet, bSet))
return true;
}
}
return false;
}
int main() {
bool res;
res = hasCycle();
if(res)
cout << "The graph has cycle." << endl;
else
cout << "The graph has no cycle." << endl;
}
আউটপুট
The graph has cycle.
