[C] Prim Alogrithm

1. 신장트리 (Spanning Tree)

: n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 이루어진 트리
: 사이클 발생하면 안됨
<=> 사이클 없이 모든 정점 포함하는 트리
 

1-1. 최소 비용 신장 트리 (MST, Minimum cost Spanning Tree)

: 무방향 가중치 그래프에서 신장 트리 구성하는 간선들의 가중치 합이 최소인 신장트리
ex) Kruskal Algorithm, Prim Algorithm
 

2. Prim Algorithm

: 우선순위 큐를 이용하는 알고리즘
: 간선을 정렬하지않고 하나의 정점에서 트리를 확장해나가는 방법
 

2-1. 동작방식

1. 그래프 G에서 시작 정점 선택 ( 대부분의 경우 1로 설정)
2. 선택한 정점에 부속된 모든 간선 중 가장 낮은 간선 연결하여 트리 확장
3. 이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중 가장 낮은 간선 삽입 => 우선순위 큐 이용
   (단, 사이클 형성하는 간선을 삽입할 수 없으므로 그 다음으로 가중치 낮은 간선 pick)
4. 그래프 G에 간선이 n-1개 삽입될 때까지 3번 과정 반복
5. 그래프 G의 간선이 n-1개가 되면 최소 비용 신장 트리 완성

2-2. 구현

1. 임의의 정점 선택해 최소 신장 트리에 추가하고 해당 정점과 연결된 모든 간선을 우선순위 큐에 추가(초기설정)
2. 우선순위 큐에서 비용이 가장 적은 간선 선택
3. 이때 해당 간선이 최소 신장 트리에 포함된 두 정점을 연결한다면(Union-find 알고리즘) 아무것도 하지않고 넘어감
   -> 해당 간선이 최소 신장 트리에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면 해당 간선과 정점 v을 최소 신장 트리에 추가 후 정점 v와 최소 신장 트리에 포함되지 않는 정점 연결(visited 배열 이용)하는 모든 간선 우선순위 큐에 추가 
4. 최소 신장 트리에 v-1개의 간선 추가될 때까지 2~3번 과정 반복

=> 프림 알고리즘에 사용되는 알고리즘

• 우선순위 큐
• 그래프
• Union-find

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

#define MAX_VERTEX 10
#define MAX_EDGE 100

typedef struct _TREE_NODE_ {
	int data;
	int distance;
	struct _TREE_NODE_* link;
}TREE_NODE;

typedef struct _GRAPH_TYPE_ {
	TREE_NODE* head[MAX_VERTEX];
	int nVertex; //정점의 갯수
	int nEdge; //간선의 갯수
}GRAPH_TYPE;



///////////////////////////////

typedef struct _EDGE_ {
	int v1;
	int v2;
	int distance;
}EDGE;

typedef struct _HEAP_TREE_ {
	EDGE* heap[MAX_EDGE];
	int nEdge; //간선의 갯수
}HEAP_TREE;


GRAPH_TYPE* MakeGraph() {
	GRAPH_TYPE* graph = (GRAPH_TYPE*)calloc(1, sizeof(GRAPH_TYPE));
	assert(graph != NULL);

	return graph;
}

void insert_heap_node(HEAP_TREE* tr, EDGE * edgeinfo) {
	if (tr->nEdge == MAX_EDGE) {
		printf("더이상 힙트리에 간선노드를 추가할 수 없습니다\n");
		return;
	}
	tr->nEdge++;
	tr->heap[tr->nEdge] = edgeinfo;

	int idx = tr->nEdge; //현재 삽입된 노드의 번호
	while (idx != 1 && tr->heap[idx / 2]->distance > edgeinfo->distance) {
		EDGE* temp = tr->heap[idx / 2];
		tr->heap[idx / 2] = tr->heap[idx];
		tr->heap[idx] = temp;
		idx /= 2;
	}
}

EDGE * delete_heap_node(HEAP_TREE* tr) {
	if (tr->nEdge == 0) {
		printf("힙트리에 노드가 존재하지않습니다\n");
		return;
	}
	EDGE* delNode = tr->heap[1];
	tr->heap[1] = tr->heap[tr->nEdge];
	tr->nEdge--;

	int idx = 1;
	while (idx * 2 <= tr->nEdge && tr->heap[idx]->distance > tr->heap[idx * 2]->distance) {
		int child = idx * 2;
		if (tr->heap[child]->distance > tr->heap[child + 1]->distance) {
			child++;
		}
		EDGE* temp = tr->heap[idx];
		tr->heap[idx] = tr->heap[child];
		tr->heap[child] = temp;

		idx = child;
	}

	return delNode;
}

//힙트리에 삽입하는 연산
void insert_edge(HEAP_TREE * tr,GRAPH_TYPE* graph, int v1, int v2, int distance) {
	EDGE* heap_node = (EDGE*)calloc(1, sizeof(heap_node));
	assert(heap_node != NULL);
	heap_node->v1 = v1;
	heap_node->v2 = v2;
	heap_node->distance = distance;

	insert_heap_node(tr, heap_node);
}

