[c++] 오일러 서킷 알고리즘

08 Dec 2023

오일러 서킷(Eulerian circuit)은 그래프 이론에서 모든 간선을 한 번씩만 지나가면서 모든 정점을 연결하는 경로를 의미합니다. 따라서 오일러 서킷 알고리즘은 그래프에서 오일러 서킷을 찾는 알고리즘입니다.

알고리즘 설명

오일러 서킷 알고리즘은 모든 정점의 차수가 짝수인 경우에만 적용할 수 있습니다. 아래는 그래프에서 오일러 서킷을 찾는 알고리즘의 간단한 예제 코드입니다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void findEulerianCircuit(vector<vector<int>>& graph, int start) {
    stack<int> currPath;
    vector<int> circuit;
    currPath.push(start);

    while (!currPath.empty()) {
        int curr = currPath.top();
        if (!graph[curr].empty()) {
            int next = graph[curr].back();
            graph[curr].pop_back();
            currPath.push(next);
        } else {
            circuit.push_back(currPath.top());
            currPath.pop();
        }
    }

    for (auto it = circuit.rbegin(); it != circuit.rend(); ++it) {
        cout << *it << " ";
    }
}

int main() {
    int V = 4; // 정점의 수
    vector<vector<int>> graph(V);
    graph[0] = {1, 2};
    graph[1] = {2, 3};
    graph[2] = {0, 3};
    graph[3] = {3};

    findEulerianCircuit(graph, 0);

    return 0;
}

위 코드는 인접 행렬이 아닌 인접 리스트를 사용하여 그래프를 표현하고, 스택을 이용하여 오일러 서킷을 찾는 방법을 보여줍니다.

마무리

오일러 서킷 알고리즘은 그래프 이론에서 중요한 알고리즘 중 하나이며, 그래프 내에 오일러 서킷이 존재하는 지 확인하는 것은 매우 유용합니다. 따라서 이 알고리즘을 효율적으로 구현하는 것은 그래프 이론에 대한 깊은 이해를 가져다 줄 것입니다.

참고: GeeksforGeeks - Euler Circuits