ফ্লুরির অ্যালগরিদম

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

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

• গ্রাফটি অবশ্যই অয়লার গ্রাফ হতে হবে।

• যখন দুটি প্রান্ত থাকে, একটি সেতু, আরেকটি নন-ব্রিজ, আমাদের প্রথমে নন-ব্রিজ বেছে নিতে হবে।

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

অ্যালগরিদম

findStartVert(গ্রাফ)ইনপুট:প্রদত্ত গ্রাফ। আউটপুট:অ্যালগরিদম শুরু করতে প্রারম্ভিক শীর্ষস্থানটি খুঁজুন। সমস্ত শীর্ষবিন্দুর জন্য শুরু করুন i, গ্রাফে, do deg :=0 সমস্ত শীর্ষ j-এর জন্য, যেগুলি i, do সংলগ্ন। deg :=deg + 1 করা হয়েছে যদি deg বিজোড় হয়, তারপর i সম্পন্ন করে ফেরত দিন যখন সব ডিগ্রি সমান হয় 0Enddfs (আগের, শুরু, পরিদর্শন করা) ইনপুট:ডিএফএস সম্পাদন করতে pervious এবং start vertex, এবং visited list. Output:সংখ্যা গণনা করুন DFS-এর পরে নোডের সংখ্যা। শুরু করা গণনা :=1 পরিদর্শন করা হয়েছে[শুরু] :=গ্রাফে সমস্ত শীর্ষবিন্দুর জন্য সত্য, যদি পূর্বে u না হয় তাহলে কর, তারপর যদি u পরিদর্শন না করা হয়, তারপর যদি start এবং u সংযুক্ত থাকে, তাহলে গণনা করুন। :=count + dfs(start, u, visited) end if end if end যদি সম্পন্ন করা হয় তাহলে রিটার্ন কাউন্টEndisBridge(u, v)ইনপুট:স্টার্ট এবং এন্ড নোড। আউটপুট:সত্য যখন u এবং v একটি সেতু তৈরি করছে। Begin deg :=v এর সাথে সংলগ্ন সকল শীর্ষবিন্দু i এর জন্য 0, do deg :=deg + 1 সম্পন্ন হলে deg> 1 হলে মিথ্যা ফেরত দিন রিটার্ন trueEndfleuryAlgorithm(start)Input:The starting vertex.Output:প্রদর্শন করুন অয়লার পাথ বা সার্কিট। Begin edge :=গ্রাফে প্রান্তের সংখ্যা পান //এটি পরবর্তী রিকারশন কলে আরম্ভ হবে না v_count =নোডের সংখ্যা //এটি স্টার্টের সংলগ্ন সমস্ত ভার্টেক্স v-এর জন্য পরবর্তী রিকারশন কলে আরম্ভ করবে না, ভিজিট করা অ্যারে তৈরি করবে এবং যদি isBridge(start, v), তাহলে v_count 1 cnt =dfs(start, v, visited) দ্বারা কমিয়ে ফেলবে। যদি cnt এবং v_count <=2 এর মধ্যে পার্থক্য থাকে, তাহলে প্রান্তটি প্রিন্ট করুন (start →‡v) যদি isBridge(v, start), তারপর v_count 1 কমিয়ে প্রান্তটি শুরু থেকে সরিয়ে ফেলুন এবং v 1 ফ্লুরিঅ্যালগোরিদম(v) শেষ হলে প্রান্তটি কমিয়ে দিন 

উদাহরণ

#include#include#include#define NODE 8 ব্যবহার করে namespace std;int গ্রাফ[NODE][NODE] ={ {0,1,1,0,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; i1) { মিথ্যা ফেরত দিন; //প্রান্ত সেতু তৈরি করছে না } রিটার্ন সত্য; // edge forming a bridge}int edgeCount() { int count =0; for(int i =0; i 
আউটপুট
 অয়লার পাথ বা সার্কিট:0--1 1--2 2--3 3--1 1--4 4--5 5--6 6--4 4--7 7--5 5- -2 2--0