অননির্দেশিত গ্রাফে সাইকেল আছে কিনা তা শনাক্ত করতে, আমরা প্রদত্ত গ্রাফের জন্য DFS ট্রাভার্সাল ব্যবহার করব। প্রতিটি ভিজিটেড ভার্টেক্স v এর জন্য, যখন আমরা কোনো সন্নিহিত ভার্টেক্স u পাব, যেটি ইতিমধ্যে ভিজিটেড, এবং u ভার্টেক্স v-এর প্যারেন্ট নয়, তখন একটি সাইকেল শনাক্ত হবে।
আমরা ধরে নিচ্ছি যে যেকোনো দুটি ভার্টেক্সের জন্য কোনো প্যারালেল এজ নেই।
ইনপুট এবং আউটপুট
ইনপুট এবং আউটপুট: অ্যাডজেসেন্সি ম্যাট্রিক্স 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 আউটপুট: গ্রাফটিতে সাইকেল আছে।
এলগরিদম
dfs(vertex, visited, parent)
ইনপুট: শুরুর ভার্টেক্স, ভিজিটেড সেট, এবং ভার্টেক্সের প্যারেন্ট নোড।
আউটপুট: সাইকেল পাওয়া গেলে true।
শুরু
vertex কে ভিজিটেড সেটে যোগ করুন
vertex-র সাথে সন্নিহিত সব ভার্টেক্স v এর জন্য, করুন
যদি v = parent, তবে
return true
যদি v ভিজিটেড সেটে না থাকে, তবে
return true
যদি dfs(v, visited, vertex) true হয়, তবে
return true
শেষ লুপ
return false
শেষ
hasCycle(graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: সাইকেল পাওয়া গেলে true।
শুরু
গ্রাফের সব ভার্টেক্স v এর জন্য, করুন
যদি v ভিজিটেড সেটে না থাকে, তবে
পরবর্তী ইটারেশনের জন্য যান
যদি dfs(v, visited, φ) true হয়, তবে // v-এর প্যারেন্ট হলো null
return true
return false
শেষ লুপ
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <set>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 0, 1, 1, 0}
};
bool dfs(int vertex, set<int> &visited, int parent) {
visited.insert(vertex);
for(int v = 0; v < NODE; v++) {
if(graph[vertex][v]) {
if(v == parent) // যদি v প্যারেন্ট হয়, সেটি দিকে যাবেন না
continue;
if(visited.find(v) != visited.end()) // যদি v ইতিমধ্যে ভিজিটেড থাকে
return true;
if(dfs(v, visited, vertex))
return true;
}
}
return false;
}
bool hasCycle() {
set<int> visited; // ভিজিটেড সেট
for(int v = 0; v < NODE; v++) {
if(visited.find(v) != visited.end()) // যখন visited-এ v থাকে, পরবর্তী ইটারেশনে যান
continue;
if(dfs(v, visited, -1)) { // -1 শুরুর ভার্টেক্সের কোনো প্যারেন্ট নেই বলে
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.
