প্রদত্ত গ্রাফটি গাছ কিনা তা পরীক্ষা করুন

এই সমস্যায়, একটি অনির্দেশিত গ্রাফ দেওয়া হয়েছে, আমাদের গ্রাফটি ট্রি কিনা তা পরীক্ষা করতে হবে। আমরা কেবল একটি গাছের মানদণ্ড পরীক্ষা করে এটি খুঁজে পেতে পারি। একটি গাছে একটি চক্র থাকবে না, তাই গ্রাফে যদি কোনো চক্র থাকে তবে সেটি গাছ নয়৷

আমরা অন্য পদ্ধতি ব্যবহার করে এটি পরীক্ষা করতে পারি, যদি গ্রাফটি সংযুক্ত থাকে এবং এতে V-1 প্রান্ত থাকে তবে এটি একটি গাছ হতে পারে। এখানে V হল গ্রাফে শীর্ষবিন্দুর সংখ্যা।

ইনপুট এবং আউটপুট

Input:
The adjacency matrix.
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
1 1 1 1 0

Output:
The Graph is a tree

অ্যালগরিদম

isCycle(u, পরিদর্শন করা, অভিভাবক)

ইনপুট: সূচনা শীর্ষবিন্দু u, পরিদর্শন করা হয়েছে বা না হয়েছে চিহ্নিত করার জন্য পরিদর্শন তালিকা, মূল শীর্ষবিন্দু৷

আউটপুট: গ্রাফে একটি চক্র থাকলে সত্য।

Begin
   mark u as visited
   for all vertex v which are adjacent with u, do
      if v is visited, then
         if isCycle(v, visited, u) = true, then
            return true
         else if v ≠ parent, then
            return true
   done
   return false
End

isTree(গ্রাফ)

ইনপুট: অনির্দেশিত গ্রাফ।

আউটপুট: গ্রাফটি একটি গাছ হলে সত্য৷

Begin
   define a visited array to mark which node is visited or not
   initially mark all node as unvisited
   if isCycle(0, visited, φ) is true, then //the parent of starting vertex is null
      return false
   if the graph is not connected, then
      return false
   return true otherwise
End

উদাহরণ

#include<iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
   {0, 1, 1, 1, 0},
   {1, 0, 1, 0, 0},
   {1, 1, 0, 0, 0},
   {1, 0, 0, 0, 1},
   {0, 0, 0, 1, 0}
};
                                                               
bool isCycle(int u, bool visited[], int parent) {
   visited[u] = true;    //mark v as visited
   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]) {
         if(!visited[v]) {     //when the adjacent node v is not visited
            if(isCycle(v, visited, u)) {
               return true;
            }
         } else if(v != parent) {    //when adjacent vertex is visited but not parent
            return true;    //there is a cycle
         }
      }
   }
   return false;
}

bool isTree() {
   bool *vis = new bool[NODE];

   for(int i = 0; i<NODE; i++)
      vis[i] = false;    //initialize as no node is visited
         
   if(isCycle(0, vis, -1))    //check if there is a cycle or not
      return false;
         
   for(int i = 0; i<NODE; i++) {
      if(!vis[i])    //if there is a node, not visited by traversal, graph is not connected
         return false;
   }
   return true;
}

int main() {
   if(isTree())
      cout << "The Graph is a Tree.";
   else
      cout << "The Graph is not a Tree.";
}

আউটপুট

The Graph is a Tree.