그리디 알고리즘 MST(최소비용 신장트리)[Minimum cost spannig tree]

신장트리(spanning tree)란?

- 간선의 개수 E가 노드(V)의 개수 n보다 n-1인 graph를 의미 한다.

circle tree 순환 트리이다

왼쪽 그래프는 V(노드)의 개수가 5개지만

edge(간선)의 개수가 7개 이며 cyclic graph이다

 

 

 

 

출처 : 유투브 주니온TV https://www.youtube.com/watch?v=jQH2wrz04io

  

 

 

 

왼쪽 그래프는 간선의 개수가 3개를 지워

노드의 개수가 5이며 간선의 개수가 4인 

acyclic graph이다

 

 

 

 

출처 : 유투브 주니온TV

 

 

MST(Minimum cost spannig tree)란 가중치가 있는 간선이 있을때 cyclic graph -> acyclic graph로 만들기 위한

간선의 최소 가중치를 찾는 방법이다.

 

최적을 선택하는 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있는데

이번 포스팅에서는 프림알고리즘과 크루스칼 알고리즘으로 작성 되었다.

 

프림 알고리즘의 순서는

1단계 : 초기화 F= 공집함으로 만들고 ( F는 간선과, 가중치를 가진 집합이다), Y는 노드를 가진 부분 집합이다

 

2단계 : 최적의 원소 하나를 해답의 집합(F)의 포함시킨다.

 - Y집합에서 V-Y집합에 포함되어 있는 노드(점)에 가장 가까운 노드(vnear)를 선택 후

 - Y집합의 vnear을 추가 및 F집합에 (노드의 시작점, vnear, 가중치)를 저장해준다.

 

3단계 : 검사를 통해 해답의 집합이 최종이면 종료되고 아니면 2단계를 반복한다.

 - 위에 경우에서 vertex의 개수가 5개이므로 F에 쌓인 간선의 정보가 4개가 될때까지 반복한다.

 

자세한 내용은 https://www.youtube.com/watch?v=jQH2wrz04io 주니온 티비 교수님의 강의를 참고하면 도움이 됩니다.

개인적으로 이부분이 가장 이해하기 힘들었다

위 표는 이 이미지를 매트릭스로 표현한것이다

W 매트릭스는 노드들간에 이어져있는 간선의 가중치를 의미한다.

nearest[i] 리스트는 각 점들과 가장 가까운 점들을 의미하며 바로 아래 있는 distance는 그 점과의 간선의 가중치를 의미한다.

INF는 간선이 이어져 있지 않는것을 의미한다.

< --- 좌측의 이미지는 위에 있는 매트릭스를 의미한다.

1. 첫번째 루프를 돌때 v1(1)과 가장 가까운 점들과의 최소 가중치의 간선을 찾으며

가장 가까운 노드는 v2가 된다. 우측 표는 부분집합 Y를 의미한다. 현재 Y집합에는 v1이 포함되어있다. 이때 distance[index]를 -1로 바꾸어 Y에 포함되어있다고 체크를 해준다.

 

2. 두번째 표는 부분집합 Y의 v1과 v2가 포함되어있을때를 의미한다. 그러므로 현재의 부분집합Y에는 4번 노드와의 간선이 생기며 INF -> 6으로 바꿔준다.

 

 

# 간선이 이어져있지 않는것을 의미한다. 거리가 멈
inf = 999

# 노드들간의 간선 연결 및 가중치의 매트릭스
w = [
    [-1,-1,-1,-1,-1,-1],
    [-1,0,1,3,inf,inf],
    [-1,1,0,3,6,inf],
    [-1,3,3,0,4,2],
    [-1,inf,6,4,0,5],
    [-1,inf,inf,2,5,0]
]

## 프림 알고리즘 시작
def prim(w):

## 리스트가 0부터 시작되기때문에 -1을 해준다.
    n = len(w)-1
    
## F를 공집합으로 만들어줌 초기화해준다.
    F = []
    nearest = [-1] * (n+1)
    distance = [-1] * (n+1)
    
## 부분집합 Y에 v1이 있다고 시작하며 v1과의 연결간선이 있는지를 표시해준다.
    for i in range(2,n+1):
        nearest[i] = 1
        distance[i] = w[1][i]

    for _ in range(n-1):
        minvalue = inf
## v1과 가장 가까운 노드와의 간선을 찾으며 찾았으면 index를 업데이트해준다.
## 루프를 처음 다돌면 가장 가까운 노드는 v2가 되며 거리의 가중치는 1이다
        for i in range(2,n+1):
            if 0<=distance[i]<minvalue:
                minvalue = distance[i]
                vnear = i ## vnear의 2가 저정된다.
