দেওয়া গ্রাফটি ট্রি কিনা তা যাচাই করা

ভূমিকা

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

আমরা অন্য একটি পদ্ধতিও ব্যবহার করতে পারি: যদি গ্রাফটি কানেক্টেড থাকে এবং এর V-1 সংখ্যক এজ থাকে, তবে এটি একটি ট্রি হতে পারে। এখানে V হলো গ্রাফের ভার্টেক্সের সংখ্যা।

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

ইনপুট: অ্যাডজেসেন্সি ম্যাট্রিক্স। 
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

আউটপুট: The Graph is a tree

অ্যালগরিদম

isCycle(u, visited, parent)

ইনপুট: স্টার্ট ভার্টেক্স u, ভিজিটেড লিস্ট (ভিজিট করা হয়েছে কিনা মার্ক করার জন্য), প্যারেন্ট ভার্টেক্স।

আউটপুট: গ্রাফে সাইকেল থাকলে True।

শুরু
    u-কে ভিজিটেড হিসেবে মার্ক করো
    u-এর সাথে সংলগ্ন সব ভার্টেক্স v-এর জন্য, করো
        যদি v ভিজিটেড হয়, তবে
            যদি isCycle(v, visited, u) = true হয়, তবে
                true রিটার্ন করো
            অন্যথায় যদি v ≠ parent হয়, তবে
                true রিটার্ন করো
        শেষ
    শেষ
    false রিটার্ন করো
শেষ

isTree(graph)

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

আউটপুট: গ্রাফ ট্রি হলে True।

শুরু
    একটি visited অ্যারে ডিফাইন করো নোড ভিজিট করা হয়েছে কিনা মার্ক করার জন্য
    প্রাথমিকভাবে সব নোডকে আনভিজিটেড হিসেবে মার্ক করো
    যদি isCycle(0, visited, ∅) true হয়, তবে //স্টার্টিং ভার্টেক্সের প্যারেন্ট হলো null
        false রিটার্ন করো
    যদি গ্রাফ কানেক্টেড না হয়, তবে
        false রিটার্ন করো
    অন্যথায় true রিটার্ন করো
শেষ

উদাহরণ (C++)

#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; 
    //v-কে ভিজিটেড হিসেবে মার্ক করো
    for(int v = 0; v<NODE; v++) { 
        if(graph[u][v]) { 
            if(!visited[v]) { 
                //যখন সংলগ্ন নোড v ভিজিটেড নয়
                if(isCycle(v, visited, u)) { 
                    return true; 
                } 
            } else if(v != parent) { 
                //যখন সংলগ্ন ভার্টেক্স ভিজিটেড কিন্তু প্যারেন্ট নয়
                return true; 
                //সাইকেল আছে
            } 
        } 
    } 
    return false; 
} 

bool isTree() { 
    bool *vis = new bool[NODE]; 
    for(int i = 0; i<NODE; i++) 
        vis[i] = false; 
    //ইনিশিয়ালাইজ করা হয়েছে কোনো নোড ভিজিটেড নয়
    if(isCycle(0, vis, -1)) 
        //চেক করা হচ্ছে সাইকেল আছে কিনা
        return false; 
    for(int i = 0; i<NODE; i++) { 
        if(!vis[i]) 
            //যদি ট্রাভার্সাল দিয়ে কোনো নোড ভিজিট না হয়, গ্রাফ কানেক্টেড নয়
            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.