ফ্লেরি'স অ্যালগরিদম (Fleury's Algorithm)

ফ্লেরি'স অ্যালগরিদম ব্যবহার করা হয় একটি প্রদত্ত গ্রাফ থেকে অয়লার পথ বা অয়লার সার্কিট প্রদর্শন করতে। এই অ্যালগরিদমে, একটি এজ থেকে শুরু করে, এটি পূর্বের ভার্টেক্সগুলো সরিয়ে অন্যান্য সন্নিহিত ভার্টেক্সের দিকে যাওয়ার চেষ্টা করে। এই ট্রিক ব্যবহার করে, প্রতিটি ধাপে গ্রাফটি সরল হয়ে যায় যাতে অয়লার পথ বা সার্কিট খুঁজে বের করা যায়।

পথ বা সার্কিট পেতে কিছু নিয়ম যাচাই করতে হয় −

• গ্রাফটি অবশ্যই একটি অয়লার গ্রাফ হতে হবে।
• যখন দুটি এজ থাকে, একটি ব্রিজ আরেকটি নন-ব্রিজ, তবে আমাদের প্রথমে নন-ব্রিজটি বেছে নিতে হবে।

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

এলগরিদম

findStartVert(graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: অ্যালগরিদম শুরু করার জন্য শুরুর ভার্টেক্স খুঁজে বের করুন।
শুরু
  গ্রাফের সব ভার্টেক্স i এর জন্য, করুন
    deg := 0
    i-র সাথে সন্নিহিত সব ভার্টেক্স j এর জন্য, করুন
      deg := deg + 1
    শেষ লুপ
    যদি deg বিজোড় হয়, তবে
      return i
  শেষ লুপ
  যখন সব ডিগ্রি জোড়, 0 ফেরত দিন
শেষ

dfs(prev, start, visited)
ইনপুট: DFS করার জন্য পূর্বের এবং শুরুর ভার্টেক্স, এবং ভিজিটেড লিস্ট।
আউটপুট: DFS-এর পর নোডের সংখ্যা গণনা করুন।
শুরু
  count := 1
  visited[start] := true
  গ্রাফের সব ভার্টেক্স b এর জন্য, করুন
    যদি prev u না হয়, তবে
      যদি u ভিজিটেড না থাকে, তবে
        যদি start এবং u সংযুক্ত থাকে, তবে
          count := count + dfs(start, u, visited)
        শর্ত শেষ
      শর্ত শেষ
    শর্ত শেষ
  শেষ লুপ
  return count
শেষ

isBridge(u, v)
ইনপুট: শুরুর এবং শেষ নোড।
আউটপুট: u এবং v ব্রিজ তৈরি করলে true।
শুরু
  deg := 0
  v-র সাথে সন্নিহিত সব ভার্টেক্স i এর জন্য, করুন
    deg := deg + 1
  শেষ লুপ
  যদি deg > 1, তবে
    return false
  return true
শেষ

fleuryAlgorithm(start)
ইনপুট: শুরুর ভার্টেক্স।
আউটপুট: অয়লার পথ বা সার্কিট প্রদর্শন করুন।
শুরু
  edge := গ্রাফে এজের সংখ্যা পান
    // এটি পরবর্তী রিকারসিভ কলে আর ইনিশিয়ালাইজ হবে না
  v_count = নোডের সংখ্যা
    // এটিেও পরবর্তী রিকারসিভ কলে আর ইনিশিয়ালাইজ হবে না
  start-র সাথে সন্নিহিত সব ভার্টেক্স v এর জন্য, করুন
    ভিজিটেড অ্যারে তৈরি করুন এবং false দিয়ে পূরন করুন
    যদি isBridge(start, v), তবে v_count কে ১ কমান
    cnt = dfs(start, v, visited)
    যদি cnt এবং v_count-এর পার্থক্য <= 2, তবে
      এজ (start → v) প্রিন্ট করুন
      যদি isBridge(v, start), তবে v_count কে ১ কমান
      start এবং v থেকে এজ সরিয়ে দিন
      edge কে ১ কমান
      fleuryAlgorithm(v)
    শর্ত শেষ
  শেষ লুপ
শেষ

উদাহরণ (C++ কোড)

#include <iostream>
#include <vector>
#include <cmath>
#define NODE 8
using namespace std;

int graph[NODE][NODE] = {
  {0,1,1,0,0,0,0,0},
  {1,0,1,1,1,0,0,0},
  {1,1,0,1,0,1,0,0},
  {0,1,1,0,0,0,0,0},
  {0,1,0,0,0,1,1,1},
  {0,0,1,0,1,0,1,1},
  {0,0,0,0,1,1,0,0},
  {0,0,0,0,1,1,0,0}
};

int tempGraph[NODE][NODE];

int findStartVert() {
  for(int i = 0; i < NODE; i++) {
    int deg = 0;
    for(int j = 0; j < NODE; j++) {
      if(tempGraph[i][j])
        deg++; // সংযুক্ত এজ পাওয়া যাওয়ার সময় ডিগ্রি বাড়ান
    }
    if(deg % 2 != 0) // যখন ভার্টেক্সের ডিগ্রি বিজোড়
      return i; // i হলো বিজোড় ডিগ্রির নোড
  }
  return 0; // সব ভার্টেক্সের ডিগ্রি জোড় হলে 0 থেকে শুরু করুন
}

int dfs(int prev, int start, bool visited[]){
  int count = 1;
  visited[start] = true;
  for(int u = 0; u < NODE; u++){
    if(prev != u){
      if(!visited[u]){
        if(tempGraph[start][u]){
          count += dfs(start, u, visited);
        }
      }
    }
  }
  return count;
}

bool isBridge(int u, int v) {
  int deg = 0;
  for(int i = 0; i < NODE; i++)
    if(tempGraph[v][i])
      deg++;
  if(deg > 1) {
    return false; // এজটি ব্রিজ তৈরি করছে না
  }
  return true; // এজটি একটি ব্রিজ তৈরি করছে
}

int edgeCount() {
  int count = 0;
  for(int i = 0; i < NODE; i++)
    for(int j = i; j < NODE; j++)
      if(tempGraph[i][j])
        count++;
  return count;
}

void fleuryAlgorithm(int start) {
  static int edge = edgeCount();
  static int v_count = NODE;
  for(int v = 0; v < NODE; v++) {
    if(tempGraph[start][v]) {
      bool visited[NODE] = {false};
      if(isBridge(start, v)){
        v_count--;
      }
      int cnt = dfs(start, v, visited);
      if(abs(v_count - cnt) <= 2){
        cout << start << "--" << v << " ";
        if(isBridge(v, start)){
          v_count--;
        }
        tempGraph[start][v] = tempGraph[v][start] = 0; // গ্রাফ থেকে এজ সরান
        edge--;
        fleuryAlgorithm(v);
      }
    }
  }
}

int main() {
  for(int i = 0; i < NODE; i++) // মূল গ্রাফকে tempGraph-এ কপি করুন
    for(int j = 0; j < NODE; j++)
      tempGraph[i][j] = graph[i][j];
  cout << "Euler Path Or Circuit: ";
  fleuryAlgorithm(findStartVert());
}

আউটপুট

Euler Path Or Circuit: 0--1 1--2 2--3 3--1 1--4 4--5 5--6 6--4 4--7 7--5 5--2 2--0