프림 알고리즘

프림 알고리즘 (Prim’s Algorithm)

개요

프림 알고리즘

• 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 신장트리 를 찾는 알고리즘이다

  최소 신장트리 (Minimum Spanning Tree, MST)

• 신장 트리 중에서 간선의 가중치 합이 가장 작은 트리

  신장트리

  • 특정한 그래프에서 모든 정점을 포함하는 그래프

프림 알고리즘

0. 처음에 트리는 비어있다고 가정한다.
1. 그래프에서 정점 하나를 선택하여 트리에 포함시킨다.
2. 1에서 포함된 정점과 인접한 노드의 간선 중에서 가중치가 가장 작은 간선을 찾아 포함시킨다.
3. 2번을 모든 노드가 포함될 때까지 반복한다.

동작 과정

이미지 삽입 예정

구현

모든 코드 확인하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define NODE_MAX 1001
#define EDGE_MAX 200001 // 양방향 간선이므로 100,000개

// 구조체 정의
typedef struct {
int cost;
int node;
} Edge;

// 데이터 위치 변환을 위한 함수 구현
void swap(Edge *a, Edge *b) {
Edge temp;
temp.cost = a->cost;
temp.node = a->node;
a->cost = b->cost;
a->node = b->node;
b->cost = temp.cost;
b->node = temp.node;
}

// 우선순위 큐 정의
typedef struct {
Edge *heap[EDGE_MAX];
int count;
} priorityQueue;

// 데이터 삽입 함수
void push(priorityQueue *pq, Edge *edge) {
    if (pq->count >= EDGE_MAX) return;
    pq->heap[pq->count] = edge;
    int now = pq->count;
    int parent = (pq->count - 1) / 2;
    
    // 새 원소를 삽입한 이후에 상향식으로 힙을 구성한다.
    while (now > 0 && pq->heap[now]->cost < pq->heap[parent]->cost) {
        swap(pq->heap[now], pq->heap[parent]);
        now = parent;
        parent = (parent - 1) / 2;
    }
    pq->count++;
}

// 데이터 추출함수 구현
Edge* pop(priorityQueue *pq) {
if (pq->count <= 0) return NULL;
Edge *res = pq->heap[0];
pq->count--;
pq->heap[0] = pq->heap[pq->count];
int now = 0, leftChild = 1, rightChild = 2;
int target = now;

// 새 원소를 추출한 이후에 하향식으로 힙을 구성합니다.
while (leftChild < pq->count) {
    if (pq->heap[target]->cost > pq->heap[leftChild]->cost) target = leftChild;
    if (pq->heap[target]->cost > pq->heap[rightChild]->cost && rightChild < pq->count) target = rightChild;
    if (target == now) break; // 더 이상 내려가지 않아도 될 때 종료
    else {
        swap(pq->heap[now], pq->heap[target]);
        now = target;
        leftChild = now * 2 + 1;
        rightChild = now * 2 + 2;
    }
  }
  return res;
}

// 데이터 연결리스트 구현
typedef struct Node {
Edge *data;
struct Node *next;
} Node;

Node** adj;
int d[NODE_MAX];

// 노드 추가를 위한 함수
void addNode(Node** target, int index, Edge* edge) {
    if (target[index] == NULL) {
        target[index] = (Node*)malloc(sizeof(Node));
        target[index]->data = edge;
        target[index]->next = NULL;
    }
    else {
        Node* node = (Node*)malloc(sizeof(Node));
        node->data = edge;
        node->next = target[index];
        target[index] = node;
    }
}

// 알고리즘 실행
int main(void) {
    int n, m;
    scanf("%d %d", &n, &m);
    // 큐 초기화
    adj = (Node**)malloc(sizeof(Node*) * (n + 1));
    for (int i = 1; i <= n; i++) {
    adj[i] = NULL;
}
priorityQueue *pq;
pq = (priorityQueue*)malloc(sizeof(priorityQueue));
pq->count = 0;
for (int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    Edge *edge1 = (Edge*)malloc(sizeof(Edge));
    edge1->node = b;
    edge1->cost = c;
    addNode(adj, a, edge1);
    Edge *edge2 = (Edge*)malloc(sizeof(Edge));
    edge2->node = a;
    edge2->cost = c;
    addNode(adj, b, edge2);
}