3-2. [그래프 탐색] Kruskal, Prim (최소신장트리)

크루스칼

• 빠른 간선 순서로 탐색한다 (결과값: 최소신장트리에 해당하는 간선 리스트)
• 단, 사이클을 만들지 않아야 한다
  • 간선의 두 정점이 서로 다른 분리집합에 있어야 한다

graph = {
    "vertices": ["A", "B", "C", "D"],
    "edges": [
        (6, "A", "B"),
        (3, "A", "C"),
        (2, "B", "C"),
        (1, "B", "D"),
        (9, "C", "D"),
    ],
}


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


def union(x, y):
    rx = find(x)
    ry = find(y)
    if rx != ry:
        parent[ry] = rx


def kruskal():
    # 1. 초기화
    for node in graph["vertices"]:
        parent[node] = node

    # 2. 간선 weight 기반 sorting
    edges = graph["edges"]
    edges.sort()

    # 3. 간선 선택
    mst = []
    for w, n1, n2 in edges:
        if find(n1) != find(n2):  # 싸이클 없는
            union(n1, n2)
            mst.append((w, n1, n2))  # 빠른 간선 순서로 선택

    return mst


parent = {}  # {'A': 'A', 'B': 'A'}
print(kruskal())  # [(1, 'B', 'D'), (2, 'B', 'C'), (3, 'A', 'C')]

 

 

Prim

• 빠른 간선 순서로 탐색한다 (결과값: 최소신장트리에 해당하는 간선 리스트)
  • 구현방법: 인접 간선을 힙에 추가... 반복 
  • 자료구조: 힙과 연결정점 리스트
• 단, 사이클을 만들지 않아야 한다
  • 연결할 정점은 [연결된 정점 리스트]에 없어야 한다 

import heapq

graph = {
    "A": [(6, "A", "B"), (3, "A", "C")],
    "B": [(6, "B", "A"), (2, "B", "C"), (1, "B", "D")],
    "C": [(3, "C", "A"), (2, "C", "B"), (9, "C", "D")],
    "D": [(1, "D", "B"), (9, "D", "C")],
}


def prim(start):
    # 힙과 연결정점
    qu = []
    for x in graph[start]:
        heapq.heappush(qu, x)
    visited = [start]

    mst = []
    while qu:
        w, n1, n2 = heapq.heappop(qu)

        if n2 not in visited:  # 싸이클 없는
            visited.append(n2)
            mst.append((w, n1, n2))
            print((w, n1, n2))  # 빠른 간선 순서로 선택

            for x in graph[n2]:
                heapq.heappush(qu, x)

    return mst


print(prim("A"))  # [(3, 'A', 'C'), (2, 'C', 'B'), (1, 'B', 'D')]