크루스컬(Kruskal) 알고리즘, 최소 신장 트리(MST), python

 

크루스컬 알고리즘 이란?

 

최소 신장 트리(Minimun Spanning Tree)란 사이클이 생기지 않게 모든 정점을 연결하면서, 간선의 가중치의 총합이 최소가 되는 트리를 말한다.

 

 

 

크루스컬 알고리즘은 최소 신장 트리를 구하는 알고리즘이다.

간선들을 가중치가 작은 것부터 오름차순으로 정렬한 뒤, 간선을 하나씩 선택한다.

선택한 간선의 양 끝 두 정점이 같은 집합에 속하지 않았다면 그 간선을 트리에 포함시킨다. 만약 같은 집합에 속한다면 사이클이 생기기 때문에 포함시키지 않는다.

이과정을 모든 정점들이 하나의 집합이 될 때까지 반복하면 된다.

최소 신장 트리에서 간선의 개수는 정점의 개수 -1 개 이므로 선택된 간선의 개수가 정점의 개수 - 1 개가 되면 종료한다.

 

 

 

 

 

크루스컬 알고리즘을 사용해 최소 신장 트리를 구하는 과정

 

가중치가 다음과 같은 그래프가 있다.

 

A	B	가중치
0	1	2
0	2	3
1	2	4
1	3	5
2	3	1
3	4	6

 

 

 

 

 

 

먼저 간선들을 가중치가 작은 것부터 오름차순으로 정렬한다.

A	B	가중치
2	3	1
0	1	2
0	2	3
1	2	4
1	3	5
3	4	6

 

 

 

 

 

 

 

가중치가 가장 작은 간선부터 선택한다.

A	B	가중치
2	3	1
0	1	2
0	2	3
1	2	4
1	3	5
3	4	6

 

가중치가 가장 작은 간선은 가중치가 1이고 양끝을 2번과 3번으로 하는 간선이다.

여기서 2번과 3번이 같은 집합에 있는지 확인하고, 같은 집합이 아니라면 두 정점을 하나의 집합으로 합치고 트리에 포함시킨다.

여기서 같은 집합인지 확인하고 같은 집합으로 합치는 것은 유니온 파인드로 구현할 수 있다.

 

 

 

유니온 파인드 알고리즘, python

유니온 파인드 알고리즘, python

 

 

 

 

 

A	B	가중치
2	3	1
0	1	2
0	2	3
1	2	4
1	3	5
3	4	6

 

가중치가 2인 간선을 선택한다. 양끝 정점은 0과 1이고 서로 다른 집합이다. 두 집합을 합쳐주고 간선을 트리에 포함시킨다.

 

 

 

 

 

 

A	B	가중치
2	3	1
0	1	2
0	2	3
1	2	4
1	3	5
3	4	6

 

가중치가 3인 간선을 선택한다. 양 끝 정점은 0과 2이다. 서로 다른 집합이므로 합쳐주고 간선을 트리에 포함시킨다.

 

 

 

 

 

 

 

A	B	가중치
2	3	1
0	1	2
0	2	3
1	2	4
1	3	5
3	4	6

 

가중치가 4인 간선을 선택한다. 양 끝은 1번과 2번이고 같은 집합에 속해있다. 따라서 사이클이 생기므로 트리에 포함시키지 않는다.

 

 

 

 

 

 

 

 

A	B	가중치
2	3	1
0	1	2
0	2	3
1	2	4
1	3	5
3	4	6

 

가중치가 5인 간선도 마찬가지로 양 끝 정점 1번과 3번이 같은 집합에 속해있다. 트리에 포함시키지 않는다.

 

 

 

 

 

 

 

 

A	B	가중치
2	3	1
0	1	2
0	2	3
1	2	4
1	3	5
3	4	6

 

가중치가 6인간선의 양 끝 정점은 3번과 4번이고 서로 다른 집합이므로 합쳐주고 간선을 트리에 포함시킨다.

 

 

이제 모든 정점들이 하나의 집합으로 합쳐졌으므로 종료한다.

정점의 개수가 V개라면 간선의 개수는 V-1개가 된다.

 

 

 

 

 

python 구현

 

크루스컬 알고리즘을 구현하기 위해서는 간선의 정렬이 먼저 되어야 한다.

정점의 개수는 V개이고 간선의 개수는 E개다.

# a,b,w 순으로 입력받는다
edges = [list(map(int, input().split())) for _ in range(E)]

# 간선을 가중치가 작은 순으로 정렬
edges.sort(key=lambda x:x[2])

 

간선을 입력받아 가중치를 기준으로 오름차순 정렬을 한다.

 

 

 

parents = [x for x in range(V)]
level = [0] * V

# 경로 압축
def find(x):
    if parents[x] != x:
        parents[x] = find(parents[x])
    return root[x]

# union
def union(x,y):
    # 각각의 루트노드를 찾는다
    x = find(x)
    y = find(y)

    # x를 루트노드로 한 트리의 깊이가 깊으면 x트리 밑에 y트리를 붙여준다.
    # y의 루트노드를 x로 바꿔준다.
    if level[x]>level[y]:
        parents[y] = x

    # y를 루트노드로 한 트리의 깊이가 깊으면 y트리 밑에 x트리를 붙여준다.
    # x의 루트노드를 y로 바꿔준다.    
    elif level[x]<level[y]:
        parents[x] = y

    # 두 트리의 높이가 같다면 x 트리의높이를 1늘려주고 x트리 밑에 y트리를 붙인다.
    else:
        level[x] += 1
        parents[y] = x

 

간선의 양 끝 두 정점이 같은 집합인지 확인하고, 다르다면 하나의 집합으로 합치기 위한 유니온 파인드를 구현한다.

 

 

 

# 최소 신장 트리 간선을 저장
mst_edges = []

for a,b,w in edges:
    # 간선의 개수가 V-1개 라면 종료
    if len(mst_edges) == V-1:
        break

    # 만약 두 정점이 같은 집합이 아니라면
    if find(a) != find(b):
    	# 간선을 트리에 포함시킨다
        mst_edges.append((a,b,w))
        # 하나의 집합으로 합쳐준다
        union(a,b)

 

간선의 가중치가 작은 것부터 선택하면서 해당 간선의 양 끝점이 다른 집합이라면 해당간선을 트리에 포함시킨다.

간선의 개수가 V-1개가 되면 종료시킨다.