Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 플뢰리(Fleury) 알고리즘으로 오일러 경로와 회로 출력하기

플뢰리(Fleury) 알고리즘이란?

플뢰리(Fleury) 알고리즘은 주어진 그래프에서 오일러 경로(Euler Path) 또는 오일러 회로(Euler Circuit)를 찾아 출력하는 고전적인 알고리즘입니다. 여기서 오일러 경로란 그래프의 모든 간선을 정확히 한 번씩만 지나는 경로를 말하며, 오일러 회로는 그 경로가 다시 시작 정점으로 돌아오는 경우를 의미합니다.

이 알고리즘은 한 간선에서 출발하여 인접한 정점들을 순서대로 이동하면서, 이미 지나간 간선을 그래프에서 제거해 나가는 방식으로 동작합니다. 이 과정을 반복하면 그래프가 단계마다 점점 단순해지기 때문에 오일러 경로나 회로를 효율적으로 추적할 수 있습니다.

알고리즘 적용 시 확인해야 할 규칙

  • 그래프는 반드시 오일러 그래프여야 합니다. 즉, 연결 그래프이면서 오일러 경로 또는 회로가 존재하는 조건을 만족해야 합니다.
  • 두 개의 간선 중 하나가 다리(bridge)이고 다른 하나가 다리가 아니라면, 반드시 다리가 아닌 간선을 먼저 선택해야 합니다. 다리란 제거했을 때 그래프가 둘 이상의 연결 요소로 분리되는 간선을 말합니다.

시작 정점 선택 방법

시작 정점을 고르는 것도 매우 중요합니다. 임의의 정점을 무조건 시작점으로 삼을 수는 없습니다.

  • 그래프에 홀수 차수(odd degree) 정점이 없는 경우: 모든 정점의 차수가 짝수이므로 오일러 회로가 존재하며, 어떤 정점이든 시작점으로 선택할 수 있습니다.
  • 홀수 차수 정점이 존재하는 경우: 오일러 경로만 존재하며(홀수 차수 정점은 정확히 2개), 반드시 그 홀수 차수 정점 중 하나를 시작점으로 선택해야 합니다.

입력 및 출력 예시

입력 − 그래프의 인접 행렬

01111
10111
11011
11101
11110

출력 − 오일러 경로 또는 회로: 1--0  0--2  2--1  1--3  3--0  0--4  4--3  3--2

알고리즘 (의사코드)

findStartVert(graph)
입력: 주어진 그래프
출력: 알고리즘을 시작할 시작 정점을 찾음
Begin
    그래프의 모든 정점 i에 대해 반복
        deg := 0
        i와 인접한 모든 정점 j에 대해 반복
            deg := deg + 1
        done
        만약 deg가 홀수라면
            return i   // 홀수 차수 정점을 시작점으로 반환
        done
    모든 차수가 짝수이면 return 0
End

isBridge(u, v)
입력: 시작 노드 u와 끝 노드 v
출력: u와 v가 다리(bridge)를 형성하면 true
Begin
    deg := 0
    v와 인접한 모든 정점 i에 대해 반복
        deg := deg + 1
    done
    만약 deg > 1이라면
        return false   // 다리를 형성하지 않음
    return true        // 다리를 형성함
End

fleuryAlgorithm(start)
입력: 시작 정점
출력: 오일러 경로 또는 회로를 출력
Begin
    edge := 그래프의 간선 수 가져오기  // 재귀 호출 시 재초기화되지 않음
    start와 인접한 모든 정점 v에 대해 반복
        만약 edge <= 1 OR isBridge(start, v)가 false라면
            start에서 v로 가는 경로 출력
            그래프에서 간선 (start, v) 제거
            edge 1 감소
            fleuryAlgorithm(v) 재귀 호출
    done
End

C++ 구현 예제

#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++; //연결된 간선을 발견하면 차수 증가
      }
      if(deg % 2 != 0) //정점의 차수가 홀수인 경우
      return i; //i는 홀수 차수를 가진 노드
   }
   return 0; //모든 정점의 차수가 짝수이면 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; //해당 간선은 다리를 형성하지 않음
      }
   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();
   for(int v = 0; v<NODE; v++){
      if(tempGraph[start][v]){ //(u,v) 간선이 존재하고 다리를 형성하지 않는 경우
         if(edge <= 1 || !isBridge(start, v)){
            cout << start << "--" << v << " ";
            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: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3--2