오일러 경로와 오일러 회로

오일러 경로(Eulerian Path)와 오일러 회로(Eulerian Circuit)

오일러 경로(Eulerian Path)

정의 : 그래프의 모든 간선을 정확히 한 번씩만 지나고, 서로 다른 두 정점에서 시작하고 끝나는 경로입니다.

조건 : 연결된 그래프에서 차수가 홀수인 정점이 정확히 2개여야 합니다.

오일러 회로(Eulerian Circuit)

정의 : 그래프의 모든 간선을 정확히 한 번씩만 지나고, 같은 정점에서 시작하고 끝나는 경로입니다.
즉, 경로가 하나의 사이클을 이룹니다.

조건 : 연결된 그래프에서 모든 정점의 차수가 짝수여야 합니다.

결론적으로, 오일러 경로와 오일러 회로는 그래프의 모든 간선을 정확히 한 번씩만 지나갈 수 있는지 여부를 묻는 것입니다.

---

방향 그래프와 무방향 그래프

• 무방향 그래프

오일러 회로 : 모든 정점의 차수가 짝수여야 하고, 그래프가 연결되어 있어야 합니다.

오일러 경로 : 차수가 홀수인 정점이 정확히 2개이고, 나머지 정점은 모두 짝수 차수여야 합니다.

• 방향 그래프

오일러 회로 : 모든 정점의 진입 차수(in-degree)와 진출 차수(out-degree)가 같아야 하고, 그래프가 강하게 연결되어 있어야 합니다.

오일러 경로 : 진출 차수가 진입 차수보다 1 큰 정점이 하나 있고(시작점), 진입 차수가 진출 차수보다 1 큰 정점이 하나 있으며(끝점), 나머지 모든 정점은 진입 차수와 진출 차수가 같아야 합니다.

---

히어홀저(Hierholzer) 알고리즘

import java.io.*;
import java.util.*;

public class Test {

    private static BufferedReader br;
    private LinkedList<LinkedList<Integer>> adj; // 인접 리스트
    private int numVertices;
    private int numEdges;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        Test graph = new Test(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(3, 4);
        List<Integer> circuit = graph.findEulerianCircuit(0);

        if (circuit != null) {
            System.out.println("오일러 회로: " + circuit);
        } else {
            System.out.println("오일러 회로가 존재하지 않습니다.");
        }

        return sb.toString();
    } // End of solve()

    public void addEdge(int v, int w) {
        adj.get(v).add(w);
        adj.get(w).add(v);
        numEdges++;
    } // End of addEdge()

    public Test(int numVertices) {
        this.numVertices = numVertices;
        adj = new LinkedList<>();
        for (int i = 0; i < numVertices; i++) {
            adj.add(new LinkedList<>());
        }
        numEdges = 0;
    }

    private boolean isEulerianCircuit() {
        // 연결성 검사는 생략 (연결 그래프라고 가정)

        for (int i = 0; i < numVertices; i++) {
            if (adj.get(i).size() % 2 != 0) {
                return false; // 홀수 차수 정점이 있으면 오일러 회로 없음
            }
        }

        return true;
    } // End of isEulerianCircuit()

    public List<Integer> findEulerianCircuit(int startVertex) {
        if (!isEulerianCircuit()) {
            return null; // 오일러 회로가 존재하지 않음
        }

        // 간선을 복사하여 사용 (원본 그래프를 수정하지 않기 위해)
        LinkedList<LinkedList<Integer>> tempAdj = new LinkedList<>();
        for (int i = 0; i < numVertices; i++) {
            tempAdj.add(new LinkedList<>());
            for (int neighbor : adj.get(i)) {
                tempAdj.get(i).add(neighbor);
            }
        }

        Stack<Integer> stack = new Stack<>();
        List<Integer> circuit = new ArrayList<>();
        stack.push(startVertex);

        while (!stack.isEmpty()) {
            System.out.println(stack);
            int cur = stack.peek();

            if (!tempAdj.get(cur).isEmpty()) {
                int next = tempAdj.get(cur).removeFirst();

                // 반대편 간선 제거
                // 방향 그래프에서는 반대편 간선이 없으므로 제거하는 코드가 없다.
                int size = tempAdj.size();
                for (int i = 0; i < size; ++i) {
                    if (tempAdj.get(next).get(i) == cur) {
                        tempAdj.get(next).remove(i);
                        break;
                    }
                }

                stack.push(next);
            } else {
                circuit.add(stack.pop());
            }
        }

        Collections.reverse(circuit);
        return circuit;
    } // End of findEulerianCircuit()
} // End of Main class

방향 그래프에서는 반대편 간선을 제거하지 않습니다.