फ्लेरी का एल्गोरिदम दिए गए ग्राफ से यूलर पथ या यूलर सर्किट प्रदर्शित करने के लिए उपयोग किया जाता है। इस एल्गोरिदम में, एक किनारे से शुरू करके, यह पिछले शीर्षों को हटाकर अन्य आसन्न शीर्षों पर जाने का प्रयास करता है। इस ट्रिक का उपयोग करके, ग्राफ प्रत्येक चरण में सरल होता जाता है ताकि यूलर पथ या सर्किट मिल सके।
पथ या सर्किट प्राप्त करने के लिए हमें कुछ नियमों की जांच करनी होगी -
ग्राफ एक यूलर ग्राफ होना चाहिए।
जब दो किनारे हों, एक ब्रिज हो, दूसरा नॉन-ब्रिज हो, तो हमें पहले नॉन-ब्रिज को चुनना होगा।
शुरुआती शीर्ष का चयन भी मुश्किल है, हम किसी भी शीर्ष को शुरुआती बिंदु के रूप में उपयोग नहीं कर सकते, यदि ग्राफ में कोई विषम डिग्री वाले शीर्ष नहीं हैं, तो हम किसी भी शीर्ष को शुरुआती बिंदु के रूप में चुन सकते हैं, अन्यथा जब एक शीर्ष की डिग्री विषम हो, तो हमें उसे पहले चुनना होगा।
एल्गोरिदम
findStartVert(graph) इनपुट: दिया गया ग्राफ। आउटपुट: एल्गोरिदम शुरू करने के लिए शुरुआती शीर्ष खोजें। शुरू ग्राफ में सभी शीर्ष i के लिए, करें deg := 0 i के साथ आसन्न सभी शीर्ष j के लिए, करें deg := deg + 1 किया यदि deg विषम है, तो वापस करें i किया जब सभी डिग्री सम हों तो 0 वापस करें अंत dfs(prev, start, visited) इनपुट: DFS करने के लिए पिछला और प्रारंभिक शीर्ष, और देखी गई सूची। आउटपुट: DFS के बाद नोड्स की संख्या गिनें। शुरू count := 1 visited[start] := सच ग्राफ में सभी शीर्ष b के लिए, करें यदि prev, u नहीं है, तो यदि u नहीं देखा गया है, तो यदि start और u जुड़े हुए हैं, तो count := count + dfs(start, u, visited) अंत यदि अंत यदि अंत यदि किया count वापस करें अंत isBridge(u, v) इनपुट: प्रारंभ और अंत नोड। आउटपुट: जब u और v ब्रिज बना रहे हों तो सच। शुरू deg := 0 v के साथ आसन्न सभी शीर्ष i के लिए, करें deg := deg + 1 किया यदि deg > 1, तो वापस करें गलत वापस करें सच अंत fleuryAlgorithm(start) इनपुट: प्रारंभिक शीर्ष। आउटपुट: यूलर पथ या सर्किट प्रदर्शित करें। शुरू edge := ग्राफ में किनारों की संख्या प्राप्त करें //यह अगले पुनरावृत्ति कॉल में आरंभ नहीं होगा v_count = नोड्स की संख्या //यह अगले पुनरावृत्ति कॉल में आरंभ नहीं होगा start के साथ आसन्न सभी शीर्ष v के लिए, करें विज़िटेड सरणी बनाएं और गलत मान से भरें यदि isBridge(start, v), तो v_count को 1 से घटाएं cnt = dfs(start, v, visited) यदि cnt और v_count के बीच अंतर <= 2, तो किनारे को प्रिंट करें (start → v) यदि isBridge(v, start), तो v_count को 1 से घटाएं start और v से किनारा हटाएं edge को 1 से घटाएं fleuryAlgorithm(v) अंत यदि किया अंत
उदाहरण
#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; i1) { return false; //किनारा ब्रिज नहीं बना रहा } return true; //किनारा ब्रिज बना रहा है } int edgeCount() { int count = 0; for(int i = 0; i
आउटपुट
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
