플뢰리 알고리즘(Fleury's Algorithm): 오일러 경로와 오일러 회로 찾기

플뢰리 알고리즘(Fleury's Algorithm)은 주어진 그래프에서 오일러 경로(Euler Path) 또는 오일러 회로(Euler Circuit)를 찾아 출력하는 고전적인 그래프 알고리즘입니다. 이 알고리즘은 한 간선에서 출발하여 지나온 간선과 정점을 제거하면서 인접한 다른 정점으로 이동하는 방식을 반복합니다. 매 단계마다 그래프가 점점 단순해지기 때문에 오일러 경로나 회로를 체계적으로 찾을 수 있습니다.

플뢰리 알고리즘의 기본 규칙

경로 또는 회로를 올바르게 구하기 위해서는 다음 두 가지 규칙을 반드시 확인해야 합니다.

• 그래프는 반드시 오일러 그래프(Euler Graph)여야 합니다. 즉, 모든 정점의 차수(degree) 조건을 만족해야 합니다.

• 두 개의 간선 중 하나가 브리지(bridge)이고 다른 하나가 비브리지(non-bridge)라면, 반드시 비브리지를 먼저 선택해야 합니다. 브리지를 성급하게 제거하면 그래프가 분리되어 나머지 간선을 모두 순회할 수 없게 되기 때문입니다.

시작 정점 선택 방법

시작 정점 선택 역시 신중해야 하며, 아무 정점이나 임의로 사용할 수 없습니다.

• 그래프에 홀수 차수(odd degree)를 가진 정점이 없다면, 어떤 정점이든 시작점으로 선택할 수 있습니다. 이 경우 결과는 오일러 회로가 됩니다.

• 홀수 차수를 가진 정점이 존재한다면, 반드시 그 정점부터 시작해야 합니다. 이 경우 결과는 오일러 경로가 됩니다.

알고리즘 의사코드

findStartVert(graph)
입력: 주어진 그래프
출력: 알고리즘을 시작할 시작 정점
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)
입력: DFS를 수행할 이전 정점과 시작 정점, 방문 목록
출력: 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)
입력: 시작 노드와 끝 노드
출력: u와 v가 브리지를 형성하면 true
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)
입력: 시작 정점
출력: 오일러 경로 또는 오일러 회로 출력
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

C++ 구현 예제

아래는 플뢰리 알고리즘을 C++로 구현한 전체 코드입니다. 인접 행렬(adjacency matrix) 형태로 그래프를 표현하며, 시작 정점 탐색, DFS 기반 연결성 확인, 브리지 판별, 간선 제거 과정을 재귀적으로 수행합니다.

#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

출력 결과를 보면 정점 0에서 시작하여 모든 간선을 정확히 한 번씩만 지나며 여덟 개의 정점을 순회하는 것을 확인할 수 있습니다. 이처럼 플뢰리 알고리즘은 브리지를 최대한 늦게 건너는 전략을 통해 유효한 오일러 경로·회로를 안정적으로 찾아냅니다.