একটি গ্রাফ ট্রি (Tree) হয় যদি সেটিতে কোনো সাইকেল (Cycle) না থাকে। এটি একটি সি++ প্রোগ্রাম যা একটি অনডিরেক্টেড গ্রাফ ট্রি কিনা তা যাচাই করে।
অ্যালগরিদম
শুরু ফাংশন cyclicUtil() : ক) বর্তমান নোডকে ভিজিটেড হিসেবে চিহ্নিত করুন। খ) এই ভের্টেক্সের সাথে সংযুক্ত সব ভের্টেক্সের জন্য পুনরাবৃত্তি করুন। গ) যদি কোনো সংলগ্ন ভিজিট না করা থাকে, তবে সেটির জন্য পুনরাবৃত্তি করুন। ঘ) যদি কোনো সংলগ্ন ভিজিটেড থাকে এবং বর্তমান ভের্টেক্সের প্যারেন্ট (parent) না থাকে, তবে সাইকেল আছে। শেষ শুরু ফাংশন cyclic(): ক) সব ভের্টেক্সকে ভিজিট না করা এবং রিকার্শন স্ট্যাকের অংশ না হওয়া হিসেবে চিহ্নিত করুন। খ) ভিন্ন DFS ট্রিতে সাইকেল ডিটেক্ট করতে রিকার্সিভ ফাংশন cyclicUtil() কল করুন। শেষ
উদাহরণ
#include<iostream> #include <list> #include <limits.h> using namespace std; class G { int n; list<int> *adj; bool CyclicUtil(int v, bool visited[], int par); public: G(int n); //কনস্ট্রাক্টর void addEd(int v, int w); bool cyclic(); }; G::G(int n) { this->n = n; adj = new list<int> [n]; } void G::addEd(int v, int u)//গ্রাফে এজ যোগ করুন { adj[v].push_back(u); //u'কে v-এর লিস্টে যোগ করুন adj[u].push_back(v);//v'কে u-এর লিস্টে যোগ করুন } //রিকার্সিভ ফাংশন visited[] ব্যবহার করে ভের্টেক্স v থেকে পৌঁছানো সাবগ্রাফে সাইকেল ডিটেক্ট করে: bool G::CyclicUtil(int v, bool visited[], int par) { visited[v] = true; // বর্তমান নোডকে ভিজিটেড হিসেবে চিহ্নিত করুন // এই ভের্টেক্সের সাথে সংযুক্ত সব ভের্টেক্সের জন্য পুনরাবৃত্তি করুন list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i]) //যদি কোনো সংলগ্ন ভিজিট না করা থাকে, তবে সেটির জন্য রিকার্সন করুন { if (CyclicUtil(*i, visited, v)) return true; } // যদি কোনো সংলগ্ন ভিজিটেড থাকে এবং বর্তমান ভের্টেক্সের প্যারেন্ট না থাকে, তবে সাইকেল আছে। else if (*i != par) return true; } return false; } // গ্রাফটি ট্রি কিনা তা চেক করতে। bool G ::cyclic() { bool *visited = new bool[n]; // সব ভের্টেক্সকে ভিজিট না করা এবং রিকার্শন স্ট্যাকের অংশ না হওয়া হিসেবে চিহ্নিত করুন for (int i = 0; i < n; i++) visited[i] = false; // ভিন্ন DFS ট্রিতে সাইকেল ডিটেক্ট করতে রিকার্সিভ ফাংশন CyclicUtil() কল করুন for (int u = 0; u < n; u++) if (!visited[u]) if (CyclicUtil(u, visited, -1)) return true; return false; } int main() { G g1(4); g1.addEd(0, 1); g1.addEd(1, 2); g1.cyclic() ? cout << "Undirected Graph isn't a tree\n" : cout << "Undirected Graph is a tree\n"; return 0; }
আউটপুট
Undirected Graph is a tree
