당신은 주제를 찾고 있습니까 “최소 비용 신장 트리 – 크루스칼 알고리즘 – 최소 신장 트리“? 다음 카테고리의 웹사이트 sk.taphoamini.com 에서 귀하의 모든 질문에 답변해 드립니다: sk.taphoamini.com/wiki. 바로 아래에서 답을 찾을 수 있습니다. 작성자 JANG 이(가) 작성한 기사에는 조회수 4,696회 및 좋아요 56개 개의 좋아요가 있습니다.
Table of Contents
최소 비용 신장 트리 주제에 대한 동영상 보기
여기에서 이 주제에 대한 비디오를 시청하십시오. 주의 깊게 살펴보고 읽고 있는 내용에 대한 피드백을 제공하세요!
d여기에서 크루스칼 알고리즘 – 최소 신장 트리 – 최소 비용 신장 트리 주제에 대한 세부정보를 참조하세요
Kruskal’s algorithm. – minimum spanning tree
최소 비용 신장 트리 주제에 대한 자세한 내용은 여기를 참조하세요.
[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란
MST = Minimum Spanning Tree = 최소 신장 트리 · 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 …
Source: gmlwjd9405.github.io
Date Published: 4/30/2022
View: 7177
최소 비용 신장 트리 – 나무위키:대문
1. 최소 비용 신장 트리(minimum spanning tree, MST)[편집]. 신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 …
Source: namu.wiki
Date Published: 5/24/2021
View: 1665
[알고리즘] 최소 비용 신장 트리 – Minimum Cost Spanning Tree
최소 비용 신장 트리, 최소 스패닝 트리라고 불리는 이 알고리즘은 가중치 무방향 그래프에서 모든 정점을 연결할 때 최소의 비용으로 연결할 수 있는 …
Source: icksw.tistory.com
Date Published: 3/7/2021
View: 5891
[알고리즘] 최소 비용 신장 트리 :: 늦깎이 IT
최소 비용 신장트리 (Minimum Spanning Tree)는 그래프에서 가능한 신장트리들 중에서 가중치의 합이 최소인 신장트리를 말한다.
Source: ghkvud2.tistory.com
Date Published: 2/13/2022
View: 3963
[알고리즘] 최소 신장 트리(Minimum Spanning Tree) – 싸비 블로그
신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미합니다. n 개의 정점이 있다면 신장 트리의 간선 수는 n …
Source: ssabi.tistory.com
Date Published: 11/5/2021
View: 4393
최소 신장 트리(Minimum Spanning Tree) – 스터디룸
최소 비용 신장 트리(Minimum cost Spanning Tree)라고도 부르는 사람들이 있지만 대부분 최소 신장 트리로 사용한다. 그래프의 간선에 가중치 등 값이 …
Source: 8iggy.tistory.com
Date Published: 6/9/2022
View: 2938
최소 비용 신장트리(MST, Minimum Spanning Tree)란?
최소 비용 신장 트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 출처 : https://kingpodo.tistory.com/49 출처 : …
Source: devlog-wjdrbs96.tistory.com
Date Published: 6/3/2022
View: 9816
[AL] 7. 최소 비용 신장 트리(MST) 알고리즘 – SuperM
7. 최소 비용 신장 트리(MST) 알고리즘 신장 트리 (Spanning Tree) 최소 비용 신장 트리 (MST) Kruskal MST 알고리즘 Prim MST 알고리즘 1. 신장 트리 (Spanning Tree) …
Source: hibee.tistory.com
Date Published: 12/24/2021
View: 255
주제와 관련된 이미지 최소 비용 신장 트리
주제와 관련된 더 많은 사진을 참조하십시오 크루스칼 알고리즘 – 최소 신장 트리. 댓글에서 더 많은 관련 이미지를 보거나 필요한 경우 더 많은 관련 기사를 볼 수 있습니다.
주제에 대한 기사 평가 최소 비용 신장 트리
- Author: JANG
- Views: 조회수 4,696회
- Likes: 좋아요 56개
- Date Published: 2019. 3. 21.
- Video Url link: https://www.youtube.com/watch?v=BJZwRWNGFMU
Minimum Cost Spanning Tree
반응형
안녕하세요! Ick입니다.
최소 비용 신장 트리 – Minimum Cost Spanning Tree
오늘은 여러 알고리즘 중에서 최소 비용 신장 트리라고 불리는 알고리즘에 대해 알아보려고 합니다!
최소 비용 신장 트리, 최소 스패닝 트리라고 불리는 이 알고리즘은 가중치 무방향 그래프에서 모든 정점을 연결할 때 최소의 비용으로 연결할 수 있는 방법을 찾는 알고리즘입니다.
가중치 무방향 그래프는 무엇일까요?
위와 같이 그래프가 있을 때 정점 사이에 가중치가 있고 간선에 방향이 없는 그래프를 가중치 무방향 그래프라고 합니다.
예를 들어 위의 그래프에서 정점 1에서 정점 3으로 가고 싶다면 25의 가중치를 가진 간선을 사용하면 되는 것입니다.
이번 글에서 배울 최소 비용 신장 트리는 이러한 그래프에서 모든 정점을 최소의 비용으로 연결하는 방법입니다.
단 모든 정점을 연결할 때 사이클을 형성하지 않아야 합니다.
여기서 사이클이란!
위의 그림과 같이 간선들을 선택한 경우가 사이클이 발생하게 된 경우입니다.
위의 그림에서 간선 하나를 제외하더라도 3개의 정점은 연결된 상태이므로 최소의 비용을 고려하는 이 알고리즘에서 사이클의 존재는 비효율적인 것이죠!
이 때문에 간선의 수는 (정점 – 1)개 만큼만 존재할 때 정답이 될 수 있습니다.
그럼 우선 위의 그래프에서 최소 비용 신장트리는 어떤 모양일까요?
위와 같이 2개의 트리가 모두 정답이 될 수 있습니다.
여기서 알 수 있는 점은 어떠한 가중치 무방향 그래프에서 최소비용 신장 트리는 여러 개 존재할 수 있다는 점입니다.
그럼 이젠 이러한 정답을 얻기 위해 어떤 방식으로 진행하는지 알아보겠습니다.
최소 비용 신장 트리 알고리즘엔 Kruskal(크루스칼) 알고리즘, Prim(프림) 알고리즘이 가장 유명합니다.
그럼 두 알고리즘을 알아볼까요?
Kruskal (크루스칼) 알고리즘
먼저 Kruskal 알고리즘을 살펴보도록 하겠습니다.
크루스칼 알고리즘은 간선을 기준으로 트리를 만드는 방법입니다.
간선을 기준으로 한다는 것은 간선의 가중치를 기준으로 하는 것인데 가중치가 작은 간선부터 트리에 추가하겠다는 말입니다.
아까 본 그래프를 사용해서 방법을 이해해 보겠습니다.
위의 그림에서 간선들의 가중치는 [ 25, 38, 17, 38, 26, 42, 9, 15, 19, 51 ] 입니다.
이 가중치들을 크기 순으로 정렬하면 [ 9, 15, 17, 19, 25, 26, 38, 38, 51 ] 입니다.
따라서 가중치가 9인 간선부터 트리에 추가하는 것입니다.
그다음은 15를 추가하고, 17, 19, 25를 추가합니다. 그러다 26을 추가하려고 할 때 문제가 발생합니다.
위의 그림에서 26 가중치를 가진 간선은 초록색으로 표시했습니다.
이때 만약 26 가중치를 가진 간선을 추가하게 되면 사이클이 발생하게 됩니다.
최소비용 신장 트리에서는 이런 사이클이 없어야 하기 때문에 26은 추가할 수 없습니다.
따라서 그다음 작은 38 가중치를 가진 간선을 고려하는데 여기선 두 개가 있고 두 개 모두를 추가하면 사이클이 발생하므로 한 개만 추가할 수 있습니다.
그렇게 하면 간선의 수가 6개가 되고 그래프의 정점보다 1 작게 되므로 위와 같은 그래프가 정답이 됩니다.
Prim (프림) 알고리즘
아까 본 크루스칼 알고리즘은 간선을 중심으로 트리를 구성했다면 프림 알고리즘은 정점을 기준으로 트리를 구성하는 방법입니다.
다시 처음 그래프를 가져와 보겠습니다.
정점을 기준으로 트리를 구성한다는 말을 이해해 보겠습니다.
먼저 시작 정점을 임의로 정합니다. 저는 정점 1에서 시작해보겠습니다.
먼저 정점 1에는 25, 38 가중치를 가진 간선들이 있고 여기서 작은 간선을 선택합니다.
그렇게 도착한 정점 3에는 17, 25, 26 가중치를 가진 간선들이 있습니다. 가장 작은 17 가중치를 가진 간선을 선택하고 정점 5에 갈 때까지 동일하게 반복합니다.
정점 5에 도착하면 연결된 어떤 간선을 선택해도 사이클이 발생하게 됩니다.
따라서 현재 선택되지 않은 정점을 임의로 선택해 다시 진행합니다.
예를 들어 정점 7을 선택한 뒤 동일하게 반복하면 다음 결과가 나올 거예요.
이렇게 최소비용 신장 트리를 찾을 수 있습니다.
실제 코드로 구현하는 방법은 아래 링크를 확인해주세요!
크루스칼 알고리즘
프림 알고리즘
감사합니다~
반응형
[알고리즘] 최소 비용 신장 트리 :: 늦깎이 IT
[신장트리란?]신장트리 (Spanning Tree)는 그래프 중 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 말한다.
N개의 정점을 가지는 그래프의 최소 간선의 수는 (N – 1)개 이고, 모든 정점이 (N – 1)개의 간선으로 연결되어 있으면 필연적으로 트리의 형태로 이루어질 수 밖에 없다.
4개의 노드로 이루어진 아래와 같은 그래프를 보면, 신장트리를 구성하는 방법은 유일하지 않음을 알 수 있다.
[최소 비용 신장트리란?]최소 비용 신장트리 (Minimum Spanning Tree)는 그래프에서 가능한 신장트리들 중에서 가중치의 합이 최소인 신장트리를 말한다. 위의 그림에서는 간선의 가중치가 없기때문에 최소신장트리(MST)를 찾을 수 없다.
그러나, 아래의 그림과 같이 간선마다 가중치가 주어질 경우, 간선의 합이 최소이면서 신장트리의 조건을 만족하는 임의의 신장트리. 즉, 최소신장트리를 찾을 수 있다.
[크루스칼 알고리즘]크루스칼 (Kruscal) 알고리즘은 그래프의 모든 정점을 최소 비용으로 연결하는 알고리즘이다.
크루스칼 알고리즘의 동작 원리는 다음과 같다.
간선들을 가중치의 오름차순으로 정렬한다.
간선들을 그 순서대로 하나씩 선택하되, 이미 선택된 간선들과 사이클이 형성되면 선택하지 않는다.
N – 1 개의 간선이 선택되면 종료한다.
크루스칼 알고리즘에서 사이클이 형성이 되는지 아닌지를 확인하는 방법은 [ Disjoint Set ]를 사용한다.
[사이클 검사]크루스칼 알고리즘의 과정 중에서 “사이클이 형성되면 선택하지 않는다.” 라고 했다. 이 과정에 초점을 맞춰 어떻게 최소비용 신장트리를 구성하는지 살펴본다.
[초기 상태]그래프의 초기상태에서는 아래 그림과 같이 나타낼 수 있다.
각각의 노드(a, b, …. i)가 집합으로 표현되고, 각 노드들을 연결하는 간선의 가중치가 표현되어 있다.
각 간선의 가중치를 오름차순으로 정렬한 후, 그 간선들을 차례대로 선택한다.
이 상태에서 최소 신장 트리를 반환할 집합 A를 공집합으로 초기화하고 조건을 만족하는 간선들을 집합 A에 추가시킨다.
간선 E(h, g) 확인
간선 E(h, g)를 선택함에 따라 사이클이 형성되는지 확인한다.
사이클을 확인하는 방법은 노드 h와 g가 같은 집합에 속해있는지 확인하면 된다.
노드 h와 g가 각각 다른 집합에 속해있으므로 집합 A에 간선 E(h, g)를 추가하고 집합 h와 g를 합집합한다.
간선 E(c, i) 확인
노드 c와 i는 같은 집합에 속하지 않으므로, 간선 E(c, i)를 집합 A에 추가하고, 집합 c와 i를 합집합한다.
간선 E(f, g) 확인
노드 f와 g는 같은 집합에 속하지 않으므로, 간선 E(f, g)를 집합 A에 추가하고, 집합 f와 g를 합집합한다.
간선 E(a, b) 확인
노드 a와 b는 같은 집합에 속하지 않으므로, 간선 E(a, b)를 집합 A에 추가하고, 집합 a와 b를 합집합한다.
간선 E(c, f) 확인
노드 c와 f는 같은 집합에 속하지 않으므로, 간선 E(c, f)를 집합 A에 추가하고, 집합 c와 f를 합집합한다.
간선 E(i, g) 확인
노드 i와 g는 같은 집합에 속하므로, 간선 E(i, g)를 집합 A에 추가하지 않고 건너뛴다.
간선 E(i, h) 확인
노드 i와 h는 같은 집합에 속하므로, 간선 E(i, h)를 집합 A에 추가하지 않고 건너뛴다.
간선 E(c, d) 확인
노드 c와 d는 같은 집합에 속하지 않으므로, 간선 E(c, d)를 집합 A에 추가하고, 집합 c와 d를 합집합한다.
간선 E(b, c) 확인
노드 b와 c는 같은 집합에 속하지 않으므로, 간선 E(b, c)를 집합 A에 추가하고, 집합 b와 c를 합집합한다.
간선 E(a, h) 확인
노드 a와 h는 같은 집합에 속하므로, 간선 E(a, h)를 집합 A에 추가하지 않고 건너뛴다.
간선 E(d, e) 확인
노드 d와 e는 같은 집합에 속하지 않으므로, 간선 E(d, e)를 집합 A에 추가하고, 집합 d와 e를 합집합한다.
N – 1 개의 간선을 선택했으므로 종료한다.
[의사 코드]1 2 3 4 5 6 7 8 9 10 11 12 MST – KRUSKAL(G, W) A is empty for each vertex v ∈ V[G] do MAKE – SET(v) sort edges of E order by weight asc for each edge(u,v) ∈ E if FIND – SET(u) ! = FIND – SET(v) then A ← A U {(u,v)} UNION(u, v) return A cs
2)번 라인에서 MST를 담는 집합 A를 공집합으로 초기화한다.
3)번 라인에서 모든 노드에 대해서 MAKE-SET 연산을 수행한다.
5)번 라인에서 모든 간선들을 오름차순으로 정렬한다.
7)번 라인에서 각각의 간선들을 확인하며 임의의 간선 E(u, v)에 대해서 사이클이 발생하는지 확인한다.
9)번 라인에서 사이클이 발생하지 않으면, 집합 A에 간선 E(u, v)를 포함시키고 UNION 연산을 수행한다.
[시간 복잡도]Make-Set의 시간 복잡도는 O(N)이다.
모든 간선을 오름차순으로 정렬하는 시간 복잡도는 간선의 갯수를 M이라고 할 때, O(MlongM)이다.
모든 간선을 순회하는데 걸리는 시간은 O(M)이고, 각각의 순회마다 Find와 Union 하는 연산은 O(1)이다.
결론적으로, 크루스칼 알고리즘의 시간 복잡도는 O(MlogM)이다.
[JAVA 코드]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Kruskal { static int N = 9 ; public static void main( String [] args) { Graph graph = new Graph(N); graph.addEdge( 1 , 2 , 4 ); graph.addEdge( 2 , 3 , 8 ); graph.addEdge( 3 , 4 , 7 ); graph.addEdge( 4 , 5 , 9 ); graph.addEdge( 5 , 6 , 10 ); graph.addEdge( 6 , 7 , 2 ); graph.addEdge( 7 , 8 , 1 ); graph.addEdge( 8 , 9 , 7 ); graph.addEdge( 1 , 8 , 8 ); graph.addEdge( 2 , 8 , 11 ); graph.addEdge( 3 , 6 , 4 ); graph.addEdge( 3 , 9 , 2 ); graph.addEdge( 4 , 6 , 14 ); graph.addEdge( 7 , 9 , 6 ); kruskalMST(graph); } public static void kruskalMST(Graph graph) { Collections.sort(graph.list); Edge[] result = new Edge[graph.V]; int mst = 0 ; int e = 1 ; int idx = 0 ; while (e < graph.V - 1 ) { Edge edge = graph.list.get(idx + + ); if (find(graph.subset, edge.src) ! = find(graph.subset, edge.dest)) { union(graph.subset, edge.src, edge.dest); mst + = edge.weight; result[e + + ] = edge; } } for ( int i = 1 ; i < e; i + + ) System . out . println (( char ) (result[i].src - 1 + 'a' ) + " <-> ” + ( char ) (result[i].dest – 1 + ‘a’ ) + ” : ” + result[i].weight); System . out . println ( “Kruskal MST : ” + mst); } public static int find(Subset[] subset, int u) { if (subset[u].parent = = u) return u; else return subset[u].parent = find(subset, subset[u].parent); } public static void union(Subset[] subset, int u, int v) { int uRoot = find(subset, u); int vRoot = find(subset, v); if (uRoot = = vRoot) return ; if (subset[uRoot].rank < subset[vRoot].rank) subset[uRoot].parent = vRoot; else if (subset[uRoot].rank > subset[vRoot].rank) subset[vRoot].parent = uRoot; else { subset[uRoot].parent = vRoot; subset[vRoot].rank + = 1 ; } } } class Graph { int V; List < Edge > list; Subset[] subset; public Graph( int size) { this .V = size + 1 ; list = new ArrayList < > (); subset = new Subset[V]; for ( int i = 1 ; i < V; i + + ) { subset[i] = new Subset(i, 0 ); } } public void addEdge( int src, int dest, int weight) { list. add ( new Edge(src, dest, weight)); } } class Edge implements Comparable < Edge > { int src; int dest; int weight; public Edge( int src, int dest, int weight) { this .src = src; this .dest = dest; this .weight = weight; } @Override public int compareTo(Edge e) { return this .weight – e.weight; } } class Subset { int parent; int rank; public Subset( int parent, int rank) { this .parent = parent; this .rank = rank; } } Colored by Color Scripter cs
[ 프림의 알고리즘 ]크루스칼 알고리즘은 간선들의 가중치를 오름차순으로 정렬하고, 가중치가 작은 간선들부터 선택하기 때문에 여러 개의 작은 트리가 하나의 더 큰 트리로 합쳐지는 방법이라고 볼 수 있다.
이에 반해, 프림의 알고리즘은 임의의 노드부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법을 사용한다.
프림 알고리즘의 동작 방식은 다음과 같다.
임의의 노드를 출발 노드로 선택한다.
출발 노드를 포함하는 트리를 점점 확장해간다.
매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택한다.
아래 그림을 보자.
그림 (a)에서는 노드 a를 출발 노드로 선택하고 집합 S에 추가한다. 그 다음, 집합 S에 속한 노드로부터 집합 S에 속하지 않은 노드들간의 간선을 비교하여 최소 가중치를 갖는 간선을 선택한다. 즉, (b) 그림처럼 간선 e(a, b)와 e(a, h)를 비교후, 더 작은 가중치를 갖는 e(a, b)를 선택하고 노드 b를 집합 S에 추가한다.
그림 (c)에서도 집합 S에 속한 노드 a, b와 집합 S에 속하지 않은 노드들간의 가중치를 비교하고, 가장 작은 가중치를 갖는 노드를 집합 S에 추가한다. 그림 (c)에서는 노드 c가 선택되었다. 이와 같은 방법으로 그림 (d)에서 노드 i 가 선택되었다.
그림 (e)에서는 노드 f를, 그림 (f)에서는 노드 g를 선택했다.
그림 (g)에서는 노드 h를, 그림 (h)에서는 노드 d를 선택했다.
마지막으로 그림 (i)에서 노드 e를 선택한다. 집합 S가 노드의 갯수 N과 같아졌으므로 알고리즘을 종료한다.
[ 초기 상태 ]프림의 알고리즘 동작 과정을 조금 더 자세히 설명한다. 집합 Va에 포함된 노드들과 Va에 포함되지 않은 노드들을 연결하며 진행한다.
Va에 속하지 않은 각 노드 v에 대해서 다음과 같은 값을 유지한다.
key(v) : 이미 Va에 속한 노드와 자신을 연결하는 간선들 중 가중치가 최소인 w(u, v)의 가중치
π(v) : 그 간선 (u, v)의 끝점 u
아래 그림을 보자.
집합 Va에는 노드 a, b, c, i가 포함되어 있다. 집합 Va에 속하지 않는 노드 d, e, f, g, h에 대해서 key와 π값을 갱신한다.
노드 d를 살펴보자. 노드 d와 Va에 속한 노드들간에 연결된 간선은 e(c, d)밖에 없다. 그러므로 key(d) = 7이고, π(d) = c이다.
노드 e를 살펴보자. 노드 e와 Va에 속한 노드들간에 연결된 간선은 존재하지 않는다. 그러므로 key(c) = ∞이고, π(c) = a이다. π(c) = a는 무시해도 된다.
노드 f를 살펴보자. 노드 f와 Va에 속한 노드들간에 연결된 간선은 e(c, f)밖에 없다. 그러므로 key(f) = 4이고, π(f) = c이다.
노드 g를 살펴보자. 노드 g와 Va에 속한 노드들간에 연결된 간선은 e(g, i)밖에 없다. 그러므로 key(g) = 6이고, π(g) = i이다.
노드 h를 살펴보자. 노드 h와 Va에 속한 노드들간에 연결된 간선은 e(a, h)와 e(b, h), e(h, i)가 있다. 이중 가장 작은 가중치를 갖는 간선은 e(h, i)이므로, key(h) = 7이고, π(h) = i이다.
집합 Va에 속하지 않는 모든 노드들에 대하여 key값과 π값을 갱신했다면, 이중 가장 작은 key값을 갖는 노드를 Va 집합에 포함시킨다. 가장 작은 키 값은 key(f) = 4 이므로, 집합 Va에 노드 f를 포함시킨다. 아래 그림을 보자.
집합 Va에 노드 f를 추가한 뒤에 Va에 속하지 않은 모든 노드들의 key값과 π값을 갱신해야 한다.
노드 d를 살펴보자. 노드 d와 Va에 속한 노드들간에 연결된 간선은 e(c, d)와 e(d, f)이다. 기존의 key(d) = 7 보다 e(d, f) = 14의 값이 더 크므로 key(d) = 7로 유지된다.
노드 e를 살펴보자. 노드 e와 Va에 속한 노드들간에 연결된 간선은 e(d, e)이다. 기존의 key(e) = ∞ 보다 e(d, e) = 10의 값이 더 작으므로 key(e) = 10, π(e) = f로 갱신된다.
노드 g를 살펴보자. 노드 g와 Va에 속한 노드들간에 연결된 간선은 e(g, i), e(f, g)이다. 기존의 key(g) = 6 보다 e(g, f) = 2의 값이 더 작으므로 key(g) = 2, π(g) = f로 갱신된다.
이때 노드 h에 대한 key값과 π값을 갱신하지 않는 이유는 무엇일까?
노드 f를 집합 Va에 추가하기전과 추가한 이후에 변하는 것은 오로지 노드 f가 집합 Va에 속해있는지 아닌지이다.
그러므로, 노드 f와 인접하지 않은 노드 h에 대해서는 갱신 여부를 확인할 필요조차 없는 것이다.
[ 의사 코드 ]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 MST – PRIM(G, w, r) // r은 시작 노드 for each u ∈ V do key[u] ← ∞ π[u] ← null end Va ← {r} key[r] ← 0 while | Va | < N do find u ∉ Va the minimum key Va ← Va U {u} for each v ∉ Va adjacent to u do if key[v] > w(u, v) then key[v] ← w(u, v) π[v] ← u end end end cs
2)~5)번 라인에서 각각의 노드에 대한 key 값과 π값을 초기화한다.
7)번 라인에서 시작 노드 r을 집합 Va에 추가한다.
10)번 라인에서 집합 Va의 크기가 N보다 작을 때 까지 반복을 수행한다.
11)번 라인에서 집합 Va에 포함되지 않는 노드들 중 key 값이 최소인 노드 u를 찾는다.
12)번 라인에서 집합 Va에 노드 u를 포함시킨다.
13)번 라인에서 노드 u와 인접한 모든 노드 v에 대해서 이미 저장된 key값과 w(u, v) 값을 비교해 갱신한다.
[ 시간 복잡도 ]그래프 G에 포함된 노드의 갯수를 N이라 하자.
집합 Va의 크기가 N과 같아질 때 까지 반복을 수행하므로 while 문은 N – 1번 반복하므로 시간 복잡도는 O(N)이다.
집합 Va에 속하지 않은 최소 key 값을 갖는 노드 u를 찾는 연산은 최대 N번이므로 시간 복잡도는 O(N)이다.
최소 key 값을 갖는 노드 u에 인접한 노드들은 최대 degree(u) = N – 1이므로 시간 복잡도는 O(N)이다.
노드 u와 인접한 노드 v의 key 값을 비교해서 갱신하는 시간 복잡도는 O(1)이다.
즉, 전체 시간 복잡도는 O( N * ( N +( N * 1 ) ) ) = O(N^2) 이다.
[ 더 생각해보기 ]위의 의사코드를 살펴보면, 집합 Va에 속하지 않은 노드들 중 가장 작은 key값을 갖는 노드를 찾는 연산을 반복하고, 이때의 시간 복잡도는 O(N)이라고 했다.
이때, 최소 힙 우선순위 큐를 사용하면 최소 key 값을 찾는 연산을 O(logN)시간에 수행할 수 있다.
[ 의사 코드 ]1 2 3 4 5 6 7 8 9 10 11 12 13 14 MST – PRIM(G, w, r) // r은 시작 노드 for each u ∈ V do key[u] ← ∞ π[u] ← null end key[r] ← 0 Q ← V[G] while Q ! = ∅ do u ← EXTRACT – MIN(Q) for each v ∈ Adj[u] do if v ∈ Q and w(u, v) < key[v] then π[v] ← u key[v] ← w(u, v) cs 2)~5)번 라인에서 각각의 노드에 대한 key 값과 π값을 초기화한다. 8)번 라인에서 모든 노드들을 우선순위 큐에 저장한다. 9)번 라인에서 큐에 저장된 노드들의 갯수만큼 반복한다. 10)번 라인에서 큐에 저장된 노드들 중 가장 작은 key값을 갖는 노드 u를 찾는다. 11)번 라인에서 노드 u에 인접한 모든 노드들 v를 찾는다. 12)번 라인에서 노드 v가 큐에 속해있고, key[v] 값이 w(u, v)보다 크다면 갱신한다. 노드 v가 큐에 속해있다는 것은 집합 Va에 포함되지 않았다는 뜻과 같다. 13), 14)번 라인에서 key 값과 π 값을 갱신한다. [ 시간 복잡도 ] 그래프 G에 포함된 노드의 갯수를 N, 간선의 갯수를 M개라고 하자. 큐의 사이즈가 0일때 까지 반복을 수행하므로 시간 복잡도는 O(N)이다. 큐에서 최소 값을 갖는 노드 u를 찾는 시간 복잡도는 O(logN)이다. 노드 u에 인접한 모든 노드 v를 찾는 시간 복잡도는 모든 노드들의 차수의 합만큼 반복하므로 아래 식을 만족한다. "모든 노드들의 차수의 합은 간선의 갯수에 2배를 한 것과 같다" 라는 성질을 이용한 것이다. 노드 u와 인접한 노드 v의 key 값을 비교해서 갱신하는 시간 복잡도는 O(logN)이다. 즉, 전체 시간 복잡도는 O(NlogN + MlogN) = O(MlogN)이다. [ JAVA 코드 ] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; public class Prim { static class Node { int dest; int weight; public Node( int dest, int weight) { this .dest = dest; this .weight = weight; } } static class Node2 implements Comparable < Node2 > { int key; int node; int prev; public Node2( int key, int node, int prev) { this .key = key; this .node = node; this .prev = prev; } public int compareTo(Node2 o) { if ( this .key < o.key) return - 1 ; else if ( this .key = = o.key) { return this .node - o.node; } else return 1 ; } } int size; Node2[] status; List < List < Node > > list; public Prim( int size) { this .size = size + 1 ; status = new Node2[ this .size]; list = new ArrayList < > (); for ( int i = 0 ; i < this .size; i + + ) { status[i] = new Node2(Integer.MAX_VALUE, i, - 1 ); List < Node > item = new ArrayList < > (); list. add (item); } } public void addEdge( int src, int dest, int weight) { list.get(src). add ( new Node(dest, weight)); list.get(dest). add ( new Node(src, weight)); } public void primMST( int start) { int sum = 0 ; status[start].key = 0 ; status[start].prev = 0 ; boolean [] mst = new boolean [ this .size]; PriorityQueue < Node2 > q = new PriorityQueue < > (); for ( int i = 1 ; i < this .size; i + + ) q.offer(status[i]); while ( ! q.isEmpty()) { Node2 node = q.poll(); mst[node.node] = true ; sum + = node.key; for ( int i = 0 ; i < list.get(node.node).size(); i + + ) { Node adj = list.get(node.node).get(i); if ( ! mst[adj.dest]) { if (status[adj.dest].key > adj.weight) { q.remove(status[adj.dest]); status[adj.dest].key = adj.weight; status[adj.dest].prev = node.node; q. add (status[adj.dest]); } } } } for ( int i = 1 ; i < this .size; i + + ) { if (i ! = start) System . out . println (( char ) (status[i].prev - 1 + 'a' ) + " -> ” + ( char ) (i – 1 + ‘a’ )); } System . out . println ( “Prim MST : ” + sum); } public static void main( String [] args) { Prim prim = new Prim( 9 ); prim.addEdge( 1 , 2 , 4 ); prim.addEdge( 2 , 3 , 8 ); prim.addEdge( 3 , 4 , 7 ); prim.addEdge( 4 , 5 , 9 ); prim.addEdge( 5 , 6 , 10 ); prim.addEdge( 6 , 7 , 2 ); prim.addEdge( 7 , 8 , 1 ); prim.addEdge( 8 , 9 , 7 ); prim.addEdge( 1 , 8 , 8 ); prim.addEdge( 2 , 8 , 11 ); prim.addEdge( 3 , 6 , 4 ); prim.addEdge( 3 , 9 , 2 ); prim.addEdge( 4 , 6 , 14 ); prim.addEdge( 7 , 9 , 6 ); prim.primMST( 1 ); } } Colored by Color Scripter cs
[알고리즘] 최소 신장 트리(Minimum Spanning Tree)
반응형
최소 신장 트리(Minimum Spanning Tree)
신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미합니다. n 개의 정점이 있다면 신장 트리의 간선 수는 n-1 개가 됩니다. 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리입니다. 가중치는 거리 , 비용 , 시간 등 여러가지로 응용할 수 있습니다. 최소 신장 트리의 대표적인 알고리즘으로는 프림 알고리즘(Prim’s Algorithm)과 크루스칼 알고리즘(Kruskal’s Algorithm)이 있습니다.
프림 알고리즘(Prim’s Algorithm)
프림 알고리즘은 로버트 프림(Robert C. Prim)이 만든 최소 신장 트리 알고리즘 입니다. 프림 알고리즘은 최소 신장 트리에 연결된 정점 주변에 있는 간선의 가중치 중 가장 작은 것을 골라 최소 신장 트리를 만드는 방법입니다. 프림 알고리즘으로 최소 신장 트리를 만드는 방법은 다음과 같습니다.
그래프와 비어 있는 최소 신장 트리를 만듦 임의의 정점을 시작 정점으로 선택하고 최소 신장 트리의 루트 노드로 삽입 최소 신장 트리에 삽입된 정점과 이 정점과 인접한 정점의 가중치를 확인해서 가장 작은 가중치를 최소 신장 트리에 삽입. (최소 신장 트리에 삽입 시 사이클이 형성되지 않게 삽입) 3번 과정을 반복 한 후 모든 정점이 최소 신장 트리에 연결되면 종료
이해를 돕기 위해 예를 들어 보겠습니다.
위 그래프에서 정점 0 부터 시작해서 하겠습니다. 정점 0 을 최소 신장 트리에 추가합니다. (파란색 선은 인접한 간선을 의미합니다.)
0 에 연결되어 있는 간선 0-1 , 0-5 중 가중치가 가장 작은 간선은 가중치가 8 인 0-1 이므로 1 을 최소 신장 트리에 추가합니다.
0 , 1 에 연결되어 있는 간선 0-5 , 1-2 , 1-6 중 가중치가 가장 작은 간선은 가중치가 10 인 1-6 이므로 6 을 최소 신장 트리에 추가합니다.
0 , 1 , 6 에 연결되어 있는 간선 0-5 , 1-2 , 6-3 , 6-4 중 가중치가 가장 작은 간선은 가중치가 15 인 0-5 이므로 5 를 최소 신장 트리에 추가합니다.
0 , 1 , 5 , 6 에 연결되어 있는 간선 1-2 , 5-4 , 6-3 , 6-4 중 가중치가 가장 작은 간선은 가중치가 17 인 1-2 이므로 2 를 최소 신장 트리에 추가합니다.
0 , 1 , 2 , 5 , 6 에 연결되어 있는 간선 2-3 , 5-4 , 6-3 , 6-4 중 가중치가 가장 작은 간선은 가중치가 21 인 5-4 이므로 4 를 최소 신장 트리에 추가합니다.
0 , 1 , 2 , 4 , 5 , 6 에 연결되어 있는 간선 2-3 , 4-3 , 6-3 , 6-4 중 가중치가 가장 작은 간선은 가중치가 23 인 6-4 이지만 6-4 를 선택하면 사이클이 형성 되므로 최소 신장 트리에 추가하지 않고, 23 다음으로 작은 가중치가 25 인 3 을 최소 신장 트리에 추가합니다.
모든 정점이 최소 신장 트리에 추가되었으므로 종료합니다.
프림 알고리즘 구현
프림 알고리즘에서 문제가 되는 것은 최소 가중치를 찾는 것입니다.
그래프에서 N 개의 정점이 있다면, N 개의 정점을 추가하고 N 개의 정점을 순회해야 하므로, 최소 가중치를 찾기 위해서는 N×N=N^2 을 반복해야 합니다.
이 문제를 해결하기 위해서는 힙(Heap)을 사용합니다. 힙을 사용하면 빠르게 최소 가중치를 찾을 수 있습니다.
최소 신장 트리에서 정점과 인접한 간선을 (가중치, 정점) 으로 힙에 삽입하고, 힙에서 꺼낸 정점과 인접한 정점을 순회하면서 가중치가 최소인 정점을 다시 힙에 추가하면서 힙이 비어 있을 때까지 반복합니다. 사이클 형성 방지를 위해 이미 방문한 정점일 경우 최소 신장 트리에 추가하지 않습니다.
예제 코드에서는 최소 신장 트리를 반환하게 코드를 작성했습니다. 최소 가중치의 합을 반환하는 등 다양하게 응용하면 될 것 같습니다. 다음은 프림 알고리즘을 구현한 예제 코드입니다.
import sys import heapq def prim(start, graphs, weights): mst_graphs = [ [ 0 for _ in range(len(graphs)) ] for _ in range(len(graphs)) ] # 최소 신장 트리 mst_vertices = [-1 for _ in range(len(graphs))] # 최소 신장 트리 연결 정보 (-1로 초기화) mst_weights = [ sys.maxsize for _ in range(len(graphs)) ] # 최소 신장 트리 가중치 정보 (최대 값으로 초기화) visited = set() # 방문 정보 heap = [] # 최소 힙 heapq.heappush(heap, (0, start)) # (가중치, 정점) 쌍으로 힙에 저장 while len(heap) > 0: vertex = heapq.heappop(heap)[1] # 힙에서 최소 가중치 꺼냄 visited.add(vertex) for target, value in enumerate (graphs[vertex]): # 인접한 간선 순회 if target in visited: continue if value == 1 and weights[vertex][target] < mst_weights[target]: heapq.heappush(heap, (weights[vertex][target], target)) mst_weights[target] = weights[vertex][target] mst_vertices[target] = vertex # 최소 신장 트리 생성 weight_sum = 0 for a, b in enumerate(mst_vertices): if b >= 0: mst_graphs[a][b] = 1 mst_graphs[b][a] = 1 weight_sum += mst_weights[a] # 출력용 print(“최소 가중치 합: “, weight_sum) for row in mst_graphs: print(row) return mst_graphs if __name__ == “__main__”: graphs = [ [0, 1, 0, 0, 0, 1, 0], [1, 0, 1, 0, 0, 0, 1], [0, 1, 0, 1, 0, 0, 0], [0, 0, 1, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 1], [1, 0, 0, 0, 1, 0, 0], [0, 1, 0, 1, 1, 0, 0], ] weights = [ [0, 8, 0, 0, 0, 15, 0], [8, 0, 17, 0, 0, 0, 10], [0, 17, 0, 27, 0, 0, 0], [0, 0, 27, 0, 29, 0, 25], [0, 0, 0, 29, 0, 21, 23], [15, 0, 0, 0, 21, 0, 0], [0, 10, 0, 25, 23, 0, 0], ] mst_graphs = prim(0, graphs, weights)
최소 가중치 합: 96 [0, 1, 0, 0, 0, 1, 0] [1, 0, 1, 0, 0, 0, 1] [0, 1, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 1] [0, 0, 0, 0, 0, 1, 0] [1, 0, 0, 0, 1, 0, 0] [0, 1, 0, 1, 0, 0, 0]
크루스칼 알고리즘(Kruskal’s Algorithm)
크루스칼 알고리즘은 그래프 내의 모든 간선의 가중치를 확인하고 가장 작은 가중치부터 확인해서 최소 신장 트리를 만드는 방법입니다. 크루스칼 알고리즘은 탐욕적인(Greedy) 방법을 사용합니다.
크루스칼 알고리즘으로 최소 신장 트리를 만드는 방법은 다음과 같습니다.
그래프 내의 모든 간선의 가중치를 오름차순으로 정렬 오름차순으로 정렬된 가중치를 순회하면서 최소 신장 트리에 삽입 (최소 신장 트리에 삽입 시 사이클이 형성되지 않게 삽입)
크루스칼 알고리즘에서 사이클을 확인하기 위해 분리 집합(Disjoint Set)을 사용합니다. 분리 집합은 다음과 같이 서로 공통된 원소를 갖지 않는 집합을 의미합니다.
최소 신장 트리에서 다음과 같은 집합이 있고 1-2 를 간선으로 연결할 경우, 왼쪽은 서로 다른 집합이기 때문에 1-2 를 연결해도 사이클이 형성 되지 않지만, 오른쪽은 이미 같은 집합에 속해 있기 때문에 1-2 를 연결할 경우 사이클을 형성하게 됩니다. 이렇게 하면 쉽게 사이클을 확인할 수 있습니다.
이해를 돕기 위해 프림 알고리즘에서 사용했던 예제와 동일한 그래프로 예를 들어 보겠습니다.
먼저 그래프 내의 모든 간선을 가중치를 기준으로 오름차순으로 정렬한 후, 각 정점 별로 분리 집합을 만듭니다.
간선 가중치 0-1 8 1-6 10 0-5 15 1-2 17 4-5 21 4-6 23 3-6 25 2-3 27 3-4 29
첫번째로 정렬된 가중치가 8 인 0-1 은 서로 다른 집합이므로 최소 신장 트리에 추가하고 간선으로 연결합니다. 그리고 집합 {0} , {1} 을 합집합 연산을 해서 하나의 분리 집합으로 만듭니다.
다음으로 가중치가 10 인 1-6 은 서로 다른 집합이므로 최소 신장 트리에 추가하고 간선으로 연결합니다. 그리고 집합 {0, 1} , {6} 을 합집합 연산을 해서 하나의 분리 집합으로 만듭니다.
가중치가 15 인 0-5 는 서로 다른 집합이므로 최소 신장 트리에 추가하고 간선으로 연결합니다. 그리고 집합 {0, 1, 6} , {5} 을 합집합 연산을 해서 하나의 분리 집합으로 만듭니다.
가중치가 17 인 1-2 는 서로 다른 집합이므로 최소 신장 트리에 추가하고 간선으로 연결합니다. 그리고 집합 {0, 1, 5, 6} , {7} 을 합집합 연산을 해서 하나의 분리 집합으로 만듭니다.
가중치가 21 인 4-5 는 서로 다른 집합이므로 최소 신장 트리에 추가하고 간선으로 연결합니다. 그리고 집합 {0, 1, 2, 5, 6} , {4} 을 합집합 연산을 해서 하나의 분리 집합으로 만듭니다.
가중치가 23 인 4-6 은 서로 같은 집합에 속해 있으므로 간선을 연결하면 사이클을 형성합니다. 따라서 다음 가중치를 확인합니다.
가중치가 25 인 3-6 은 서로 다른 집합이므로 최소 신장 트리에 추가하고 간선으로 연결합니다. 그리고 집합 {0, 1, 4, 5, 6} , {3} 을 합집합 연산을 해서 하나의 분리 집합으로 만듭니다.
모든 정점이 하나의 집합 안에 포함되었으므로 최소 신장 트리가 만들어졌습니다. 남은 가중치를 확인해보면 모두 사이클을 형성하므로 더 이상 최소 신장 트리에 추가되지 않습니다.
크루스칼 알고리즘 구현
그래프 내의 모든 간선의 가중치를 (가중치, 정점, 정점) 쌍으로 힙에 삽입하고, 힙에서 데이터를 꺼내면서 정점1 , 정점2 가 서로 다른 집합이면 최소 신장 트리를 생성하고 합집합 연산을 수행합니다. 이 과정을 힙이 비어 있을 때까지 반복합니다. 또한 사이클을 확인하기 위해 분리 집합 클래스, 분리 집합 부모 찾기, 합집합 연산 함수를 구현하였습니다.
예제 코드에서는 프림 알고리즘과 마찬가지로 최소 신장 트리를 반환하게 코드를 작성했습니다. 다음은 크루스칼 알고리즘을 구현한 예제 코드입니다.
import sys import heapq # 분리 집합 클래스 class DisjointSet: def __init__(self): self.parent = None # 분리 집합 합집합 연산 def unionset(set1, set2): set2 = findset(set2) set2.parent = set1 # 분리 집합 부모 찾기 def findset(set): while set.parent != None: set = set.parent return set def kruskal(graphs, weights): mst_graphs = [ [ 0 for _ in range(len(graphs)) ] for _ in range(len(graphs)) ] # 최소 신장 트리 vertex_sets = [ DisjointSet() for _ in range(len(graphs))] # 분리 집합 배열 visited = set() # 방문 정보 heap = [] # 최소 힙 for vertex in range(len(graphs)): for target in range(vertex, len(graphs)): if weights[vertex][target] > 0: heapq.heappush(heap, (weights[vertex][target], vertex, target)) # (가중치, 정점1, 정점2) 쌍으로 힙에 저장 weight_sum = 0 while len(heap) > 0: pop = heapq.heappop(heap) w = pop[0] v1 = pop[1] v2 = pop[2] set1 = vertex_sets[v1] set2 = vertex_sets[v2] print(‘{}-{}: {}’.format(v1, v2, w)) if findset(set1) != findset(set2): # 같은 집합이 아닐 경우 unionset(set1, set2) # 최소 신장 트리 생성 mst_graphs[v1][v2] = 1 mst_graphs[v2][v1] = 1 weight_sum += weights[v1][v2] # 출력용 print(“최소 가중치 합: “, weight_sum) for row in mst_graphs: print(row) return mst_graphs if __name__ == “__main__”: graphs = [ [0, 1, 0, 0, 0, 1, 0], [1, 0, 1, 0, 0, 0, 1], [0, 1, 0, 1, 0, 0, 0], [0, 0, 1, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 1], [1, 0, 0, 0, 1, 0, 0], [0, 1, 0, 1, 1, 0, 0] ] weights = [ [0, 8, 0, 0, 0, 15, 0], [8, 0, 17, 0, 0, 0, 10], [0, 17, 0, 27, 0, 0, 0], [0, 0, 27, 0, 29, 0, 25], [0, 0, 0, 29, 0, 21, 23], [15, 0, 0, 0, 21, 0, 0], [0, 10, 0, 25, 23, 0, 0] ] mst_graphs = kruskal(graphs, weights)
0-1: 8 1-6: 10 0-5: 15 1-2: 17 4-5: 21 4-6: 23 3-6: 25 2-3: 27 3-4: 29 최소 가중치 합: 96 [0, 1, 0, 0, 0, 1, 0] [1, 0, 1, 0, 0, 0, 1] [0, 1, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 1] [0, 0, 0, 0, 0, 1, 0] [1, 0, 0, 0, 1, 0, 0] [0, 1, 0, 1, 0, 0, 0]
반응형
최소 신장 트리(Minimum Spanning Tree)
읽기 전
불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
개인적으로 사용해보면서 배운 점을 정리한 글입니다.
신장 트리(Spanning Tree)란?
스패닝 트리라고도 부른다. 모든 임의의 정점이 연결된 그래프인 연결 그래프의 부분 그래프다. 모든 정점이 간선으로 연결되어 있지만 사이클이 존재하지 않는 그래프다.
연결 그래프가 주어졌을 때 생성할 수 있는 신장 트리는 유일하지 않음을 알 수 있다.
최소 신장 트리(Minimum Spanning Tree)란?
최소 비용 신장 트리(Minimum cost Spanning Tree)라고도 부르는 사람들이 있지만 대부분 최소 신장 트리로 사용한다. 그래프의 간선에 가중치 등 값이 부여될 때 이를 가중치 그래프라고 하며 그 그래프가 유향 그래프일 경우 네트워크라 부른다. 가중치가 부여된 그래프의 신장 트리를 구성하는 비용은 신장 트리를 구성하는 모든 가중치의 합이다. 즉, 최소 신장 트리는 신장 트리를 구성하는 간선들의 가중치 합이 가장 작은 신장 트리 이다. 그리고 최소 신장 트리를 구현하는 알고리즘에는 주로 2가지 알고리즘을 소개한다. 따로 자세히 정리할 크루스칼 알고리즘과 프림 알고리즘이다.
MST의 특징
신장 트리들 중 간선의 가중치 합이 최소이다.
n개의 정점을 갖는 그래프에 대해 n – 1 개의 간선만을 사용해야 한다.
사이클이 존재해서는 안된다.
최소 신장 트리는 최단 경로를 보장하지 않는다.
MST 사용 문제 예시
도로, 통신 등 모든 노드를 방문해야 하는 문제들 중 구축 비용이나 소요 시간 등을 최소로 해야하는 문제들에 적용될 수 있다.
MST의 구현 알고리즘
크루스칼 알고리즘 (Kruskal’s Algorithm)
그리디 알고리즘 기반으로 구현한다. MST가 최소 비용의 간선으로 구성되며 사이클을 이루지 않는다는 특성에 기인해 각 단계에서 기존 선택된 간선들과 사이클을 이루지 않는 최소 비용 간선을 선택한다. 선택 시 사이클 형성 여부를 체크하는 로직을 작성해두고 사용해야 한다.
그래프의 간선들을 가중치를 기준으로 오름차순 정렬한다.
정렬된 간선들을 순서대로 탐색하며 사이클을 형성하지 않는 간선을 선택한다.
선택된 간선을 MST 집합에 넣는다. 집합의 원소 개수가 $V – 1$개가 될 때까지 반복한다.
구체적인 구현 방법, 시간 복잡도는 크루스칼 알고리즘(Kruskal’s Algorithm)에 정리하였다.
프림 알고리즘 (Prim’s Algorithm)
그리디 알고리즘 기반으로 구현한다. 다만 크루스칼 알고리즘과 동작 방식은 유사하나 간선 선택을 중심으로 동작했던 크루스칼 알고리즘과는 달리 정점을 기준으로 탐색을 진행한다. 시작 정점에서 출발하여 신장 트리 집합을 단계적으로 확장해나간다.
시작 시 시작 정점만이 MST 집합에 포함된다.
인접한 정점들 중 최소 비용 간선으로 연결된 정점을 MST 집합에 삽입한다. (삽입 시 사이클 형성 여부 체크)
모든 정점이 연결되도록 $V – 1$개의 간선을 갖게될 때까지 반복한다.
구체적인 구현 방법, 시간 복잡도는 프림 알고리즘(Prim’s Algorithm에 정리하였다.
관련 링크
크루스칼 알고리즘(Kruskal’s Algorithm
프림 알고리즘(Prim’s Algorithm
최소 비용 신장트리(MST, Minimum Spanning Tree)란?
728×90
반응형
신장트리
신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 또한 사이클을 포함해서는 안된다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다.
출처 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
출처 : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https%3A%2F%2Fwww.google.com%2F
신장 트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 또한 신장트리는 그래프의 최소 연결 부분 그래프가 된다. 여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다. n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며 (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 트리가 된다.
그렇다면 신장 트리는 어디에 사용될까?
신장트리는 통신 네트워크 구축에 많이 사용된다. 예를들어 n개의 위치를 연결하는 통신 네트워크를 최소의 링크를 이용하여 구축하고자 할 경우, 최소의 링크수는 (n-1)이 되고 따라서 신장 트리들이 가능한 대안이 된다.
출처 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
그러나 각 링크의 구축 비용은 똑같지가 않다. 따라서 단순히 가장 적은 링크만을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다. 즉 간선에 비용을 붙여서 링크의 구축 비용까지를 고려하여 최소 비용의 신장 트리를 선택할 필요가 있다. 이것이 바로 최소 비용 신장 트리의 개념이다.
최소 비용 신장 트리
통신망, 도로망, 유통망 등은 간선에 가중치가 부여된 네트워크로 표현될 수 있다. 가중치는 길이, 구축 비용, 전송 시간 등을 나타낸다. 이러한 도로망, 통신망, 유통망을 가장 적은 비용으로 구축하고자 한다면, 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 최소 비용 신장 트리(MST: minimum spanning tree)가 필요하게 된다.
최소 비용 신장 트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다.
출처 : https://kingpodo.tistory.com/49 출처 : https://kingpodo.tistory.com/49
최소 비용 신장 트리를 구하는 방법으로는 Kruskal과 Prim이 제안한 알고리즘이 대표적으로 사용되고 있으며, 이 알고리즘들은 최소 비용 신장 트리가 간선의 가중치의 합이 최소이어야 하고, 반드시 (n-1)개의 간선만 사용해야 하며, 사이클이 포함되어서는 안 된다는 조건들을 적절히 이용하고 있다.
반응형
SuperM :: [AL] 7. 최소 비용 신장 트리(MST) 알고리즘
그래프 내의 모든 정점을 포함하는 트리
Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
탐욕적인 방법(Greedy) 을 이용하여 가중치 그래프의 모든 정점을 최소 비용으로 연결하는 방법
정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다
그래프의 간선들을 가중치의 오름차순으로 정렬한다
주의할점
시간 복잡도
Union-Find 알고리즘을 이용하면 Kruskal 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다. 즉, 간선 N개를 효율적으로 정렬한다면 O(N logN) 의 시간 복잡도를 갖는다.
시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법
위의 과정을 트리가 N-1 개의 간선을 가질 때까지 반복한다
앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다
시작 단계에서는 시작 정점만이 MST 에 포함된다
시간 복잡도
1차 반복문이 정점의 수인 n만큼 반복하고, 2차 반복문이 n번 반복된다. 따라서 Prim 알고리즘은 O(N^2) 의 시간 복잡도를 갖는다. 만약, 우선순위 큐를 사용한다면 O(E logV) 의 시간 복잡도를 갖는다.
키워드에 대한 정보 최소 비용 신장 트리
다음은 Bing에서 최소 비용 신장 트리 주제에 대한 검색 결과입니다. 필요한 경우 더 읽을 수 있습니다.
이 기사는 인터넷의 다양한 출처에서 편집되었습니다. 이 기사가 유용했기를 바랍니다. 이 기사가 유용하다고 생각되면 공유하십시오. 매우 감사합니다!
사람들이 주제에 대해 자주 검색하는 키워드 크루스칼 알고리즘 – 최소 신장 트리
- Kruskal
- algorithm
- minimum spanning tree
- MST
- 크루스칼
- 알고리즘
- 최소 신장 트리
- 자료구조
크루스칼 #알고리즘 #- #최소 #신장 #트리
YouTube에서 최소 비용 신장 트리 주제의 다른 동영상 보기
주제에 대한 기사를 시청해 주셔서 감사합니다 크루스칼 알고리즘 – 최소 신장 트리 | 최소 비용 신장 트리, 이 기사가 유용하다고 생각되면 공유하십시오, 매우 감사합니다.
