#6. 프림 알고리즘

최소 신장 트리

 

1.신장 트리란 특정한 그래프에서 모든 정점을 포함하는 그래프이다.

2.최소 신장 트리는 스패닝 트리 중에서 간선의 가중치 합이 가장 작은 트리를 의미한다.

 

 

->모든 노드를 연결할때, 가장 적은 간선만 선택 할 수 있도록 한다.

 

 

 

프림 알고리즘

 

1.그래프에서 정점 하나를 선택해 트리T에 포함시킨다.

2.T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 가중치가 가장 작은 간선을 찾는다.

3.해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킨다.

4.반복한다.

 

->프림 알고리즘은 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 구현할 수 있다.

 

코드예시

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define NODE_MAX  1001   
#define EDGE_MAX  200001  //간선최대10만개 ,양방향 간선이므로 20만개

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);
	}
	//프림 알고리즘 시작
	long long res = 0;
	Edge* start = (Edge*)malloc(sizeof(Edge));
	start->cost = 0; start->node = 1; push(pq, start);
	for (int i = 1; i <= n; i++) {
		int nextNode = -1, nextCost = INT_MAX;
		while (1) {
			Edge* now = pop(pq);
			if (now == NULL) break;
			nextNode = now->node;
			if (!d[nextNode]) {
				nextCost = now->cost; break;
			}
		}
		if (nextCost == INT_MAX) printf("연결 그래프가 아닙니다.\n");
		res += nextCost;
		d[nextNode] = 1;
		Node* cur = adj[nextNode];
		while(cur != NULL) { push(pq, cur->data); cur = cur->next; }
	}
	printf("%lld\n", res);
	system("pause");
}

 

 

결과값

 

3 3 노드3개, 간선3개
1 2 8    1->2로갈때, 8비용소모
1 3 9
2 3 10

17

 

라 한다면,

1,2,3을 모두 연결시킬 수있는 최소값은

8과9

8+9= 17

따라서 결과값이 17이 나온다는걸 알 수있다.

 

 

ps.점점,, 코드가 복잡해지니 이해하는데 시간이 지수함수꼴로 늘어나는것 같다..  부디.. 지수함수가아닌,  저항받는 생장곡선 모양이길,,,ㅋㅋㅋㅋㅋ