[C] Prim Algorithm 코드 보완

2023.10.06 - [C/알고리즘] - [C] Prim Alogrithm

[C] Prim Alogrithm

 

PriorityQueue.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#define MAX_HEAP_SIZE 100


typedef struct _HEAP_NODE_ {
	int start;
	int end;
	int distance;
}HEAP_NODE;

typedef struct _HEAP_TREE_ {
	int n;
	HEAP_NODE* heap[MAX_HEAP_SIZE];
}HEAP_TREE;


void insertHeapNode(HEAP_TREE* tr, int start, int end, int distance);
HEAP_NODE* deleteHeapNode(HEAP_TREE* tr);​

 

PriorityQueue.c

#include "PriorityQueue.h"
void insertHeapNode(HEAP_TREE* tr, int start, int end, int distance) {
	if (tr->n >= MAX_HEAP_SIZE) {
		printf("더이상 힙트리에 노드를 삽입할 수 없습니다\n");
		return;
	}

	HEAP_NODE* newNode = (HEAP_NODE*)calloc(1, sizeof(HEAP_NODE));
	assert(newNode != NULL);
	newNode->start = start;
	newNode->end = end;
	newNode->distance = distance;

	tr->heap[++(tr->n)] = newNode;
	int idx = tr->n;
	while (idx != 1 && tr->heap[idx]->distance < tr->heap[idx / 2]->distance) {
		HEAP_NODE* temp = tr->heap[idx];
		tr->heap[idx] = tr->heap[idx / 2];
		tr->heap[idx / 2] = temp;
		idx /= 2;
	}
}

HEAP_NODE* deleteHeapNode(HEAP_TREE* tr) {
	if (tr->n == 0) {
		printf("공백 힙트리이기에 꺼낼 노드가 존재하지 않습니다\n");
		return;
	}
	HEAP_NODE* delNode = tr->heap[1];
	tr->heap[1] = tr->heap[tr->n];
	tr->n--;
	int idx = 1;
	while (idx * 2 <= tr->n && tr->heap[idx]->distance > tr->heap[idx * 2]->distance) {
		int child = idx * 2;
		if (tr->heap[child]->distance > tr->heap[child + 1]->distance) {
			child++;
		}
		HEAP_NODE* temp = tr->heap[child];
		tr->heap[child] = tr->heap[idx];
		tr->heap[idx] = temp;
		idx = child;
	}

	return delNode;
}​

 

Prim.c

#include "PriorityQueue.h"
#define MAX_VERTEX 10

typedef struct GRAPH_NODE {
	int vertex;
	int weight;
	struct GRAPH_NODE* link;
}NODE;

typedef struct {
	NODE* head[MAX_VERTEX];
	int nVertex;
}GRAPH;

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

int isCycle(int* parent, int x, int y) {
	x = getParent(parent, x);
	y = getParent(parent, y);
	if (x == y) {
		return 1;
	}
	else {
		return 0;
	}
}

void unionParent(int* parent, int x, int y) {
	x = getParent(parent, x);
	y = getParent(parent, y);
	if (x < y) {
		parent[y] = x;
	}
	else {
		parent[x] = y;
	}
}

void insertGraphNode(GRAPH * g, int u,int v, int w){
	if (u >= g->nVertex || v >= g->nVertex) {
		printf("해당 정점은 존재하지 않습니다\n");
		return;
	}
	NODE* newNode = (NODE*)calloc(1, sizeof(NODE));
	newNode->vertex = v;
	newNode->weight = w;
	NODE* curNode = g->head[u];
	NODE* preNode = g->head[u];
	if (curNode == NULL) {
		g->head[u] = newNode;
		return;
	}
	else {
		if (curNode->vertex > v) {
			newNode->link = curNode;
			g->head[u] = newNode;
			return;
		}
		else {
			curNode = curNode->link;
			while (curNode != NULL) {
				if (curNode->vertex > v) {
					break;
				}
				else {
					preNode = curNode;
					curNode = curNode->link;
				}
			}
			newNode->link = preNode->link;
			preNode->link = newNode;
		}
	}
}

