Kruskal's Algorithm

• Kruskal's Algorithm
1. 모든 edge를 오름차순 목록을 만든다.
2. 각 vertex는 각각 개별적인 집합이라고 한다.
3. 가장 작은 weight의 edge와 연결된 vertex는 한 집합이 된다.
4. edge마다 vertex를 연결시켜서 집합을 만들어준다.
5. 집합이 만들어질때 edge가 vertex or 집합과 다른 vertex or 집합을 연결해준다면, 둘을 합쳐서 하나의 집합으로 만든다.

• pseudo code

1 2 3 4 5 6 7 8 9 10 11 12

for( 각 vertex){     vertex -> cluster //각각 vertex를 클러스터로 만듬 }   Graph의 모든 edge를 priority queue(Q)에 넣는다. //오름차순 : 1,3,6,7,9,...   while(모든 vertex가 하나의 cloud에 들어갈때까지){     Q에서 가장 작은 edge를 꺼낸다.     if(꺼낸 edge가 cloud안에서 vertex를 연결하는 것이 아니라면){         edge와 연결된 vertex로 클라우드를 merge하거나 생성한다      } }