최소 비용 신장 트리(Minimum Cost Spanning Tree)

신장 트리

• Spanning Tree
• 연결되어 있다(Connected)
• 최소 에지 수 = |E| = |V| - 1
  • 트리의 조건
  • E와 V가 같으면 사이클을 돌게 되므로 |V| - 1이다.

최소 비용 신장 트리

• MST(Minimum Cost Spanning Tree)
• 무방향 그래프
• 가중치 그래프
• 비용이 최소가 된다.
  • 에지들의 비용이 가장 작은 트리를 구한다.
  • 에지 비용이 같은게 존재할 수 있으므로 유일하지 않는 특성도 있다.
• 탐욕 알고리즘(Greedy Algorithm) 기반
  • Kruskal Algorithm
  • Prim Algorithm

탐욕 알고리즘(Greedy Algorithm)

• 전역적 최적해를 찾기 위해 각 단계에서 지역적 최적해를 선택하는 알고리즘

출처 : https://github.com/ythwork/CS

• 위 그림의 경우
  • 탐욕 알고리즘에 의한 경로 = 4 + 30 + 5 = 39
  • 실제 최적 경로 = 4 + 8 + 80 = 92
• 위와 같이 지역적 최적 선택의 모임이 전역적으로 최적해라는 보장이 없다.
• 그래서 다음과 같이 탐욕 알고리즘이 성공하기 위한 조건이 있다.
  • Greedy choice property : 지역 최적해를 선택해 나가면 전역 최적해에 도달할 수 있다.
  • Optimal substructure : 문제에 대한 최적해가 부분 문제에 대한 최적해를 포함한다.

Greedy MST Algorithm 단순화

• 에지 가중치는 서로 다르다고 가정한다.
• 그래프는 연결되어 있다고 가정한다.
• 따라서 최소 비용 신장 트리가 존재하며 유일하다고 가정할 수 있다.

컷(Cut)

출처 : https://github.com/ythwork/CS

• V(G) 집합을 공집합이 아닌 두 집합으로 나눈 것
• Crossing edge : 컷으로 나뉜 한 집합의 정점과 다른 집합의 정점을 연결
• Cut property : Crossing edge 중 가장 작은 에지로, MST의 한 에지가 된다.
• Kruskal과 Prim 모두 Cut property 기반으로 만들어졌으며, 다른 점은 어떻게 자를 것인가의 차이이다.

알고리즘 과정

1. 시작점에서 인접한 정점을 주변으로 컷을 찾는다.

   
   출처 : https://github.com/ythwork/CS
   
   

2. crossing edge 중에서 가중치가 가장 작은 에지인 2를 선택한다.

   
   출처 : https://github.com/ythwork/CS
   
   

3. 선택된 crossing edge를 포함하지 않는 컷을 찾는다.

   
   출처 : https://github.com/ythwork/CS
   
   

4. crossing edge 중에서 가중치가 가장 작은 에지인 7을 선택한다.

   
   출처 : https://github.com/ythwork/CS
   
   

5. 선택된 crossing edge를 포함하지 않는 컷을 찾는다.

   
   출처 : https://github.com/ythwork/CS
   
   

6. crossing edge 중에서 가중치가 가장 작은 에지인 5를 선택한다.

   
   출처 : https://github.com/ythwork/CS
   
   

7. 선택된 crossing edge를 포함하지 않는 컷을 찾는다.

   
   출처 : https://github.com/ythwork/CS
   
   

8. crossing edge 중에서 가중치가 가장 작은 에지인 4를 선택한다.

   출처 : https://github.com/ythwork/CS

출처 : https://github.com/ythwork/CS

• MST의 핵심은 에지(E)
• 생각해야 할 점
  • 어떻게 컷을 선택할 것인가?
  • 어떻게 가중치가 가장 작은 에지를 찾을 것인가?

분리 집합(disjoint set)

출처 : https://github.com/ythwork/CS

i	0	1	2	3	4
parent	-1	2	-1	0	2

• 위 그림을 표로 정리
• root node라면 parent는 -1로 표현한다.
• {1, 2, 4}와 {0, 3}

1. FIND(i)

• 정점 i가 포함된 트리의 루트를 찾아 반환한다.
• FIND(1) = 2

2. UNION(i, j)

출처 : https://github.com/ythwork/CS

i	0	1	2	3	4
parent	-1	2	0	0	2

• i, j는 모두 root이다.
• parent[i] = j
• parent[2] = -1에서 0으로 바뀐다.

성능 향상

출처 : https://github.com/ythwork/CS

i	0	1	2	3	4
parent	-2	2	-3	0	2

• root node의 parent 값을 -1 아닌 정점의 수를 가진 음수로 바꾼다.
• parent[i] < 0이면 root node의 abs(parent[i]) = size[i]
• parent[i] >= 0이면 parent[i]는 정점 i의 부모
• 위에서는 parent[0]은 -1에서 -2로, parent[2]는 -1에서 -3이 된다.

1. collapsing-find

출처 : https://github.com/ythwork/CS

• 루트의 높이를 낮춰서 성능을 높인다.

2. weighted-union

출처 : https://github.com/ythwork/CS

i	0	1	2	3	4
parent	2	2	-5	0	2

• weighted-union(i, j)
• i, j는 모두 root이다.
• i, j 중에서 size가 큰 root가 parent가 된다.
• parent[0]은 -1에서 2로, parent[2]는 -1에서 -5가 된다.

Kruskal Algorithm

• 에지를 가중치가 작은 것에서 큰 것으로 정렬한다.
• 트리에 에지를 하나씩 추가한다.
• 사이클이 생기면 추가하지 않는다.
• 최소 비용 신장 트리가 완성되면 종료(|E| = |V| - 1)

