자료구조(18) - 최소 스패닝 트리

#include <stdio.h>
#include <stdlib.h>
#include "Heap.h"
#include "Union_find.h"

int Kruskal(info info_arr[], const int arr_num) {
	Heap st = NULL;
	int num_of_nodes = 0;
	// 미리 만든 힙 이용

	int arr[NODE + 1] = { 0 , };
	init(arr);
	// 미리 만든 유니온 파인드 사용

	for (int i = 0; i < arr_num; i++) {
		insert(&st, info_arr[i], &num_of_nodes);
	} // 힙에 넣어서 하나씩 pop해서 사용

	int total_cost = 0; // 총 가중치 합

	for (int i = 0; i < arr_num; i++) {
		info* temp= Delete(&st, &num_of_nodes);
		// 정렬된 간선 리스트에서 순서대로 간선을 선택하면서

		if (find(arr, temp->vertex1) != find(arr, temp->vertex2)) {
			_union(arr, temp->vertex1, temp->vertex2);
            //한 집합으로 연결

            total_cost += temp->weight;
            // 가중치를 더함

			printf("total_cost : %d\n\n", total_cost);
		}
		else {
			continue;// 아닐시 패스
		}
	}

	return total_cost;
}


int main(void) {
	info arr[] = { {1, 2, 2}, {1, 3, 3}, {2, 3, 1}, {2, 4, 3}, {2, 5, 2}, {4, 5, 5}, {3, 5, 1}};
	// 정점 연결, 가중치 정보

	int arr_num = sizeof(arr) / sizeof(info);

	printf("The minimum cost of spanning tree is %d", Kruskal(arr, arr_num));

}

int primMST(struct EdgeInfo edges[], int numEdges, int startVertex) {
    // 유니온-파인드를 위한 배열 초기화
    int parent[NODE + 1];
    for (int i = 1; i <= NODE; i++) {
        parent[i] = i;
    }

    int num_of_tree_node = 1;
	// 스패닝 트리에 포함된 정점 수
	//임의의 시작 정점을 선택하여 트리에 포함시킨다.

	int total_cost = 0;
	// 총 가중치 합

    // 시작 정점을 스패닝 트리에 추가
    // 여기서는 간선이 없는 정점으로 가정
    // 실제 구현에서는 dist 배열 초기화 등이 필요할 수 있음

    // 스패닝 트리를 만들 때까지 반복
    while (numTreeNodes < NODE) {
        // 아직 트리에 속하지 않은 정점 중에서 가장 작은 간선 선택 및 추가

        // 유니온-파인드 연산을 통해 정점을 스패닝 트리에 추가

        // 스패닝 트리에 포함된 정점 수 증가

        // 선택한 간선의 가중치를 총 가중치 합에 추가

        // 선택한 정점을 기준으로 다른 정점들과의 거리 업데이트
    }

    return totalCost;
}

#include <stdio.h>
#include <stdlib.h>
#include "Union_find.h"

#define INF 123456789

typedef struct input {
	int vertex1;
	int vertex2;
	int weight;
}info;

int is_tree(int parent[], const int target, const int start) {
	if (find(parent, target) == find(parent, start)) {
		return 1;
	}
	else {
		return 0;
	}
}

void make_matrix(info info_arr[], int matrix[][NODE + 1], const int parent_num) {
	for (int i = 0; i < parent_num; i++) {
		int v1 = info_arr[i].vertex1;
		int v2 = info_arr[i].vertex2;
		int w = info_arr[i].weight;

		matrix[v1][v2] = w;
		matrix[v2][v1] = w;
	}
}

void init_dist(int matrix[][NODE + 1], int dist[], const int start) {
	for (int i = 1; i <= NODE; i++) {
		if (start == i) {
			dist[i] = 0;
			// 이미 트리라면 0
		}
		else if (matrix[start][i] != 0) {
			dist[i] = matrix[start][i];
			// 스패닝 트리와 연결되지 않는다면 INF
		}
	}
}

void update(int matrix[][NODE + 1], int dist[], const int target_v) {
	for (int i = 1; i <= NODE; i++) {
		if (target_v == i) {
			dist[i] = 0;
			// 이미 트리라면 0
		}
		else if (matrix[target_v][i] != 0) {
			if (dist[i] > matrix[target_v][i]) {
				dist[i] = matrix[target_v][i];
			}
			// 새로 추가된 target_v를 통해 연결할 수 있고
			// 기존의 dist보다 작은 값을 가진다면 바꿈
		}
	}
}

int Prim(info info_arr[], const int parent_num, const int start) {
	int matrix[NODE + 1][NODE + 1] = { 0, };
	make_matrix(info_arr, matrix, parent_num);
	//쉬운 처리를 위해 인접행렬 사용

	int parent[NODE + 1] = { 0 , };
	init(parent);
	// 유니온-파인드를 위한 배열 초기화

	int num_of_tree_node = 1;
	// 스패닝 트리에 포함된 정점 수
	//임의의 시작 정점을 선택하여 트리에 포함시킨다.

	int total_cost = 0;
	// 총 가중치 합

	int dist[6] = {INF, INF, INF, INF, INF, INF };
	// 스패닝 트리가 아닌 원소와 이미 트리인 원소의 사이 간선 중
	// 가중치가 가장 작은 간선의 가중치

	init_dist(matrix, dist, start);
	// dist 배열 초기화

	// 스패닝 트리를 만들 때까지 반복
	while (num_of_tree_node < NODE) {
		int target_v;
		int min = INF;// 초기화

		for (int i = 1; i <= NODE; i++) {
			if (!is_tree(parent, i, start)) {
				if (min > dist[i]) {
					min = dist[i];
					target_v = i;
				}
			}
		}
		// 아직 트리에 속하지 않은 정점 중에서
		// 가장 작은 간선을 가진 정점 선택

		_union(parent, target_v, start);
		// 유니온-파인드 연산을 통해 정점을 스패닝 트리에 추가

		num_of_tree_node += 1;
		// 스패닝 트리에 포함된 정점 수 증가

		total_cost += min;
		// 선택한 간선의 가중치를 총 가중치 합에 추가

		// dist 최신화
		update(matrix, dist, target_v);
	}
	// 선택한 정점을 기준으로 다른 정점들과의 거리 업데이트

	return total_cost;
}


int main(void) {
	info parent[] = { {1, 2, 2}, {1, 3, 3}, {2, 3, 1}, {2, 4, 3}, {2, 5, 2}, {4, 5, 5}, {3, 5, 1} };
	// 정점 연결, 가중치 정보

	int parent_num = sizeof(parent) / sizeof(info);

	printf("The minimum cost of spanning tree is %d", Prim(parent, parent_num, 1));
	// 임의의 정점 1에서 시작

}