크루스칼 알고리즘

1. 크루스칼 알고리즘

최소 신장 트리를 구하는 알고리즘 중 하나이다.

  1. 유니온 파인드 연산을 필요로 한다. 

   유니온 파인드 보러가기 >>

  2.트리 그래프  :

순환을 갖지 않는 연결 그래프.  임의의 두 정점에 대해서 경로가 정확히 1개 존재함.

하나 이상의 정점을 가지며 임의의 간선 e를 제거한 그래프는 연결 그래프가 아니다.

(연결 그래프: 모든 정점들을 간선을 통해방문할 수 있는 그래프 : 임의의 v, u 정점에 대해 path(v,u)가 존재하는 그래프)

- 느낌: 그래프를 최소한의 간선으로 모두 연결해서 이동가능 할 수 있게 만든 것이되 사이클이 없는 것.

- 특징: 전체 노드의 개수가 N개일때, 트리를 만들고 나면 전체 간선의 수는 N-1개가 된다. (1개의 경로로만 이루어져 있기 때문에)

 

  3. 알고리즘 개요:

- 간선을 가중치를 기준으로 정렬 한 후, 최소 비용인 간선부터 트리에 넣기 시작한다. (그리디 알고리즘에 속한다.)

     -  간선을 트리에 넣는 행위가 곧 Union연산임: union연산을 했다면(true값 반환)

 - 트리에 넣은 것이므로 비용, 간선의 수를 세는 것에 고려하고, 그렇지 않다면 그냥 지나간다.

  - 이른 종료: 최소 신장 트리의 특징으로, 모든 정점이 단 한개의 간선으로 이루어져 있을 것이므로 그린 간선의 수가 N-1(N은 전체 간선의 수)이라면 이미 최소 신장트리를 완성했다는 뜻으로 더 진행하지 않아도 된다. 

 

 

가장 가중치가 작은 순서대로 1 -> 2 -> 3 순서로 트리를 만든 구조이다. 

운좋게 순서대로 하자마자 바로 최소 신장트리가 완성되었다!

 

pseudo code

vecEdge : 간선 정보를 담은 vector 구조 (start, end, cost 정보를 갖고 있다.)

Alg Kruskal
	1. nowCost = 0, nowEdgecount = 0
    2. init Parent
    3. sort(vecEdge.begin(), vecEdge.end()) {최소 비용 간선부터 그리디로 접근하기 위해 가중치 기준 정렬}
    4. for i <- 0 to vecEdge.size()
    	if(Union(vecEdge[i].start , vecEdge[i].end) == true){간선에 순차적으로 접근: 트리에 담으려고 한다.}
        	nowCost += vecEdge[i].cost				{트리에 담는 게 성공했을 때만 전체 비용과 전체 간선 개수 갱신}
            nowEdgecount <- nowEdgecount + 1
         if(nowEdgecount = N -1) {전체 노드개수 -1개 만큼 간선을 트리에 담았다면 종료}	
         	return

 

3. 크루스칼 알고리즘 정리

1. 간선을 정렬한 다음 for문을 통해 순차적으로 접근한다. 

2. 접근한 간선이 트리에 담겼다면 전체 비용과 전체 간선의 수를 갱신시킨다. 

     트리에 담기지 못했다는 것은 이미 트리에 담겨있다는 의미로, 다시 같은 정점에 접근했다는 것을 의미한다. 

3. 진행중에 트리에 담긴 간선의 수가 N-1 즉 전체 노드 수 -1 개라면, 이른 종료를 해도 좋다. (트리가 다 만들어졌다는 뜻이기 때문)

 

- 시간 복잡도 : O(ElogE) (정렬에 O(ElogE), 트리 만드는 과정 O(E))