KoreanFoodie's Study
기술면접 알고리즘 [Graph] : 프림 (Prim - Minimum Spanning Tree) 본문
Data Structures, Algorithm/GeeksForGeeks
기술면접 알고리즘 [Graph] : 프림 (Prim - Minimum Spanning Tree)
GoldGiver 2022. 1. 21. 16:45
기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.
각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.
프림 알고리즘 (최소 신장 트리)
프림 알고리즘은 Greedy 한 방식으로 Vertex 들을 이어 최소 신장 트리를 만든다. 구체적으로는 :
해당 정점의 집합 대해, 연결된 {간선, 정점} 쌍을 정점 가중치 기준으로 우선순위 큐에 넣는다. 그리고 가중치가 기존의 가중치보다 작으면서, 도착 지점이 미방문인 노드를 집합에 넣고, 추가된 노드의 {간선, 정점} 쌍들을 다시 우선순위 큐에 넣는다. 해당 작업을 모든 Vertex 를 순회할 때까지 반복하면 된다.
시간 복잡도는 (모든 정점에 대해서) * (우선순위 큐에서 정점 추출) + (모든 간선에 대해서) * (값 변경 및 우선순위 큐에 삽입) 이 되므로, O( V * log(V) + E * log(E) ) 가 되어, 최종적으로 O( E * log(E) ) 가 된다. (E 는 최대 V^2 이므로)
#include <iostream>
#include <queue>
#include <vector>
#define V 5
#define INF 1000000
struct myP {
int v;
int dist;
};
struct compare {
bool operator()(myP a, myP b) {
return a.dist > b.dist;
}
};
void primMST(int (*graph)[V]) {
std::priority_queue<myP, std::vector<myP>, compare> q;
int dist[V];
std::fill(dist, dist+V, INF);
int parent[V];
std::fill(parent, parent+V, -1);
// pick node 0 as starting point
dist[0] = 0;
q.push({0, 0});
bool visited[V];
myP cur;
while (!q.empty()) {
cur = q.top();
q.pop();
int c_v = cur.v;
int c_d = cur.dist;
// relaxation
visited[c_v] = true;
dist[c_v] = c_d;
for (int i = 0; i < V; ++i) {
if (graph[c_v][i] && !visited[i] && dist[i] > c_d + graph[c_v][i]) {
dist[i] = c_d + graph[c_v][i];
parent[i] = c_v;
q.push({i, dist[i]});
}
}
}
std::cout << "Edge Weight" << std::endl;
for (int i = 1; i < V; ++i) {
std::cout << parent[i] << " - " << i << "\t" << graph[parent[i]][i] << std::endl;
}
}
// Driver code
int main()
{
/* Let us create the following graph
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 1, 11 },
{ 0, 3, 0, 0, 7 },
{ 6, 1, 0, 0, 9 },
{ 0, 11, 7, 9, 0 } };
// Print the solution
primMST(graph);
return 0;
}
'Data Structures, Algorithm > GeeksForGeeks' 카테고리의 다른 글
기술면접 알고리즘 [Graph] : 위상정렬 (Topological Sort) (0) | 2022.01.21 |
---|---|
기술면접 알고리즘 [Graph] : 크루스칼 (Kruskal - Minimum Spanning Tree) (0) | 2022.01.21 |
기술면접 알고리즘 [Graph] : 유니온 파인드 / 사이클 찾기 (Union-Find / Cycle Detection) (0) | 2022.01.21 |
기술면접 알고리즘 [Graph] : Floyd-Warshall (플로이드 와샬 - 최단거리 쌍) (0) | 2022.01.21 |
기술면접 알고리즘 [Graph] : 다익스트라 (최단 경로) (0) | 2022.01.21 |
Comments