최소 신장 트리 (Kruskal MST)

최소 신장 트리 (Minimum Spanning Tree)

주어진 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 간선들의 가중치 합이 최소인 트리

• 크러스컬(Kruskal) 알고리즘
• 프림(Prim) 알고리즘

Kruskal MST

가중치(거리)의 오름차순으로 간선들을 정렬하여 정렬된 간선들을 리스트에 저장

트리 선언 및 초기화(null로)

트리의 간선 수가 n-1이 될 때까지 아래의 반복문 수행

정렬된 간선들을 저장한 리스트에서 가장 작은 가중치를 가진 간선 선택 및 리스트에서 제거

만약 선택한 간선이 트리에 추가되어 사이클을 만들지 않으면 트리에 선택한 간선 추가

사이클을 만들면 선택한 간선 그냥 버리기

최종적으로 트리를 리턴

선택한 간선이 사이클을 만드는지 확인하는 방법

연결하려는 두 점이 어느 트리에 속하는지 확인

만약 A와 B의 간선을 추가하고 싶을 경우 A점이 속한 트리와 B점이 속한 트리가 다를 경우 간선 추가 가능

A와 B점이 속한 트리가 같을 경우 간선을 추가하면 사이클이 생김

∴ 각 트리의 대표 원소를 지정하고 선택한 각 점의 대표 원소를 서로 비교해 다르면 트리에 간선을 추가할 것

 

참고) 알기 쉬운 알고리즘

 

# Kruskal Minimum Spanning Tree

class DisjointSetSimple:
    def __init__(self, n):	# 최상위 부모(대표원소) 초기화
        self.parent = list(range(n))

    def find(self, id):     # 제일 위의 parent를 출력하는 함수
        while self.parent[id] != id:
            id = self.parent[id]
        return id

    def union(self, s1, s2):    # s1의 제일 위의 부모를 s2로 지정
        self.parent[self.find(s1)] = self.find(s2)


def MSTKruskal(V, adj):
    vsize = len(V)
    dsets = DisjointSetSimple(vsize)
    E = []      # 가중치의 오름차순으로 정렬된 간선들을 담을 것 [(점1, 점2, 가중치), (...), ...]

    # 시작점과 끝점 그리고 그 사이의 거리
    # 데이터를 (A,B,16) 이런식으로 정렬하는 것
    for i in range(vsize - 1):
        for j in range(i + 1, vsize):
            if adj[i][j] != None:
                E.append((i, j, adj[i][j])) # 튜플로 데이터 삽입
                

    # 거리(가중치; weight)를 오름차순으로 정렬
    # E의 하나의 요소를 e라고 하고 두번째 요소(인덱스)(weight)를 기준으로 정렬하겠다는 의미
    E.sort(key=lambda e: e[2])
    print(E)    # weight가 낮은 순부터 정렬되어 출력
    
    for i in range(len(E)):
        e = E[i]
        # uset과 vset이 같은 값이면 같은 트리에 속한다는 뜻(최상위 부모(대표원소)가 같다는 의미이므로)
        uset = dsets.find(e[0])
        vset = dsets.find(e[1])

        # 출발지점과 끝지점의 최상위 부모가 같은지 확인
        if uset != vset:
            # 다르면 간선을 추가(즉 set으로 묶음)
            dsets.union(uset, vset)
            print(f"Edge added: ({V[e[0]]}, {V[e[1]]}, {e[2]})")
            

    
# 실행
vertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
weight = [  [None,   29, None, None, None,   10, None],   # A
            [  29, None,   16, None, None, None,   15],   # B
            [None,   16, None,   12, None, None, None],   # C
            [None, None,   12, None,   22, None,   18],   # D
            [None, None, None,   22, None,   27,   25],   # E
            [  10, None, None, None,   27, None, None],   # F
            [None,   15, None,   18,   25, None, None]    # G
          ]


print("MST By Kruskal's Algorithm")
MSTKruskal(vertex, weight)

 

실행 결과