সি++ এ ইউলারিয়ান পাথ বা সার্কিট প্রিন্ট করার জন্য ফ্লুরির অ্যালগরিদম

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

পাথ বা সার্কিট −

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

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

ইনপুট − একটি গ্রাফের সংলগ্নতা ম্যাট্রিক্স

আউটপুট − অয়লার পাথ বা সার্কিট:1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2

অ্যালগরিদম

findStartVert(graph)
Input: The given graph.
Output: Find the starting vertex to start algorithm.
Begin
   for all vertex i, in the graph, do
      deg := 0
      for all vertex j, which are adjacent with i, do
         deg := deg + 1
      done
      if deg is odd, then
         return i
      done
      when all degree is even return 0
End
isBridge(u, v)
Input: The start and end node.
Output: True when u and v are forming a bridge.
Begin
   deg := 0
   for all vertex i which are adjacent with v, do
      deg := deg + 1
   done
   if deg > 1, then
      return false
   return true
End
fleuryAlgorithm(start)
Input: The starting vertex.
Output: Display the Euler path or circuit.
Begin
   edge := get the number of edges in the graph //it will not initialize in next
   recursion call
   for all vertex v, which are adjacent with start, do
      if edge <= 1 OR isBridge(start, v) is false, then
         display path from start and v
         remove edge (start,v) from the graph
         decrease edge by 1
         fleuryAlgorithm(v)
   done
End

উদাহরণ

#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 1, 1, 1, 1},
   {1, 0, 1, 1, 0},
   {1, 1, 0, 1, 0},
   {1, 1, 1, 0, 1},
   {1, 0, 0, 1, 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++; //increase degree, when connected edge found
      }
      if(deg % 2 != 0) //when degree of vertices are odd
      return i; //i is node with odd degree
   }
   return 0; //when all vertices have even degree, start from 0
}
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; //the edge is not forming bridge
      }
   return true; //edge forming a bridge
}
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; //count nunber of edges in the graph
}
void fleuryAlgorithm(int start){
   static int edge = edgeCount();
   for(int v = 0; v<NODE; v++){
      if(tempGraph[start][v]){ //when (u,v) edge is presnt and not forming bridge
         if(edge <= 1 || !isBridge(start, v)){
            cout << start << "--" << v << " ";
            tempGraph[start][v] = tempGraph[v][start] = 0; //remove edge from graph
            edge--; //reduce edge
            fleuryAlgorithm(v);
         }
      }
   }
}
int main(){
   for(int i = 0; i<NODE; i++) //copy main graph to 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: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2