void insertVertex(GRAPH* g, int v) {
	if (g->nVertex >= MAX_VERTEX) {
		printf("더이상 정점을 삽입할 수 없습니다\n");
		return;
	}
	else {
		g->nVertex++;
	}
}

void printGraph(GRAPH* g) {
	printf("\n================Print Graph==============\n");
	for (int i = 0; i < g->nVertex; i++) {
		printf("\n정점 %c의 인접 리스트 ", i+'A');
		NODE* cur = g->head[i];
		while (cur != NULL) {
			printf("-> %c", (cur->vertex) + 'A');
			cur = cur->link;
		}
		printf("\n");

	}
}


int PrimAlgorithm(GRAPH* g, int start) {
	printf("\n=================Prim Algorithm 수행===============\n");
	int totalEdge = 0;
	int cost = 0;
	int* parent = (int*)calloc(g->nVertex, sizeof(int));
	assert(parent != NULL);
	for (int i = 0; i < g->nVertex; i++) {
		parent[i] = i;
	}
	bool* visited = (bool*)calloc(g->nVertex, sizeof(bool));
	assert(visited != NULL);

	visited[start] = true;
	HEAP_TREE* tr = (HEAP_TREE*)calloc(1, sizeof(HEAP_TREE));
	assert(tr != NULL);
	//init단계
	NODE* curNode = g->head[start];
	while (curNode) {
		insertHeapNode(tr, start, curNode->vertex, curNode->weight);
		curNode = curNode->link;
	}

	while (totalEdge != g->nVertex-1) {
		HEAP_NODE* now = deleteHeapNode(tr);
		if (visited[now->end] == true || isCycle(parent, now->start, now->end)) {
			continue;
		}
		//방문하지않고 사이클이 발생하지 않는 노드
		visited[now->end] = true;
		unionParent(parent, now->start, now->end);
		cost += (now->distance);
		printf("간선 (%c, %c) %d 선택\n", (now->start) + 'A', (now->end) + 'A', now->distance);
		totalEdge++;
		NODE* p = g->head[now->end];
		while (p != NULL) {
			if (visited[p->vertex] == false) {
				insertHeapNode(tr, now->end, p->vertex, p->weight);
			}
			p = p->link;
		}
	}

	if (totalEdge == g->nVertex - 1) {
		printf("\nComplete Minimum spanning tree with Prim Algorithm ");
		return cost;
	}
}


int main() {
	GRAPH* g = (GRAPH*)calloc(1, sizeof(GRAPH));
	assert(g != NULL);
	for (int i = 0; i < 7; i++) {
		insertVertex(g, i);
	}

	insertGraphNode(g, 0, 1, 3);
	insertGraphNode(g, 0, 2, 17);
	insertGraphNode(g, 0, 3, 6);
	insertGraphNode(g, 1, 0, 3);
	insertGraphNode(g, 1, 3, 5);
	insertGraphNode(g, 2, 0, 17);
	insertGraphNode(g, 2 , 4, 10);
	insertGraphNode(g, 2, 5, 8);
	insertGraphNode(g, 3, 0, 6);
	insertGraphNode(g, 3, 1, 5);
	insertGraphNode(g, 3, 4, 9);
	insertGraphNode(g, 4, 2, 10);
	insertGraphNode(g, 4, 3, 9);
	insertGraphNode(g, 4, 5, 4);
	insertGraphNode(g, 4, 6, 2);
	insertGraphNode(g, 5, 2, 8);
	insertGraphNode(g, 5, 4, 4);
	insertGraphNode(g, 5, 6, 14);
	insertGraphNode(g, 6, 1, 12);
	insertGraphNode(g, 6, 4, 2);
	insertGraphNode(g, 6, 5, 14);
	printGraph(g);
	printf("\n");
	int cost = PrimAlgorithm(g, 0);
	printf("\ntotal cost : %d", cost);


	getchar();
	return 0;

}​