Prim Algorithm

• 정점 하나를 가진 트리에서 시작한다.
• 트리 내에 있는 정점 u와 트리 밖의 정점 v를 잇는 에지 중 최소 비용을 가진 (u, v)를 트리 에지로 만든다.
• 트리 밖의 정점 v도 트리의 정점으로 만든다.
• 트리 정점이 기존 정점의 수와 같아지면 종료(TV = V(G))
• 트리 내의 정점 u와 트리 밖의 정점 v를 잇는 에지를 선택하기 때문에 사이클이 형성되지 않는다.

MST Example

출처 : https://github.com/ythwork/CS

# Union Find Algorithm

class DisjointSet:
    def __init__(self, vnum):
        self.parent = [-1 for _ in range(vnum)]

    def simple_find(self, i):
        # i가 속한 트리의 루트를 반환
        while self.parent[i] >= 0:
            i = self.parent[i]
        return i

    def simple_union(self, i, j):
        # i, j must be ROOTS
        self.parent[i] = j

    # 성능 향상
    # 노드의 개수대로 root의 음수 값을 변경(노드가 3개라면 -3)
    def collapsing_find(self, i):
        root = i
        while self.parent[root] >= 0:
            root = self.parent[root]
            
        trail = i

        while trail != root:
            lead = self.parent[trail]
            self.parent[trail] = root
            trail = lead

        return root

    def weighted_union(self, i, j):
        # i, j must be ROOTS
        temp = self.parent[i] + self.parent[j]
        if self.parent[i] > self.parent[j]:
            self.parent[i] = j
            self.parent[j] = temp
        else:
            self.parent[j] = i
            self.parent[i] = temp

# test code
if __name__=="__main__":
    ds=DisjointSet(5)
    ds.parent[2]=-5
    ds.parent[4]=2
    ds.parent[0]=4
    ds.parent[1]=0
    ds.parent[3]=1
    print(ds.parent)
    print("the root is {}".format(ds.collapsing_find(3)))
    print(ds.parent)

import math
from disjoint_set import DisjointSet

# Graph representation : adjacency list
"""
MST
1. 무방향
2. 가중치
3. 인접 리스트
"""

class GNode:
    def __init__(self, vertex, weight):
        self.vertex = vertex
        self.weight = weight
        self.link = None

class Edge:
    # ex) (2,3): 7 -> (u,v): w
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

# 그래프는 객체와 객체 사이의 "관계"
# 새로운 노드(정점)을 추가하는 경우가 거의 없다!
class Graph:
    def __init__(self, vnum):
        self.adjacency_list = [None for _ in range(vnum)]
        self.edge_list = []
        self.vertex_num = vnum

    def __add_node(self, n, nNode):
        cur = self.adjacency_list[n]
        if not cur:
            self.adjacency_list[n] = nNode
            return
        
        while cur.link:
            cur = cur.link

        cur.link = nNode

    def insert_edge(self, u, v, w):
        unode = GNode(u, w)
        vnode = GNode(v, w)

        self.__add_node(u, vnode)
        self.__add_node(v, unode)
        self.edge_list.append(Edge(u, v, w))

    # kruskal
    def MST_kruskal(self):
        mst = Graph(self.vertex_num)
        ds = DisjointSet(self.vertex_num)
        self.edge_list.sort(key=lambda e: e.w)

        mst_edge_num = 0
        edge_idx = 0
        while mst_edge_num < self.vertex_num - 1:
            edge = self.edge_list[edge_idx]
            # 사이클이 있는지 체크
            # 사이클이 없다면 이 에지를 선택한다.
            if ds.collapsing_find(edge.u) != ds.collapsing_find(edge.v):
                # 에지를 선택
                mst.insert_edge(edge.u, edge.v, edge.w)
                ds.weighted_union(ds.collapsing_find(edge.u), ds.collapsing_find(edge.v))
                mst_edge_num += 1

            edge_idx += 1
            
        return mst

    def get_min_v(self, w):
        _min = math.inf
        min_v = None
        for i in range(len(w)):
            if _min > w[i]:
                _min = w[i]
                min_v = i

        return min_v

    # prim
    def MST_prim(self):
        mst = Graph(self.vertex_num)
        TV = set()
        w = [math.inf for _ in range(self.vertex_num)]
        _from = [None for _ in range(self.vertex_num)]
        w[0] = 0

        while len(TV) < self.vertex_num:
            v = self.get_min_v(w)
            # TV = TV U {v}
            # TE = TE U {(v, from[v])}
            # each u in adj[v]
            TV.add(v)
            if _from[v] != None:
                mst.insert_edge(v, _from[v], w[v])
            
            w[v] = math.inf
            # adj[v]
            u = self.adjacency_list[v]

            while u:
                if u.vertex  not in TV and u.weight < w[u.vertex]:
                    w[u.vertex] = u.weight
                    _from[u.vertex] = v

                u = u.link

        return mst

    # 테스트를 위한 함수 코드
    def print_edges(self):
        for edge in self.edge_list:
            print(f"({edge.u}, {edge.v}) : {edge.w}")

# test code
if __name__=="__main__":
    g=Graph(6)

    g.insert_edge(0, 1, 10)
    g.insert_edge(0, 2, 2)
    g.insert_edge(0, 3, 8)
    g.insert_edge(1, 2, 5)
    g.insert_edge(1, 4, 12)
    g.insert_edge(2, 3, 7)
    g.insert_edge(2, 4, 17)
    g.insert_edge(3, 4, 4)
    g.insert_edge(3, 5, 14)

    print("kruskal : ")
    mst=g.MST_kruskal()
    mst.print_edges()

    print()

    print("prim : ")
    mst=g.MST_prim()
    mst.print_edges()