//연결리스트 기반 그래프에서 노드 삽입
void insert_node(GRAPH_TYPE* graph, int v1, int v2, int distance) {
	graph->nEdge++;
	if (graph->nEdge == MAX_EDGE) {
		printf("더이상 추가할 수 없습니다\n");
		return;
	}
	
	TREE_NODE* newNode = (TREE_NODE*)calloc(1, sizeof(TREE_NODE));
	assert(newNode != NULL);
	newNode->data = v2;
	newNode->distance = distance;

	//비어있는 경우
	if (graph->head[v1] == NULL) {
		graph->head[v1] = newNode;
	}
	else {
		//가장 작은 값 삽입하는 경우
		if (graph->head[v1]->data > v2) {
			newNode->link = graph->head[v1];
			graph->head[v1] = newNode;
		}
		
		TREE_NODE* curNode = graph->head[v1];
		TREE_NODE* preNode = curNode;
		curNode = curNode->link;

		while (curNode != NULL) {
			if (curNode->data > v2) {
				break;
			}
			else {
				preNode = curNode;
				curNode = curNode->link;
			}
		}
		//가장 큰 값 삽입하는 경우
		if (curNode == NULL) {
			preNode->link = newNode;
		}
		//일반적인 경우
		else {
			newNode->link = preNode->link;
			preNode->link = newNode;
		}
	}

	
}

int getParent(int * parent, int node)
{
	if (parent[node] == node) {
		return node;
	}
	else {
		return parent[node] = getParent(parent, parent[node]);
	}
}

int Union(int* parent, int v1, int v2) {
	v1 = getParent(parent, v1);
	v2 = getParent(parent, v2);
	if (v1 < v2) {
		parent[v2] = v1;
	}
	else {
		parent[v1] = v2;
	}
}

void print_graph(GRAPH_TYPE* graph) {
	
	for (int i = 1; i <= graph->nVertex; i++) {
		printf("정점 %d의 인접 리스트 ", i);
		TREE_NODE* curNode = graph->head[i];
		while (curNode != NULL) {
			printf("-> %d ", curNode->data);
			curNode = curNode->link;
		}
		printf("\n");
	}
}

void Prim_Algorithm(GRAPH_TYPE* graph, HEAP_TREE* heap, int* parent, bool* visited, int start) {

	visited[start] = true;
	
	//맨 처음에
	TREE_NODE* curNode = graph->head[start];
	while (curNode != NULL) {
		insert_edge(heap, graph, start, curNode->data, curNode->distance);
		curNode = curNode->link;
	}

	int res = 0;

	while (res != graph->nVertex - 1) {
		EDGE* delNode = delete_heap_node(heap);
		int now = delNode->v2;
		if (getParent(parent, delNode->v1) == getParent(parent, delNode->v2)) { 
			continue;
		}
		else {
			printf("간선 (%c, %c) %d 선택\n", (delNode->v1) - 1 + 'A', (delNode->v2) - 1 + 'A', delNode->distance);
			Union(parent, delNode->v1, delNode->v2);
			res++;
			if (res == graph->nVertex - 1) {
				printf("\n최소 신장 트리를 완성하였습니다\n");
				return;
			}
		}

		TREE_NODE* curNode = graph->head[now];
		while (curNode != NULL) {
			if (visited[curNode->data] == false) {
				insert_edge(heap, graph, now, curNode->data, curNode->distance);
			}
			curNode = curNode->link;
		}

	}
}


int main() {

	GRAPH_TYPE* graph = MakeGraph();
	HEAP_TREE* heap = (HEAP_TREE*)calloc(1, sizeof(HEAP_TREE));
	assert(heap != NULL);

	int res = 0; //그래프 형성했는지 여부 알 수 있는 간선의 총갯수
	
	insert_node(graph, 1, 2, 3);
	insert_node(graph, 1, 3, 17);
	insert_node(graph, 1, 4, 6);
	insert_node(graph, 2, 1, 3);
	insert_node(graph, 2, 4, 5);
	insert_node(graph, 2, 7, 12);
	insert_node(graph, 3, 1, 17);
	insert_node(graph, 3, 5, 10);
	insert_node(graph, 3, 6, 8);
	insert_node(graph, 4, 1, 6);
	insert_node(graph, 4, 2, 5);
	insert_node(graph, 4, 5, 9);
	insert_node(graph, 5, 3, 10);
	insert_node(graph, 5, 4, 9);
	insert_node(graph, 5, 6, 4);
	insert_node(graph, 5, 7, 2);
	insert_node(graph, 6, 3, 8);
	insert_node(graph, 6, 5, 4);
	insert_node(graph, 6, 7, 14);
	insert_node(graph, 7, 2, 12);
	insert_node(graph, 7, 5, 2);
	insert_node(graph, 7, 6, 14);

	graph->nVertex = 7;
	print_graph(graph);

	

	int* parent = (int*)calloc(graph->nVertex + 1, sizeof(int));
	assert(parent != NULL);

	bool* visited = (bool*)calloc(graph->nVertex + 1, sizeof(bool));
	assert(visited != NULL);


	for (int i = 1; i <= graph->nVertex + 1; i++) {
		parent[i] = i;
	}

	printf("\n");
	Prim_Algorithm(graph, heap, parent, visited, 1);

	getchar();
	return 0;
}