오일러 경로(Eulerian Path) 알고리즘

---

오일러 경로(Eulerian Path)는 그래프 내의 모든 간선을 정확히 한 번씩 통과하는 경로를 의미합니다.

만약 이러한 경로가 시작 정점과 종료 정점이 동일하다면, 이를 오일러 회로(Eulerian Circuit)라 합니다.

오일러 경로와 회로는 그래프 이론에서 매우 중요한 개념으로, 특정 조건을 만족하는 경로의 존재 여부를 판별하고 찾는 데 중요한 역할을 합니다.

오일러 경로 알고리즘의 개념

---

오일러 경로를 찾기 위해 그래프의 특성을 분석하는 것이 중요합니다. 오일러 경로와 회로를 판별하기 위한 조건은 다음과 같습니다:

1. 오일러 회로의 조건:

   • 모든 정점의 차수(degree)가 짝수여야 합니다.
   • 그래프는 연결 그래프(connected graph)여야 합니다.

2. 오일러 경로의 조건:

   • 정확히 두 개의 정점이 홀수 차수를 가져야 합니다.
   • 그래프는 연결 그래프여야 합니다.

위 조건에 따라, 그래프를 탐색하여 오일러 경로를 판별하고 경로를 찾을 수 있습니다.

예시

다음과 같은 그래프가 있다고 가정합시다:

1 -- 2 -- 3 
|         | 
4 ------- 5

1. 각 정점의 차수를 확인합니다:

   • 정점 1: 차수 2
   • 정점 2: 차수 2
   • 정점 3: 차수 2
   • 정점 4: 차수 3
   • 정점 5: 차수 3

2. 차수가 홀수인 정점이 2개이므로, 오일러 경로가 존재합니다.

오일러 경로 알고리즘의 구현

---

C언어로 오일러 경로 알고리즘을 구현한 코드는 다음과 같습니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 1000

int graph[MAX][MAX]; // 인접 행렬
int visited[MAX];
int degree[MAX];
int n; // 정점의 개수
int m; // 간선의 개수

// 그래프 초기화
void initGraph() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            graph[i][j] = 0;
        }
        visited[i] = 0;
        degree[i] = 0;
    }
}

// 간선 추가
void addEdge(int u, int v) {
    graph[u][v]++;
    graph[v][u]++;
    degree[u]++;
    degree[v]++;
}

// DFS를 이용한 연결성 확인
void dfs(int node) {
    visited[node] = 1;
    for (int i = 0; i < n; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(i);
        }
    }
}

// 오일러 경로 판별
bool isEulerian() {
    int odd = 0; // 홀수 차수를 가진 정점의 개수
    for (int i = 0; i < n; i++) {
        if (degree[i] % 2 != 0) {
            odd++;
        }
    }

    // 홀수 차수 정점이 0개 또는 2개일 때 오일러 경로가 존재
    return (odd == 0 || odd == 2);
}

// 오일러 경로 탐색
void findEulerPath(int start) {
    for (int i = 0; i < n; i++) {
        if (graph[start][i]) {
            graph[start][i]--;
            graph[i][start]--;
            findEulerPath(i);
        }
    }
    printf("%d ", start);
}

int main() {
    int u, v;
    initGraph();

    printf("정점과 간선의 개수를 입력하세요 (n m): ");
    scanf("%d %d", &n, &m);

    printf("간선 정보를 입력하세요 (u v):\n");
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }

    dfs(0);

    if (!isEulerian()) {
        printf("오일러 경로가 존재하지 않습니다.\n");
    } else {
        printf("오일러 경로: ");
        findEulerPath(0);
        printf("\n");
    }

    return 0;
}

오일러 경로 알고리즘 특징

---

장점:
모든 간선을 정확히 한 번씩 방문하는 문제를 해결할 수 있습니다.
DFS를 기반으로 구현하면 비교적 간단하게 해결 가능.

단점:
간선이 많거나 정점의 개수가 많을 경우 메모리 사용량이 증가합니다.
연결성 확인 및 차수 계산 과정에서 추가 연산이 필요합니다.

오일러 경로 알고리즘의 시간 복잡도

---

• DFS 기반 탐색: $O(V + E)$ (정점 수와 간선 수에 비례)

• 차수 계산 및 판별: $O(V)$

• 전체 시간 복잡도: $O(V + E)$

정리

---

오일러 경로 알고리즘은 그래프 내의 모든 간선을 한 번씩 방문하는 문제를 해결하는 데 매우 강력한 도구입니다.

연결된 그래프에서 정점의 차수를 이용해 경로 또는 회로의 존재 여부를 효율적으로 판별할 수 있으며, DFS 기반의 재귀적 탐색을 통해 실제 경로를 찾습니다.

이러한 알고리즘적 특성 덕분에 오일러 경로는 네트워크 경로 최적화 🌐, 도시 기반시설 계획 🏙️, 물류 관리 🚚 등 다양한 응용 분야에서 널리 활용되고 있습니다.