একটি গ্রাফ ট্রি (Tree) হয় যদি সেটিতে কোনো সাইকেল (Cycle) না থাকে। এটি একটি সি++ প্রোগ্রাম যা DFS ব্যবহার করে একটি ডিরেক্টেড গ্রাফ ট্রি কিনা তা যাচাই করে।
অ্যালগরিদম
শুরু ফাংশন cyclicUtil() : ক) বর্তমান নোডকে ভিজিটেড এবং রিকার্শন স্ট্যাকের অংশ হিসেবে চিহ্নিত করুন খ) এই ভের্টেক্সের সাথে সংযুক্ত সব ভের্টেক্সের জন্য পুনরাবৃত্তি করুন। গ) রিকার্শন স্ট্যাক থেকে ভের্টেক্সটি সরিয়ে দিন। ফাংশন cyclic() : ক) সব ভের্টেক্সকে ভিজিট না করা এবং রিকার্শন স্ট্যাকের অংশ না হওয়া হিসেবে চিহ্নিত করুন খ) সাইকেল ডিটেক্ট করতে CyclicUtil() ফাংশনটি কল করুন ভিন্ন ট্রিতে। শেষ
উদাহরণ
#include<iostream> #include <list> #include <limits.h> using namespace std; class G { int n; list<int> *adj; //সংলগ্ন লিস্ট ধারণ করে। bool CyclicUtil(int v, bool visited[], bool *rs); public: G(int V); // কনস্ট্রাক্টর 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-এর লিস্টে যোগ করুন } bool G::CyclicUtil(int v, bool visited[], bool *recurS) { if (visited[v] == false) { visited[v] = true; //বর্তমান নোডকে ভিজিটেড এবং রিকার্শন স্ট্যাকের অংশ হিসেবে চিহ্নিত করুন recurS[v] = true; // এই ভের্টেক্সের সাথে সংযুক্ত সব ভের্টেক্সের জন্য পুনরাবৃত্তি করুন। list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i] && CyclicUtil(*i, visited, recurS)) return true; else if (recurS[*i]) return true; } } recurS[v] = false; //ভের্টেক্সটি রিকার্শন স্ট্যাক থেকে সরিয়ে দিন। return false; } //গ্রাফটি ট্রি কিনা তা চেক করুন bool G::cyclic() { //সব ভের্টেক্সকে ভিজিট না করা এবং রিকার্শন স্ট্যাকের অংশ না হওয়া হিসেবে চিহ্নিত করুন bool *visited = new bool[n]; bool *recurS = new bool[n]; for (int i = 0; i < n; i++) { visited[i] = false; recurS[i] = false; } // ভিন্ন ট্রিতে সাইকেল ডিটেক্ট করতে CyclicUtil() ফাংশনটি কল করুন for (int i = 0; i < n; i++) if (CyclicUtil(i, visited, recurS)) return true; return false; } int main() { G g(4); g.addEd(0, 2); g.addEd(1, 2); g.addEd(2, 0); g.addEd(3, 2); if (g.cyclic()) cout << "Directed Graph isn't a tree"; else cout << "Directed Graph is a tree"; return 0; }
আউটপুট
Directed Graph isn't a tree
