Fleury's Algorithm은 주어진 그래프에서 오일러 경로 또는 오일러 회로를 표시하는 데 사용됩니다. 이 알고리즘에서는 한 모서리에서 시작하여 이전 정점을 제거하여 다른 인접 정점을 이동하려고 합니다. 이 트릭을 사용하면 그래프가 오일러 경로 또는 회로를 찾기 위한 각 단계에서 더 간단해집니다.
경로 또는 회로를 얻으려면 몇 가지 규칙을 확인해야 합니다.
-
그래프는 오일러 그래프여야 합니다.
-
에지가 두 개일 때 하나는 브리지이고 다른 하나는 비 브리지이므로 처음에는 비 브리지를 선택해야 합니다.
시작 정점을 선택하는 것도 까다롭습니다. 어떤 정점도 시작 정점으로 사용할 수 없습니다. 그래프에 홀수 차수 정점이 없으면 아무 정점이나 시작점으로 선택할 수 있습니다. 그렇지 않으면 한 정점에 홀수 차수가 있으면 먼저 그 정점을 선택해야 합니다. .
알고리즘
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 dfs(prev, start, visited) Input: The pervious and start vertex to perform DFS, and visited list. Output: Count the number of nodes after DFS. Begin count := 1 visited[start] := true for all vertex b, in the graph, do if prev is not u, then if u is not visited, then if start and u are connected, then count := count + dfs(start, u, visited) end if end if end if done return count 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 v_count = number of nodes //this will not initialize in next recursion call for all vertex v, which are adjacent with start, do make visited array and will with false value if isBridge(start, v), then decrease v_count by 1 cnt = dfs(start, v, visited) if difference between cnt and v_count <= 2, then print the edge (start →‡ v) if isBridge(v, start), then decrease v_count by 1 remove edge from start and v decrease edge by 1 fleuryAlgorithm(v) end if done End
예시
#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++; //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
}
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; //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;
}
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; //remove edge from graph
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: 0--1 1--2 2--3 3--1 1--4 4--5 5--6 6--4 4--7 7--5 5--2 2--0