11. 그래프 - 무방향 그래프 사이클 판별, 최소 신장 트리

서로소 집합 자료구조

• 서로소 집합 정의: 공통 원소가 없는 두 집합
  • 예시)
    • 서로소o: {1,2} {3,4}
    • 서로소x: {1,2} {2,3}
• 서로소 집합 자료구조 정의: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하는 자료구조
• 2가지 연산 지원
  • 합집합(Union): 2개의 집합을 하나의 집합으로 합치는 연산
  • 찾기(Find): 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산

 

1. 합집합 연산을 통해, 노드 A와 B를 연결
   1. A와 B의 루트 노드인 A`과 B`을 찾기
   2. A`과 B`을 부모 노드로 설정
2. 모든 합집합 연산을 처리할때까지 1번 연산 반복

 

진행 흐름

• 서로소 집합을 합치는 과정은 다음과 같이 진행된다.
• 예시) if 노드가 1~6번까지 존재하고, 4가지 합치는 연산이 존재하는 경우 

 

1. 부모 테이블 초기화

• 초기에는 자기 자신이 부모가 되도록 부모 테이블을 초기화

 

코드

// 노드의 개수 만큼 부모 테이블 생성
int[] parent = new int[n+1];

//부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
    parent[i] = i;
}

 

 

작동 방식

 

 

2. 연산 개수 만큼 반복을 통해 부모 테이블 갱신

1. 합집합 연산을 통해, 노드 A와 B를 연결
   • A와 B의 루트 노드인 A`과 B`을 찾기
   • A`와 B` 중 노드 번호가 더 작은 것을 루트 노드로 설정
     • 일반적으로 번호가 작은 노드가 루트 노드가 되도록 함

루트 노드가 동일하면 같은 집합에 포함된 것

 

코드

public static void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

// Union 연산을 각각 수행
for (int i = 0; i < e; i++) {
    int a = sc.nextInt();
    int b = sc.nextInt();
    unionParent(a, b);
}

 

 

작동 방식

 

 

3. 최종 결과

최종적으로 아래처럼 2개의 집합이 발생하고, 2개의 잡합은 서로 서로소 관계

같은 집합에 포함되어있는지는 연결성을 통해 확인 가능

• 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라감

 

 

경로 압축

해당 알고리즘을 사용하면 루트 노드가 부모 노드가 되도록 테이블이 갱신됨 (성능 개선)

• 찾기(find) 함수를 최적화하기 위해 경로 압축 기법을 사용 가능
• 찾기 함수를 재귀적으로 호출한 뒤, 부모 테이블 값을 바로 갱신

public static int findParent(int x){
    //자기 자신을 가리키는 것이 루트 노드
    if(parent[x] == x) return x;
    return parent[x] = findParent(parent[x]);
}

 

 

최종 코드

public class Main {
    static int v, e;
    static int[] parent;

    public static int findParent(int x){
        //자기 자신을 가리키는 것이 루트 노드
        if(parent[x] == x) return x;
        return parent[x] = findParent(parent[x]);
    }

    public static void unionParent(int a, int b){
        int a_ = findParent(a);
        int b_ = findParent(b);

        //a_와 b_중 더 작은 값을 루트 노드로 설정
        if(a_ < b_){
            parent[b_] = a_;
        } else {
            parent[a_] = b_;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        //1. 부모 테이블 초기화
        parent = new int[v+1];

        for(int i=1; i<=v; i++){
            parent[i] = i;
        }

        //2. 합집합 연산 개수만큼 반복
        for(int i=0; i<e; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            unionParent(a,b);
        }

        //3. 최종 결과 확인
        for (int i = 1; i <= v; i++) {
            System.out.print(parent[i] + " ");
        }
        System.out.println();
    }
}

 

 

활용처

무방향 그래프 사이클 판별

• 무방향 그래프 내에서 사이클을 판별할 때 사용 가능
  • 방향 그래프 내에서 사이클 여부는 DFS를 이용하여 판별 가능
• 동작 과정 요약
  1. 그래프의 모든 간선을 하나씩 확인하여 두 노드의 루트 노드 확인
     • 루트 노드가 서로 다른 경우: 두 노드에 대해서 합집합 연산 진행
     • 루트 노드가 서로 같은 경우: 사이클(cycle) 발생
  2. 모든 과정에서 루트 노드가 같은 경우가 나오지 않았다면 사이클이 없는 것

 

 

 

 

 

 

 

public class struct {

    static int[] parents;
    public static void main(String[] args) throws IOException {
        //1. 가중치 그래프 생성
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList<Edge> edges = new ArrayList<>();

        // 모든 간선 정보를 입력받기
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            edges.add(new Edge(a,b,c));
        }

        //2. 모든 간선에 대한 부모 테이블 초기화
        parents = new int[n+1];
        for(int i=1; i<=n; i++){
            parents[i] = i;
        }

