신장트리 최소비용 탐색

신장트리(spanning tree)

모든 정점을 포함하면서

사이클이 없는 트리 (트리의 조건)

 

 

 

오른쪽 두개가 신장트리

목표

• 그리디(Prim, Kruskal) 알고리즘으로 mst(최소비용신장트리) 찾아보자
• 알고리즘의 최적의 여부를 검증해보자

 

 

그리디 알고리즘

• 결정 순간마다 가장 좋다고 생각되는 것을 해답으로 선택
• 선택은 그 당시(local)에는 최적이나 최종적인 선택(global)은 최적이라는 보장 없음, 검증 필수

 

 

---

Prim의 알고리즘

개념

 

 

집합에 속한 정점 중에서 가장 가까운 정점을 반복에서 추가하는 방법

처음 노드를 v1으로 선택했다고 하자 (랜덤으로 해도 상관없음)

 

순서	안보임	경계	결과집합
1	V4,V5	V2,V3	V1
2	V5	V3,V4	V1,V2
3	null	V4,V5	V1,V2,V3
4	null	V4	V1,V2,V3,V5
5	null	null	V1,V2,V3,V5,V4

결과 집합과 인접한 노드중에서 가장 가중치가 적은 노드를 추가한다.

 

알고리즘

 

먼저 각 정점의 가중치를 담은 행렬식 W를 정의한다.

 

이를 개념대로 구현하면

 

inf = 1000
w = [[0,1,3,inf,inf],
    [1,0,3,6,inf],
     [3,3,0,4,2],
     [inf,6,4,0,5],
     [inf,inf,2,5,0]] 

F=set()
printMatrix(w)
n=len(w)
nearest=n*[0]
distance=n*[0]



#초기화
for i in range(1,n):
    nearest[i]=0
    distance[i]=w[0][i]



for repeat in range(0,n-1):
    min = inf

#검색
    for i in range(1,n):
        if 0<distance[i] and distance[i]<min:
            min = distance[i]
            vnear = i

#추가
    distance[vnear] = 0 
    F.add((vnear, nearest[vnear])) 

#갱신

    for i in range(1,n):
        if w[i][vnear] < distance[i]:  
            distance[i] = w[i][vnear]  
            nearest[i]=vnear

          
print()
print(F)

---

Kruskal의알고리즘

 

개념

1. 최소가중치를 갖고 있는 다음 이음선을 선정
2. 이 이음선이 두 개의 서로소인 정점을 잇는다면 추가한다
3. 모든 부분집합이 하나의 집합으로 합쳐지면 최소비용신장트리가 된다

 

 

 

 

 

구현

 

 

 

parent = dict()
rank = dict()

#서로소 집합 추상 간단 구현
def make_singleton_set(v):
    parent[v] = v
    rank[v] = 1

def find(v):
    if parent[v] != v:
        parent[v] = find(parent[v])
    return parent[v]


def union(r1, r2):


    if r1 != r2:  #짧은 트리가 긴 트리에 합쳐진다
        if rank[r1] > rank[r2]:
            parent[r2] = r1
            rank[r1] += rank[r2]
        else:
            parent[r1] = r2
            if rank[r1] == rank[r2]:
                rank[r2] += rank[r1]

# kruskal 구현
def kruskal(graph):

    for v in graph['vertices']:
        make_singleton_set(v)

    mst = []
    
    lst = sorted(graph['edges'])
    #부모가 겹치지 않으면 서로소
    for t in lst:
        p = find(t[1])
        q = find(t[2])
        if p != q:
            union(p,q)
            mst.append(t)
            print(mst)
    return mst
    




graph = {
        'vertices': ['A', 'B', 'C', 'D', 'E'],
        'edges': set([
            (1, 'A', 'B'),
            (3, 'A', 'C'),
            (3, 'B', 'C'),
            (6, 'B', 'D'),
            (4, 'C', 'D'),
            (2, 'C', 'E'),
            (5, 'D', 'E'),
            ])
        }



        
mst=kruskal(graph)
print(mst)