MST

MST

스패닝 트리 : 그래프의 모든 정점을 포함하는 트리

최소 스패닝 트리 : 가중치의 합이 가장 작은 스패닝 트리

 

Kruscal

<원리>

1. 간선을 가중치 순으로 저장한다.

2. 간선을 순서대로 확인하면서 계속 추가한다. 사이클을 만드는 간선은 추가하지 않는다.

 

<구현>

1. 간선을 가중치 순으로 저장한다.

2. 간선을 순서대로 확인하면서 계속 추가한다.

- 두 정점이 같은 집합 안에 있다면 사이클을 만드는 간선이므로 무시한다

- 두 정점이 다른 집합 안에 있다면  union 연산을 수행하고 mst, mst_weight를 갱신한다.

 

def kruscal(adj): # adj : (weight, from, to) 의 배열
    mst = []
    mst_weight = 0
    
    adj.sort()
    uf = UnionFind(n)
    
    for w, x, y in adj:
        if uf.find(x) == uf.find(y): continue
        uf.union(x, y)
        mst.append((x, y))
        mst_weight += w
    
    return mst, mst_weight

 

시간 복잡도 : $O(|E|\log|E|)\ $ (간선의 정렬)

 

Prim

<원리>

1. MST를 단계적으로 확장한다

2. 현재까지 발견한 MST로부터 거리가 가장 짧은 정점을 추가한다

 

<구현>

1. 세팅

- check : 정점의 방문 여부

- parent : (임시) 부모 노드

- minDist : 현재까지 발견한 MST로부터의 거리

2. 정점을 V번 방문한다.

- 아직 방문하지 않은 정점 중 minDist가 최소인 정점을 x로 선택하고 방문한다.
- x의 부모 노드가 존재한다면(새로운 간선을 추가했다면) mst를 갱신한다.

- mst_weight를 갱신한다.
- x와 아직 방문하지 않은 nx 사이의 weight를 확인한다. 더 짧은 경로(MST - nx)를 발견한다면 nx의 parent, minDist를 갱신한다. 

 

def prim(adj):
    mst = []
    mst_weight = 0

    check = [False]*n # 방문 여부
    parent = [i for i in range(n)] # 부모 노드 저장
    INF = float('inf'); minDist = [INF]*n # MST로부터의 거리

    # 첫 번째 iteration에는 0이 선택 되도록 설정
    minDist[0] = 0
    for i in range(n):
        # MST로부터 거리가 가장 짧은 정점 선택
        x = INF
        for v in range(n):
            if not check[v] and (x == INF or minDist[v] < minDist[x]):
                x = v
        check[x] = True

        # MST 정보 갱신
        if x != parent[x]:
            mst.append((parent[x], x))
        mst_weight += minDist(x)

        # 방문하지 않은 인접 정점에 대한 정보 갱신
        for w, nx in adj[x]:
            if not check[nx] and w < minDist[nx]:
                parent[nx] = x
                minDist[nx] = w

    return mst, mst_weight

 

시간 복잡도 : $O(|V|^2)$