हैमिल्टोनियन साइकिल

एक अनडायरेक्टेड ग्राफ में, हैमिल्टोनियन पथ एक ऐसा पथ है जो प्रत्येक वर्टेक्स को ठीक एक बार विजिट करता है, और हैमिल्टोनियन साइकिल या सर्किट एक हैमिल्टोनियन पथ है, जिसमें अंतिम वर्टेक्स से पहले वर्टेक्स तक एक एज होती है।

इस समस्या में, हम यह निर्धारित करने का प्रयास करेंगे कि क्या ग्राफ में हैमिल्टोनियन साइकिल है या नहीं। और जब हैमिल्टोनियन साइकिल मौजूद हो, तो उसे प्रिंट भी करें।

इनपुट और आउटपुट

इनपुट: एक ग्राफ G(V, E) का एडजेसेंसी मैट्रिक्स।  आउटपुट: एल्गोरिदम दिए गए ग्राफ का हैमिल्टोनियन पथ ढूंढता है। इस मामले में यह (0, 1, 2, 4, 3, 0) है। इस ग्राफ में कुछ अन्य हैमिल्टोनियन पथ भी हैं। यदि किसी ग्राफ में कोई हैमिल्टोनियन पथ नहीं है, तो एल्गोरिदम false वापस करना चाहिए।

एल्गोरिदम

isValid(v, k)

इनपुट - वर्टेक्स v और पोजीशन k

आउटपुट - जांचता है कि v को पोजीशन k में रखना वैध है या नहीं

Begin 
  if there is no edge between node(k-1) to v, then 
    return false 
  if v is already taken, then 
    return false 
  return true; //otherwise it is valid 
End

cycleFound(node k)

इनपुट - ग्राफ का नोड

आउटपुट - जब हैमिल्टोनियन साइकिल हो तो True, अन्यथा false

Begin 
  if all nodes are included, then 
    if there is an edge between nodes k and 0, then 
      return true 
    else 
      return false; 
  for all vertex v except starting point, do 
    if isValid(v, k), then //when v is a valid edge 
      add v into the path 
      if cycleFound(k+1) is true, then 
        return true 
      otherwise remove v from the path 
  done 
  return false 
End

उदाहरण

#include<iostream> #define NODE 5 using namespace std; int graph[NODE][NODE] = { {0, 1, 0, 1, 0}, {1, 0, 1, 1, 1}, {0, 1, 0, 0, 1}, {1, 1, 0, 0, 1}, {0, 1, 1, 1, 0}, }; /* int graph[NODE][NODE] = { {0, 1, 0, 1, 0}, {1, 0, 1, 1, 1}, {0, 1, 0, 0, 1}, {1, 1, 0, 0, 0}, {0, 1, 1, 0, 0}, }; */ int path[NODE]; void displayCycle() { cout<<"Cycle: "; for (int i = 0; i < NODE; i++) cout << path[i] << " "; cout << path[0] << endl; //print the first vertex again } bool isValid(int v, int k) { if (graph [path[k-1]][v] == 0) //if there is no edge return false; for (int i = 0; i < k; i++) //if vertex is already taken, skip that if (path[i] == v) return false; return true; } bool cycleFound(int k) { if (k == NODE) { //when all vertices are in the path if (graph[path[k-1]][ path[0] ] == 1 ) return true; else return false; } for (int v = 1; v < NODE; v++) { //for all vertices except starting point if (isValid(v,k)) { //if possible to add v in the path path[k] = v; if (cycleFound (k+1) == true) return true; path[k] = -1; //when k vertex will not in the solution } } return false; } bool hamiltonianCycle() { for (int i = 0; i < NODE; i++) path[i] = -1; path[0] = 0; //first vertex as 0 if ( cycleFound(1) == false ) { cout << "Solution does not exist"<

आउटपुट
Cycle: 0 1 2 4 3 0