-
2021.06.30
프림의 최소 신장 트리 알고리즘(Prim's Minimum Spanning Tree Algorithm)
프림의 최소 신장 트리 알고리즘(Prim's Minimum Spanning Tree Algorithm) MST 문제 정점 집합 V의 가중치를 갖는 에지 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하는 문제 크루스칼 알고리즘(Kruskal Algorithm) 그래프의 모든 에지를 최소 힙 에 추가하고, 사이클을 만들지 않는 최소 가중치의 에지를 이용하여 MST를 구성함. 프림 알고리즘(Prim's Algorithm) BFS의 동작 방식과 유사함. 먼저 시작 정점을 이용하여 경계를 구성함. 경계는 이전에 방문했던 정점들에 의해 구성됨. 현재 경계에 인접한 정점을 반복적으로 탐색함. 이때 프림 알고리즘은 경계를 관통하는 에지 중에서 가장..
-
2021.06.26
크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm)
크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm) 최소 신장 트리(Minimum Spanning Tree) 정점(Vertex) 의 집합 V와 가중치를 갖는 에지(Edge) 의 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소 인 트리 T 크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm) 1956년에 발표됨. 알고리즘 ① 그래프 G의 모든 에지를 최소 힙 H에 추가함. ② H로부터 에지 e를 하나 꺼냄. e : 모든 에지 중에서 가장 가중치가 작은 에지 ③ e이 양 끝 정점이 이미 T에 있을 경우, e로 인해 T에서 사이클이 발생할 수 있음...