## edge(1, 2 #1->2라는 방향을 의미, 1 # 가중치)를 저장후
## 결과 F집합에 포함해준다.
        edge = (nearest[vnear], vnear, w[nearest[vnear]][vnear])
        F.append(edge)
        
## V2는 집합 Y에 포함되었으므로 -1을 통해 더이상 check를 안하게 만든다.
        distance[vnear] = -1
        
## 마지막으로 표를 업데이트 해줌으로써
## 처음에는 v1과 연결된 주변 노드들과 가중치를 표시해 주었지만.
## V2가 들어가게 되면서 v1과 v2와 가까운 노드의 간선의 정보값을 업데이트 해준다.
## 그러므로 distance 리스트에 4번 노드가 v1과는 연결되어있지 않지만 v2와는 연결되어있어 INF -> 6으로 변환된다.
## 또한 nearest 리스트에 v2와 v4과 연결되어 있다고 표시해준다.
        for i in range(2,n+1):
            if distance[i] > w[vnear][i]:
                distance[i] = w[vnear][i]
                nearest[i] = vnear

## 모드 루프문이 돌면 F에는 n-1개의 간선의 정보가 저장되면 집합의 리턴해준다.
    return F


print(prim(w))

 

크루스칼 알고리즘의 순서는

1단계 : 초기화 해답의 집합 F를 공집합으로 둔다(빈 리스트)

 - V의 서로소 집합(disjoint set)을 생성한다

 - E를 가중치를 기준으로 오름차순으로 정렬한다. E = [[노드1,노드2,가중치]] 노드1->노드2로 가는 간선의 가중치를 의미한다.

 

2단계 : 최적의 원소 하나를 해답의 집합에 포함시킨다.

 - E가 가중치를 기준으로 오름차순으로 되어있을때 0번째 인덱스 값은 가장 낮은 가중치의 간선이 위치하게 된다.

 - 그 때 node1 과 node2가 속한 집합 p,q를 찾아서(Find) p,q가 같은면 같은 그래프 이므로 간선 E를 버리고

 다르면 다른 그래프를 의미하므로 해답 리스트 F에 간선 E를 포함하고 p그래프와 q그래프를 합쳐준다(Union)

 

3단계 : F의 리스트의 길이 즉 간선의 개수가 노드의 개수 N일때 N-1이어야 하므로 n-1개가 될때까지 반복해준다.

 

 

 

 

 

 

v2와 v3는 루트 노드가 동일 하므로 하나의 그래프에 둘다 포함되는 노드들이므로

v2 -> v3로 가는 edge는 패스해준다.

 

 

왼쪽 표는 첫번째 노드에서 두번째 노드로 가는 간선을 의미하면 weight 가중치를 의미한다.

 

출처 : 주니온TV 아무거나연구소 https://www.youtube.com/watch?v=80dafLyB_Vk

 

 

 

 

 

 

 

class DisjointSet:
## 처음에 노드의 개수 만큼 U라는 전역변수 리스트를 만든다
## self에는 dset의 주소값이 저장되어있음, 전역 변수는 각자의 객체에게만 공유된다
## 멤버 변수는 다른 객체에도 값이 공유 된다
## self.변수명을 이용하지 않으면 지역변수로 선언되어 다른 메소드가 호출하지 못한다.
    def __init__(self,n):
        self.U = []        
        for i in range(n):
            self.U.append(i)

## p와 q가 다르면 이것은 연결되어 있지 않은 그래프를 의미한다
    def equal(self,p,q):
        if p == q:
            return True
        else:
            return False

## 본인 index리스트에 저장된 값이 자기 자신이면 이것은 사이클 Graph가 아니다
## 본인 index리스트에 저장된 값에 다른값이 들어 있으면 부모 노드로 이동하며 루트노드 까지 이어진다
    def find(self, i):
        j = i
        while self.U[j] != j:
            j = self.U[j]
        return j

## p,q가 다르면 p or q에 값을 방향을 넣어주어 두개의 그래프를 하나의 그래프로 만들어준다.
    def union(self,p,q):
        if p<q:
            self.U[q] = p
        else:
            self.U[p] = q

## E는 오름차순으로 정렬된 리스트여야 하며[노드번호, 노드번호, 가중치]로 만들어진다.
## 가중치를 기준으로 오름차순이어야 한다.
## n은 노드의 개수이다
def kruskal(n,E):
    F = []
    dset = DisjointSet(n)
    while len(F) < n-1:
        edge = E.pop(0)
        i,j = edge[0], edge[1]
        p = dset.find(i)
        q = dset.find(j)
        if not dset.equal(p,q):
            dset.union(p,q)
            F.append(edge)
    return F

matrix=[
        [0,1,1],
        [2,4,2],
        [0,2,3],
        [1,2,3],
        [2,3,4],
        [3,4,5],
        [1,3,6]
    ]
    
print(kruskal(5,matrix))