Recent Posts
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- ML
- algorithm
- 3d
- 알고리즘
- nlp
- cs
- nerf
- Torch
- Front
- FGVC
- SSL
- 머신러닝
- Depth estimation
- math
- PRML
- REACT
- CV
- Python
- classification
- 자료구조
- 딥러닝
- clean code
- computervision
- GAN
- dl
- pytorch
- FineGrained
- Meta Learning
- Vision
- web
- Today
- Total
KalelPark's LAB
[ Algorithm ] Prim's Algorithm 이란? 본문
Prim's Algorithm 이란?
최소 비용 신장 트리를 구하는 알고리즘 중 하나로, 가중치를 가지는 그래프에서, 가장 작은 가중치를 가지는 간선(Edge)를 시작으로
인접한 정점과 연결된 Edge들 중에서, 가장 작은 가중치를 가지는 간선(Edge)들을 선택하는 방식이다.
Prim 알고리즘은, 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복됩니다. 그러므로 시간복잡도는 O(N*N) 입니다.
Prim's Algorithm 동작
1. 시작 단계에서, 시작 정점만을 MST(최소 비용 신장 트리) 집합에 포함합니다.
2. MST(최소 비용 신장 트리) 집합에 포함된 정점들에 인접한 정점과 최소 간선으로 연결할 수 있는 정점을 집합에 넣어줍니다.
3. 이러한 과정을 간선이 N-1개, 즉 Cycle이 발생시키지 않게 반복합니다.
Prim's Algorithm의 구체적인 원리
1. 정점(Vertex) 선택을 기반으로 하는 알고리즘
2. 이전 단계에서 만들어진 신장 트리를 확장
Prim Algorithm Pseudo code
T = {}
TV = {0};
while (T는 n-1개의 edge보다, 적게 edge를 포함하고 있어야 합니다.)
{
만약 Vertex가 TV에 포함되고, 인접한 Vertex를 TV에 포함하고 있지 않음을 가정하자.
if (edge가 없다면) {
break;
}
add v to TV; // 인접한 Vertex를 추가합니다.
add (u, v) to T; // 최소의 신장트리를 가진 edge도 추가합니다.
}
if (T가 n-1개의 edge보다 적게 포함하고 있다면,) {
print("no spanning Tree");
}
Prim's Algorithm code with C/C++
// Prim's Algorithm in C
#include<stdio.h>
#include<stdbool.h>
#define INF 9999999
#define V 5
int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}};
int main() {
int no_edge; // number of edge
int selected[V];
memset(selected, false, sizeof(selected));
no_edge = 0;
selected[0] = true;
int x; // row number
int y; // col number
printf("Edge : Weight\n");
while (no_edge < V - 1) {
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j]) {
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
printf("%d - %d : %d\n", x, y, G[x][y]);
selected[y] = true;
no_edge++;
}
return 0;
}
Author's GitHub
'Study > Algorithm' 카테고리의 다른 글
[ Algorithm ] Heap & Priority Queue? (0) | 2022.12.04 |
---|---|
[ Algorithm ] Dijkstra's Algorithm? (0) | 2022.11.30 |
[ Algorithm ] Insertion sort, Bubble sort, Selection sort? (0) | 2022.11.30 |
[ Algorithm ] Bellman-Ford Algorithm이란? (2) | 2022.11.29 |
[ Algorithm ] Sollin's Algorithm 이란? (0) | 2022.11.28 |
Comments