[Daira i Noor] Python Algorithm (3) - Minimum Spanning Tree

Graph 알고리즘

가장 기본이 되는 그래프 알고리즘인 DFS와 BFS에 대한 이야기는 아래의 링크를 통해 확인할 수 있다.

https://he-kate1130.tistory.com/73

[Daira i Noor] Python Algorithm (2) - Brute Force Search

 

오늘은 Minimum spanning tree에 대한 이야기를 한다.

 

Minimum spanning tree (MST)

MST는 한국어로 최소 신장 트리라 한다. 

가중치가 있는 무방향의 그래프에서, 모든 정점을 포함하고, 사이클이 존재하지 않는 최소 비용의 트리를 의미한다.

 

간단히 말해서 최소한의 간선(비용)을 통해서 모든 정점을 연결하는 트리가 MST이다

 

특징

• 노드가 V개 일때 간선의 수는 V-1개
• 사이클이 없어야 한다.
• 모든 정점이 연결되어야 한다
• 최소 비용으로 연결되어야 한다.

 

알고리즘

MST문제를 해결하는 알고리즘은 크게 두개가 있다

• Kruskal
  간선을 가중치가 오름차 순으로 정렬 후, 낮은것 부터 하나씩 선택한다.
  이때 사이클이 발생하지 않으면 선택하고, 사이클이 발생하면 다음 가중치로 넘어가 확인한다.
  • 시간 복잡도: O(E log E)    (간선의 수=E)

 

• Prim
  하나의 정점을 먼저 시작 점으로 정하고, 여기서부터 가장 낮은 가중치의 간선을 선택해나간다.
  즉, 인점한 간선 중 가장 작은 값을 선택한다. 이때 간선과 연결된 노드는 기존에 연결되어있지 않아야 한다.
  • 시간 복잡도: O(E log V)

 

두 알고리즘에 대해서는 아래에서 코드와 함께 더 확인하자

 

Kruskal

기본 접근은 다음과 같다.

1. 간선을 가중치가 오름차 순으로 정렬
2. 낮은것 부터 하나씩 확인한다.
   1. 사이클이 발생하지 않으면 간선 선택 (사이클x = Find 에서 조상이 다름)
   2. 사이클이 발생하면 다음 가중치의 간선으로 넘어간다. 
3. 모든 노드가 연결될 때 까지 반복한다. 

 

접근은 간단하다. 문제는 '사이클'이 발생하는지, 발생하지 않는지 확인하는 것이다.

사이클의 발생여부는 유니온-파인드 알고리즘을 통해 확인한다.

 

Kruskal방식의 시간 복잡도는 O(ElogE)

 

Union - Find

• Find: 우리 집합의 조상님 노드를 찾기
  • i의 조상 노드를 parent[i]로 한다

 

• Union: 두개의 집합을 하나의 집합으로 합친다
  • i와 j의 조상을 하나로 통일한다. parent[i]=parent[j]

 

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n #집합에 있는 노드의 개수

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

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            # Union by rank
            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

 

 

 

Prim

Prim's algorithm의 기본 접근은 다음과 같다. 

1. 시작 정점을 정하여 시작. 
2. 연결된 정점들 중, 연결되지 않은 정점으로의 최소 비용간선을 선택.
3. 모든 정점을 방문한 경우 종료

 

Heap Q

최소힙을 활용해 구현한다. 

즉, 최소힙을 통해서 가장 낮은 가중치 간선을 pop 한다.

 

# heapq모듈을 통해 최소 힙을 사용
import heapq

# PRIM 알고리즘
def prim(graph, start_node):

	#visited에 있는 노드는 방문하지 않는다
	visited = set() 
    #(비용, 시작노드 번호)
    min_heap = [(0,start_node)]
    #간선의 비용
    total_cost = 0
    
    while min_heap: #더이상 방문 가능한 인접 가능한 노드가 없을 때 까지
    
    	cost, node = heapq.heappop(min_heap)
        
        if node not in visited:
        	visited.add(node)
            total_cost+=cost
            
            for neighbor, w in graph[node].items(): 인접한 노드들 추가
            	if neighbor not in visited:
                	heapq.heappush(min_heap, (w, neighbor))
                    
    return total_cost