[알고리즘 in python] 신장 트리 / 최소 신장 트리 / 크루스칼 알고리즘 / 프림 알고리즘

그래프 (Graph)

• 정점(Vertex)과 이 정점들을 연결하는 간선(Edge)으로 구성된 데이터 구조.
• 가중치 그래프 (Weighted Graph) : 각 간선에 가중치(비용 또는 거리 등)가 할당된 그래프
• 비가중치 그래프 (Unweighted Graph)

 

신장 트리 (Spanning Tree) 알고리즘

• 그래프 이론에서 최소 비용으로 모든 정점을 연결하는 트리를 찾는 알고리즘
• 네트워크 설계, 도로 건설, 통신 케이블 배치와 같은 문제에서 최소 비용으로 네트워크 구성하기 위해 사용

 

신장 트리의 특징

• 주어진 그래프의 모든 정점을 포함하는 연결 그래프
• 사이클이 없는 그래프
• n-1개의 엣지를 가짐. n은 그래프의 정점 수

 

최소 신장 트리 (Minimum Spanning Tree, MST)

• 주어진 가중치 그래프에서 가능한 모든 신장 트리 중에서 가중치의 합이 최소인 트리
• 크루스칼 알고리즘, 프림 알고리즘을 통해 찾을 수 있음

크루스칼 알고리즘 (Kruskal's Alogorithm)

1. 모든 간선(E)을 가중치 기준으로 오름차순 정렬
2. 빈 집합(F)을 초기화하여 신장 트리 생성
3. 가장 낮은 가중치의 간선 선택
4. 사이클이 생기지 않으면 간선을 집합 F에 추가, 사이클이 생기면 그 간선 제외
5. 모든 정점이 연결될 때까지 과정 반복 : F가 정확히 (V-1)개의 간선 가질 때까지 반복

=> 크루스칼 알고리즘은 간선 중심적(Edge-centric)으로 작동, 주로 그래프의 엣지 개수가 적을 때 효율적

=> 시간 복잡도: O(ElogE)

 

class UnionFind:
    def __init__(self, n):
        # 초기화: 각 노드는 자기 자신이 부모인 독립적인 집합으로 시작합니다.
        self.parent = list(range(n))
        # rank는 트리의 높이를 추적하여, 두 집합을 합칠 때 최적화를 돕습니다.
        self.rank = [0] * n

    def find(self, u):
        # Find 연산: 경로 압축(path compression)을 사용하여 트리의 높이를 줄입니다.
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        # Union 연산: 두 집합을 랭크에 기반하여 결합합니다.
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            # 랭크가 높은 트리를 랭크가 낮은 트리의 루트로 설정합니다.
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                # 랭크가 동일하면 하나를 다른 하나의 루트로 하고, 랭크를 증가시킵니다.
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(n, edges):
    uf = UnionFind(n)  # n개의 정점으로 Union-Find 자료구조를 초기화합니다.
    mst = []  # 최소 신장 트리를 저장할 리스트를 초기화합니다.
    # 간선을 가중치에 따라 오름차순으로 정렬합니다.
    edges.sort(key=lambda x: x[2])  
    for u, v, weight in edges:
        # u와 v가 같은 집합에 속하지 않으면(즉, 사이클이 생성되지 않으면)
        if uf.find(u) != uf.find(v):  
            uf.union(u, v)  # 두 집합을 결합합니다.
            mst.append((u, v, weight))  # 최소 신장 트리에 현재 간선을 추가합니다.
    return mst  # 최소 신장 트리를 반환합니다.

# 예제 사용
n = 4  # 정점의 수
edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
print(kruskal(n, edges))

 

프림 알고리즘 (Prim's Algorithm)

1. 임의의 정점을 시작 정점으로 선택 후, 신장 트리에 추가
2. 신장 트리에 연결된 정점에서 나가는 간선 중 가장 가중치가 작은 간선을 선택하여, 연결된 새로운 정점을 신장 트리에 추가
3. 간선을 추가할 때마다 트리의 정점과 새로 추가된 정점 간의 모든 간선 검사
4. 모든 정점이 신장 트리에 포함될 때까지 이 과정 반복

=> 프림 알고리즘은 정점 중심적(Vertex-centric)으로 작동, 그래프가 밀집되어 있을 때 효율적

=> 시간 복잡도 : O(V^2), 힙(heap) 사용시 O(ElogV)

 

import heapq  # 최소 힙(min-heap)을 사용하기 위해 heapq 모듈을 임포트합니다.

def prim(n, edges):
    # 그래프를 인접 리스트로 표현합니다.
    graph = {i: [] for i in range(n)}
    for u, v, weight in edges:
        graph[u].append((weight, v))
        graph[v].append((weight, u))

    mst = []  # 최소 신장 트리를 저장할 리스트를 초기화합니다.
    visited = [False] * n  # 정점 방문 여부를 추적합니다.
    min_heap = [(0, 0)]  # 최소 힙을 초기화하고 시작 정점(정점 0)의 가중치를 0으로 설정합니다.
    total_cost = 0  # 최소 신장 트리의 총 비용을 저장하는 변수입니다.

    while min_heap:
        # 최소 힙에서 가장 작은 가중치를 가진 간선을 꺼냅니다.
        weight, u = heapq.heappop(min_heap)
        if not visited[u]:
            visited[u] = True  # 현재 정점을 방문했음을 표시합니다.
            total_cost += weight  # 최소 신장 트리의 총 비용에 현재 간선의 가중치를 추가합니다.
            mst.append(u)  # 현재 정점을 최소 신장 트리에 추가합니다.

            # 현재 정점(u)과 연결된 모든 인접 간선을 확인합니다.
            for next_weight, v in graph[u]:
                if not visited[v]:  # 인접 정점이 방문되지 않았다면
                    # 최소 힙에 인접 간선을 추가합니다.
                    heapq.heappush(min_heap, (next_weight, v))

    return total_cost, mst  # 최소 신장 트리의 총 비용과 트리를 반환합니다.

# 예제 사용
n = 4  # 정점의 수
edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
print(prim(n, edges))