Problem Solving/Algorithm, DS
[알고리즘] 최소신장트리(MST)와 프림, 크루스칼 알고리즘 + 백준1197번
📂 최소신장트리 (Minimum Spanning Tree) 신장트리 : 그래프 G의 노드 V를 모두 포함하는 E에 속하는 에지를 사용해 만든 트리 최소신장트리 : 가중그래프 G의 신장트리 중에서 트리에 속한 가중치의 합을 최소로 하는 신장 트리 최소신장트리를 만드는 2가지 방법 : Prim's Algorithm, Kruskal's Algorithm 최소신장트리의 간선 개수는 (정점의 수 - 1) 이다. (N-1개의 간선으로 연결되어 있으면 필연적으로 모든 노드가 연결된다) 간선들의 가중치 합이 최소인 경우 서로 다른 최소신장트리가 하나 이상 있을 수 있다. 📂 크루스칼 알고리즘 (Kruskal's Algorithm) 가중치가 가장 작은 간선부터 차례대로 간선을 선택해 나가는 방법으로, 탐욕적(greedy..
