হ্যামিল্টোনিয়ান সাইকেল

এক অনির্দেশিত গ্রাফে, হ্যামিল্টোনিয়ান পাথ হলো এমন একটি পাথ যা প্রতিটি ভার্টেক্সকে ঠিক একবার ভিজিট করে, এবং হ্যামিল্টোনিয়ান সাইকেল বা সার্কিট হলো এমন একটি হ্যামিল্টোনিয়ান পাথ যেখানে শেষ ভার্টেক্স থেকে প্রথম ভার্টেক্সে একটি এজ থাকে।

এই সমস্যায়, আমরা চেষ্টা করব একটি গ্রাফে হ্যামিল্টোনিয়ান সাইকেল আছে কিনা তা নির্ধারণ করতে। এবং হ্যামিল্টোনিয়ান সাইকেল থাকলে, সেটিও প্রিন্ট করব।

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

ইনপুট: একটি গ্রাফ G(V, E)-এর এডজেসেন্সি ম্যাট্রিক্স।  আউটপুট: অ্যালগরিদমটি দিয়ে দেওয়া গ্রাফের হ্যামিল্টোনিয়ান পাথ বের করা হয়েছে। এই কেসে সেটি (0, 1, 2, 4, 3, 0)। এই গ্রাফের আরও কিছু হ্যামিল্টোনিয়ান পাথ আছে। যদি কোনো গ্রাফে হ্যামিল্টোনিয়ান পাথ না থাকে, তবে অ্যালগরিদমটি false রিটার্ন করবে।

অ্যালগরিদম

isValid(v, k)

ইনপুট - ভার্টেক্স v এবং পজিশন k।

আউটপুট - চেক করে v কে k পজিশনে রাখা বৈধ কিনা।

শুরু
  যদি node(k-1) থেকে v-তে কোনো এজ না থাকে, তবে
    return false
  যদি v ইতিমধ্যে নেওয়া হয়ে থাকে, তবে
    return false
  return true; //অন্যথায় এটি বৈধ
শেষ

cycleFound(node k)

ইনপুট - গ্রাফের নোড।

আউটপুট - হ্যামিল্টোনিয়ান সাইকেল থাকলে True, অন্যথায় false।

শুরু
  যদি সব নোড ইনক্লুড হয়ে যায়, তবে
    যদি নোড k এবং 0-এর মধ্যে এজ থাকে, তবে
      return true
    অন্যথায়
      return false;
  স্টার্টিং পয়েন্ট ছাড়া সব ভার্টেক্স v-এর জন্য করুন
    যদি isValid(v, k) হয়, তবে //যখন v একটি বৈধ এজ
      v কে পাথে যোগ করুন
      যদি cycleFound(k+1) true হয়, তবে
        return true
      অন্যথায় pথ থেকে v রিমুভ করুন
  শেষ
  return false
শেষ

উদাহরণ

#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; //প্রথম ভার্টেক্স আবার প্রিন্ট করুন } bool isValid(int v, int k) { if (graph [path[k-1]][v] == 0) //যদি কোনো এজ নেই return false; for (int i = 0; i < k; i++) //যদি ভার্টেক্স ইতিমধ্যে নেওয়া হয়ে থাকে, স্কিপ করুন if (path[i] == v) return false; return true; } bool cycleFound(int k) { if (k == NODE) { //যখন সব ভার্টেক্স পাথে আছে if (graph[path[k-1]][ path[0] ] == 1 ) return true; else return false; } for (int v = 1; v < NODE; v++) { //স্টার্টিং পয়েন্ট ছাড়া সব ভার্টেক্সের জন্য if (isValid(v,k)) { //যদি v পাথে যোগ করা সম্ভব হয় path[k] = v; if (cycleFound (k+1) == true) return true; path[k] = -1; //যখন k ভার্টেক্স সমাধানে থাকবে না } } return false; } bool hamiltonianCycle() { for (int i = 0; i < NODE; i++) path[i] = -1; path[0] = 0; //প্রথম ভার্টেক্স 0 হিসেবে if ( cycleFound(1) == false ) { cout << "Solution does not exist"<<endl; return false; } displayCycle(); return true; } int main() { hamiltonianCycle(); }

আউটপুট

Cycle: 0 1 2 4 3 0