[자료구조] Krustkal Algorithm

Krustal Algorithm은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 방법이다. Krustal Algortihm의 설계 방법은 다음과 같다.

 

1) 그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정렬한다.

2) 그래프 G에서 가중치가 가장 높은 간선을 제거한다. 정점을 그래프에서 분리시키는 간선은 제거할 수 없으므로 이런 경우 그 당므으로 가중치가 높은 간선을 제거한다.

3) 그래프 G에 간선이 n-1개만 남을 때까지 (2)를 반복한다.

4) 그래프에 간선이 n-1개만 남으면 최소 비용 신장 트리가 완성된다.

 

[python으로 구현한 코드] 

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        x_root = self.find(parent, x)
        y_root = self.find(parent, y)

        if rank[x_root] < rank[y_root]:
            parent[x_root] = y_root
        elif rank[x_root] > rank[y_root]:
            parent[y_root] = x_root
        else:
            parent[y_root] = x_root
            rank[x_root] += 1

    def kruskal(self):
        result = []
        self.graph = sorted(self.graph, key=lambda item: item[2])

        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        i = 0
        while len(result) < self.V - 1:
            u, v, w = self.graph[i]
            i += 1

            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

# 예시 그래프
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)

# 크루스칼 알고리즘 실행
result = g.kruskal()

# 결과 출력
print("최소 비용 신장 트리:")
for u, v, weight in result:
    print(f"{u} - {v}: {weight}")