[알고리즘] Kruskal & Prim Algorithm in Python

Kruskal & Prim Algorithm을 Python으로 구현해보고 해당 알고리즘에 대해 분석해보자

Kruskal Algorithm

그래프 이론에서 사용되는 그래프 최소 신장 트리 (Minimum Spanning Tree,MST)를 찾는 알고리즘 중 하나

그래프의 모든 정점을 연결하면서 가중치가 작은 간선들로 이루어진 트리를 구성

• 간선의 가중치 기반 선택
• 사이클 방지
• 그리디 알고리즘

그래프의 모든 간선을 가중치 순으로 정렬
정렬된 간선 목록을 처음부터 순회하면서 사이클을 형성하지 않는 간선 선택
선택한 간선을 트리에 추가
> 해당 알고리즘을 통해 MST를 리턴

G = { 
    'vertices' : [],
    'edges': []
}

parent = dict() 
rank = dict() 

def initial(node):
  parent[node] = node 
  rank[node] = 0 

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

def union(node_a, node_b):
  root_a = find(node_a)
  root_b = find(node_b)
  if rank[root_a]>rank[root_b]:
    parent[root_b] = root_a
  else:
    parent[root_a] = root_b
    if rank[root_a] == rank[root_b]:
      rank[root_b]+=1


def KruskalMST(G):
  mst = []
  for node in G['vertices']:
    initial(node)
  e = G['edges']
  e.sort(key=lambda x : x[2])

  for edge in e:
    node_a, node_b, weight = edge
    if find(node_a) != find(node_b):
      union(node_a,node_b)
      mst.append(edge)

  return mst

v, e = map(int,input().split()) 
for i in range(v):
  G['vertices'].append(i)

for i in range(e):
  u, v, weight = map(int, input().split())
  G['edges'].append((u,v,weight))

KruskalMST(G)

 

크루스칼 알고리즘의 시간 복잡도는 (E log E) - 간선의 수 E에 따라 변화함

 

Prim Algorithm

그래프 이론에서 사용되는 그래프 최소 신장 트리 (Minimum Spanning Tree,MST)를 찾는 알고리즘 중 하나

시작 정점을 통해 해당 정점에 연결된 간선의 가중치가 작은 것을 선택해가는 알고리즘

• 시작 정점 선택
• 그리디 알고리즘
• 사이클 방지

import heapq

v, e = map(int,input().split()) # 노드 수, 간선 수
visited = [0] * (v+1) # 노드의 방문 정보 초기화
graph = [[] for _ in range(v+1)]  # 그래프 초기화

# 무방향 그래프 생성
for i in range(e): # 간성 정보 입력 받기
    u, v, weight = map(int,input().split())
    graph[u].append([weight, u, v])
    graph[v].append([weight, v, u])


# 프림 알고리즘
def PrimMST(start):
    visited[start] = 1 # 방문 갱신
    candidate = graph[start] # 인접 간선 추출
    heapq.heapify(candidate) # 우선순위 큐 생성
    mst = [] # mst

    while candidate:
        weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
        if visited[v] == 0: # 방문하지 않았다면
            visited[v] = 1 # 방문 갱신
            mst.append((u,v,weight)) # mst 삽입

            for edge in graph[v]: # 다음 인접 간선 탐색
                if visited[edge[2]] == 0: # 방문한 노드가 아니라면, (순환 방지)
                    heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입

    return mst

start_node = int(input())
print(PrimMST(start_node))

일반적인 프림 알고리즘은 O(E log V)의 시간 복잡도를 가집니다
대규모 그래프에서 효율적으로 동작할 수 있습니다

 

최소 신장 트리를 만드는 kruskal과 prim 알고리즘에 대해 알아보았습니다