Union-find algorithm for graph

1. Problem

- 여러 개의 노드 중 2개를 선택했을 때, 두 노드가 같은 그래프에 있는지 알아보자.

- 합집합 찾기(union find) 알고리즘은 i번 노드에 대한 부모 노드의 값을 arr[i]에 저장해서 m번 노드와 n번 노드의 부모가 같다면 같은 그래프에 있다고 판단하는 알고리즘이다.

- 한 그래프의 노드들을 연결할 때 부모 노드가 여러개가 생긴다면 더 작은 값으로 저장한다. 이 과정을 합침(union) 과정이라 한다.

- 합침 과정에서 최종 부모를 찾기 위해 재귀적으로 메서드를 호출하게 된다.

- 찾기(find) 과정에서는 두 노드의 부모를 찾아 같은지 확인한다.

 

2. Input

1) int[][] graph

- 연결된 노드를 표현

2) int a, b

 

3. Output

1) a, b가 같은 그래프에 있는 노드인지 확인

 

4. Example

// 0번부터 11번까지 총 12개의 노드가 있다.			parent
// 부모 노드의 값을 담을 배열 parent[12]를 생성한다.		[0,0,0,0,0,0,0,0,0,0,0,0]
// 각 노드에 대해 자기 값을 초기 부모로 저장한다.			[0,1,2,3,4,5,6,7,8,9,10,11]
// 방문하지 않은 노드를 방문하면서 자기와 연결된 노드를 확인하고 합침 과정을 거친다.
// 0번: 2번과 연결되어 있고, 0 < 2 이므로 parent[2] == parent[0] == 0
// 1번: 2번과 연결되어 있고, 1 > 0 이므로 parent[1] == parent[2] == 0
// 2번: 4번과 연결되어 있고, 0 > 4 이므로 parent[4] == parent[2] == 0
// 3번: 8번과 연결되어 있고, 3 > 8 이므로 parent[8] == parent[3] == 3
// 위와 같은 연산을 수행하면 parent는 다음과 같이 바뀐다.		[0,0,0,3,0,0,3,0,3,3,3,3]
// find()를 이용해 4번과 7번이 같은 그래프에 있는지 확인해보자.
// parent[4] == 0 == parent[7]이므로 true를 반환한다.

 

5. Code

static int[] parent = new int[12]; // 클래스 변수로 선언

// main()
// 위 그래프를 2차원 배열로 표현
// graph[i][j]: i번과 j번을 연결하는 모든 간선들의 정보. 중복이 있을 수 있다.
int[][] graph = {{0,2},{1,2},{2,0},{2,1},{2,4},{2,7},{3,8},{3,9},{4,2},{4,5},
                 {5,4},{6,11},{7,2},{8,3},{9,3},{9,10},{9,11},{10,9},{11,6},{11,9}};

for(int i=0 ; i<12 ; i++) // 각 노드에 대해 자기 값을 초기 부모로 지정한다
    parent[i] = i;

for(int i=0 ; i<graph.length ; i++)  // 그래프의 간선을 따라가며 부모를 합친다.
    union(graph[i][0], graph[i][1]);

// 합치기 과정
static void union(int a, int b) {
    a = getParent(a);      // 두 노드의 부모를 찾은 후
    b = getParent(b);
    if(a<b) parent[b] = a; // 더 작은 수를 부모로 한다.
    else parent[a] = b;
}

// 그래프를 따라가며 부모를 찾는 과정
static int getParent(int a) {
    if(parent[a]!=a)                      // 간선의 정보가 업데이트 될 때
        parent[a] = getParent(parent[a]); // 부모가 달라질 수 있으므로
    return parent[a];                     // 재귀호출을 이용해 최종 부모를 찾는다.
}

// 두 노드가 같은 그래프에 있는지 확인하는 과정
static boolean find(int a, int b) {    // 업데이트가 안됐을 것을 대비하여
    return getParent(a)==getParent(b); // 직접 비교(parent[a]==parent[b]) 대신
}                                      // getParent()를 이용한다.

// main()
System.out.println(find(3,6));       // true, 3과 6의 부모는 3으로 같다.
System.out.println(find(1,9));       // false, 1의 부모는 0, 9의 부모는 3으로 다르다.
union(1,9);                          // 서로 다른 그래프에 존재하는 1과 9를 연결해줬다.
System.out.println(find(1,9));       // true, 1과 9의 부모는 0으로 같다.