[Graph] 크루스칼 알고리즘 (Kruskal's algorithm)

최소 스패닝 트리(MST)를 만들기 위한 방법 중 하나. (+ 프림알고리즘)

 

1. 모든 간선들의 가중치를 오름차순으로 정렬한다.

2. 가중치가 가장 작은 간선을 선택한다.

3. 선택한 간선이 연결하려는 2개의 노드가 아직 서로 연결되지 않은 상태라면

    2개의 노드를 서로 연결한다.

4. 반복.

 

=> 최소가중치를 가진 간선들을 사이클이 발생하지 않게 계속 연결하여 MST를 찾는다.

 

 

 

시간 복잡도 : O(mlog n)

 

구현

가장 작은 가중치를 갖는 간선이 연결하고자 하는 두 노드가 연결되어있는지 확인해주는 과정에서 많이 사용하는 방식이 Union-Find이다. 이전에 Union_Find를 다룬 적이 있는데 이를 이렇게 적용할 줄이야 하하핳.

 

parent[]

• 코드 구현시에 대중적으로 많이 사용하는 방법은 parent[]라는 1차원 배열을 사용한다.
• 이 배열은 부모가 같은지를 판단해주는 배열이다. == 속해있는 집합이 같은지 확인한다. 
  • == 서로 다른 두 노드가 같은 부모를 가지고 있다면 서로 연결되어 있음을
  • 서로 다른 부모를 가지고 있다면 연결되어 있지 않음을 뜻한다.
• 처음 시작때는 모든 노드가 서로 연결되어있지 않은 상태이므로 parent 배열의 초기값은 자기 자신이 된다.
  • ex) 노드1,2,3,4,5 => Parent[1] = 1, Parent[2] = 2 ... Parent[5] = 5

 

find

앞서 설명한 parent[] 배열에서 부모가 같다면 연결되어 있음을, 부모가 같지 않다면 연결되어있지 않음을 알 수 있다고 하였다.

크루스칼 알고리즘을 사용하여 MST를 구할 때 find를 사용하여 vertex들의 연결 여부를 확인한다.

 

 

1. 서로 같은 부모를 갖는지 판단해주는 함수

2. 부모를 찾는 find 함수

3. 서로 다른 부모일 경우 두 vertex를 연결하는 union함수.

 

 

# 서로 같은 부모를 갖는지 판단해주는 함수

bool SameParent(int x, int y)
{
    x = Find_Parent(x);     
	y = Find_Parent(y);       

	if(x == y) return true;    
	else return false;        
}

 

# find 함수

int Find_Parent(int x)
{
	if (Parent[x] == x) return x;
	else return Parent[x] = Find_Parent(Parent[x]);

}

 

#union함수

void Union(int x, int y)   

{
	x = Find_Parent(x);    
	y = Find_Parent(y);    
	if (x != y)           
	{
		Parent[y] = x;   
	}                    
}

 

참고 URL : https://yabmoons.tistory.com/186