        //3. 모든 간선에 대한 확인
        boolean isCycle = false;
        for(Edge e : edges){
            //사이클이 발생x
            //=2개의 원소의 루트 노드가 서로 다른 것
            if(findParent(e.s) != findParent(e.e)){
                unionParent(e.s, e.e);
            }
            //사이클 발생o
            //=2개의 원소의 루트 노드가 서로 같은 것
            else{
                isCycle = true;
                break;
            }
        }

    }

    public static int findParent(int x){
        if(x == parents[x]) return x;
        else return parents[x] = findParent(parents[x]);
    }

    public static void unionParent(int a, int b){
        int a_ = findParent(a);
        int b_ = findParent(b);

        if(a_ < b_) parents[b_] = a_;
        else parents[a_] = b_;
    }

    static class Edge{
        int s;
        int e;
        int w;

        public Edge(int s, int e, int w){
            this.s=s;
            this.e = e;
            this.w = w;
        }
    }
}

 

 

 

최소 신장 트리 - 크루스칼 알고리즘

• 신장 트리 정의: 모든 노드를 포함하면서, 사이클이 존재 하지 않는 부분 그래프

• 최소 신장 트리 정의: 최소한의 비용 구성되는 신장 트리를 찾는 방법
  • 그리디 알고리즘으로 분류
• 시간복잡도: O(ElogE) - 간선의 개수(E)
• 동작 과정
  1. 간선 데이터를 비용에 따라 오름차순으로 정렬
  2. 모든 간선을 하나씩 확인하여, 현재 간선이 사이클을 발생시키는지 확인
     • 사이클이 발생하지 않는 경우: 최소 신장 트리에 포함
     • 사이클이 발생하는 경우: 패스

 

진행 흐름

기본적으로 부모 테이블, findParent(), unionParent는 위와 동일

 

1. 가중치 그래프 생성 - 간선 관점

//1. 가중치 그래프 생성
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int m = sc.nextInt();

ArrayList<Edge> edges = new ArrayList<>();

// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();

    edges.add(new Edge(a,b,c));
}


static class Edge{
    int s;
    int e;
    int w;

    public Edge(int s, int e, int w){
        this.s=s;
        this.e = e;
        this.w = w;
    }
}

 

 

2. 간선 데이터 정렬

• 최소 비용 간선부터 확인하기 위해 정렬 진행 ( 그리디 )

//2. 간선 데이터 정렬 - 가중치가 적은게 우선(오름차순)
Collections.sort(edges, (e1, e2) -> e1.w - e2.w);

 

3. 모든 간선에 대해서 반복 진행

• 현재 간선이 사이클을 발생시키지 않는다면 ( = 루트 노드가 같지 않다면) 

//3. 모든 간선에 대한 부모 테이블 초기화
parents = new int[n+1];
for(int i=1; i<=n; i++){
    parents[i] = i;
}

 

 

4. 모든 간선에 대해서 반복 진행

• 현재 간선이 사이클을 발생시키지 않는다면 ( = 루트 노드가 같지 않다면) 
• 신장트리에 포함 ( = union 연산 진행 )

//4. 모든 간선을 반복하여 사이클x 경우만 최소 신장 트리에 포함
int weight_sum = 0;
for(Edge e : edges){
    //사이클이 발생하지 않는다면
    // = 두 노드가 같은 집합에 속하지 않는다면
    // = 두 노드의 루트 노드가 동일하지 않다면
    if(findParent(e.s) != findParent(e.e)){
        weight_sum += e.w;
        unionParent(e.s, e.e);
    }
}

System.out.println(weight_sum);

 

 

 

 

 

 

 

 

 

 

 

전체 코드

public class struct {
    static int[] parents;
    
    public static void main(String[] args) throws IOException {
        //1. 가중치 그래프 생성
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList<Edge> edges = new ArrayList<>();

        // 모든 간선 정보를 입력받기
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            edges.add(new Edge(a,b,c));
        }

        //2. 간선 데이터 정렬 - 가중치가 적은게 우선(오름차순)
        Collections.sort(edges, (e1, e2) -> e1.w - e2.w);

        //3. 모든 간선에 대한 부모 테이블 초기화
        parents = new int[n+1];
        for(int i=1; i<=n; i++){
            parents[i] = i;
        }

        //4. 모든 간선을 반복하여 사이클x 경우만 최소 신장 트리에 포함
        int weight_sum = 0;
        for(Edge e : edges){
            //사이클이 발생하지 않는다면
            // = 두 노드가 같은 집합에 속하지 않는다면
            // = 두 노드의 루트 노드가 동일하지 않다면
            if(findParent(e.s) != findParent(e.e)){
                weight_sum += e.w;
                unionParent(e.s, e.e);
            }
        }

        System.out.println(weight_sum);
    }

    public static int findParent(int x){
        if(x == parents[x]) return x;
        else return parents[x] = findParent(parents[x]);
    }

    public static void unionParent(int a, int b){
        int a_ = findParent(a);
        int b_ = findParent(b);

        if(a_ < b_) parents[b_] = a_;
        else parents[a_] = b_;
    }

    static class Edge{
        int s;
        int e;
        int w;

        public Edge(int s, int e, int w){
            this.s=s;
            this.e = e;
            this.w = w;
        }
    }
}