जांचें कि दिया गया ग्राफ ट्री है या नहीं

इस समस्या में, एक अनडायरेक्टेड ग्राफ दिया गया है, हमें जांचना है कि ग्राफ ट्री है या नहीं। हम ट्री के मानदंड की जांच करके इसे सरलता से ढूंढ सकते हैं। एक ट्री में साइकिल नहीं होगी, इसलिए यदि ग्राफ में कोई साइकिल है, तो यह ट्री नहीं है।

हम इसे दूसरे दृष्टिकोण से भी जांच सकते हैं, यदि ग्राफ कनेक्टेड है और इसमें 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 आउटपुट: ग्राफ एक ट्री है

एल्गोरिदम

isCycle(u, visited, parent)

इनपुट: स्टार्ट वर्टेक्स u, विजिटेड सूची विजिटेड या नहीं मार्क करने के लिए, पैरेंट वर्टेक्स

आउटपुट: True यदि ग्राफ में साइकिल है

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(graph)

इनपुट: अनडायरेक्टेड ग्राफ

आउटपुट: True जब ग्राफ एक ट्री हो

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 #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

आउटपुट
The Graph is a Tree.