프림

[C++] 개인적인 (MST 알고리즘) 크루스칼 & 프림 구현

사용할 데이터는 다음과 같다. 결과) 17 1 2 2 2 6 7 3 2 3 3 6 8 4 3 5 4 2 3 4 1 1 5 1 4 5 4 9 공통으로 쓰여짐 // 간선 개수 const int edge = 9; struct sNode { public: int from = 0, to = 0, weight = 0; /*sNode() = default; sNode(int from, int to, int weight) : from(from), to(to), weight(weight) { }*/ bool operator(const sNode& ref) const { return weight > ref.weight; } bool operator==(const sNode& ref) const { return from =..

C++ MST 크루스칼 + 프림 알고리즘 코드

이미지 출처) Minimum Spanning Tree - Kruskal - Algorithms for Competitive Programming (cp-algorithms.com) 정답) 1 + 2 + 3 + 4 + 7 = 17 순회하는 순서가 추가되는 노드 순서에 따라 상이할 수 있음. 입력 데이터 From 1 To 2 Value 2 Edge형 구조체에 담음, int from, to, val; 9 1 2 2 1 4 1 1 5 4 2 4 3 2 3 3 2 6 7 3 6 8 4 3 5 5 4 9 0 0 0 크루스칼 알고리즘 핵심 포인트) 모든 부모 노드들을 포함하고 있을 int형 벡터와 Edge형 벡터, 한 방향만 연결. #include #include #include using namespace std;..

C++ 프림(Prim) 알고리즘으로 MST 찾기

1. 프림(Prim) 알고리즘이란? 최소신장트리(MST, Minimum Spanning Tree) 를 찾기 위한 대표적인 알고리즘이다. 여기에서 최소신장트리란, 아래와 같이 모든 노드를 연결하는 부분 그래프 중, 가장 비용이 적은 것이다. 하늘색으로 표시한 경로가 최소신장트리이다. 여기에서 최소신장트리의 길이는 (4 + 8 + 16 + 20) = 48다. 최소신장트리를 찾는 알고리즘은 크루스칼(Kruskal) 과 프림(Prim) 이 대표적이다. 2. 동작원리 프림 알고리즘에서는 MST의 후보가 될 간선을 담을 우선순위 큐가 필요하다. 우선순위 큐는 최소의 비용을 가지는 경로가 우선순위를 갖게 한다. (보통 Min Heap을 이용해서 구현한다.) 가장 먼저, 그래프에서 아무 노드나 선택하므로 가장 번호가 ..