크루스칼,union find

정리 정리 시즌... 다시 다시 하는 시즌..자주 나오진 않는 거 같지만, 꼭 까먹었을 때 나오길래..ㅎㅎ

Union find ( 유니온 파인드 )

합 집합 찾기 == 서로소 찾기

• 여러개의 노드가 존재할 때, 두 개의 노드를 선택해, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 이다.

내부 동작

• 각 노드의 parent 를 기록 한다 -> 두 노드가 공통적인 parent 를 갖고 있다면, 이 두 노드는 같은 그래프에 속한다고 할 수 있다.

부모 노드를 업데이트 해 간다.

• a, b 노드가 속해 있는 두 서브 그래프를 합치면서, a, b 의 부모 노드를 업데이트한다
  ex) 더 작은 숫자의 노드가 항상 부모노드라고 한다면

  int unionParent(int parent[], int a, int b ) {
  	a = getParent(parent, a);
      b = getParent(parent, b);
      if ( a < b) parent[b] = a;
      else parent[a] = b;
   }

구현

• 각 노드의 부모노드를 기록하는 테이블을 둔다 -> parent
  - 여기에는, 각 노드의 부모노드로서 "자기 자신" 을 세팅한다.
• 같은 부모를 확인하기 위해서는

int findParent(int parent[], int a, int b) {
	if(getParent(a) == getParent(b)) return 1;
    return 0;
}

int getParent(int parent[], int x ) {
	if(parent[x] == x) return x;	// 현재노드가 이 그래프의 루트노드인 경우 바로 리턴한다
    return getParent(parent, parent[x]); // 재귀호출을 통해, 현재 이 노드가 속한 그래프 상에서 가장 상위 노드를 리턴한다
}

효율 높이기

위에서 재귀함수 부분에서 효율을 높일 수 있음. ㅎㅅㅎ.
지금은, a-b-c-d-e 까지 depth 가 있는 그래프에서 b 에서부터 시작해서 한 번 getParent() 를 호출했더라도, c 에서 또 찾으면 또 그 탐색 과정을 하나하나 거쳐야함.

• 이제는 이거를 캐싱해놓고, c에서 또 이 메소드 호출하면 이번엔 하나 하나 다시 탐색 하지 않고, 캐싱해놓은 값을 불러올 거임.
• 즉, 어떤 노드가 속해 있는 그래프 상의 가장 root node 를 찾는 연산에서 효율을 높이는 것이다.

int getParent(int parent[], int x ) {
	if(parent[x] == x ) return x; 
    return parent[x] = getParent(parent[x]);
}

하나를 업데이트 해 가는 과정에서, 루트 노드를 세팅하였기 때문에, 다음번 getParent 호출은 바로 If 에서 리턴되어온다.

크루스칼 알고리즘

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다

• 탐욕법을 사용한다 -> "비용"을 기준으로 모든 간선들을 오름차순으로 정렬한다 -> 가장 작은 비용의 간선을 먼저 선택하여 1. 이 간선을 추가할 경우, 사이클이 생기는가? 를 확인한다. 그렇지 않을 경우 해당 간선을 추가한다.
• 위의 "1"을 확인하기 위해서는 유니온 파인드를 활용할 수 있다. cycle 이 생긴다는 것은,이미 두 노드가 같은 그래프에 속해있다는 것을 의미하기 때문이다.
  - 우리는, 두 노드가 같은 그래프에 속해 있지 않음을 확인해야만 한다 .따라서 이 때 유니온 파인드를 활용할 수 있다.