합집합찾기(union-find)알고리즘을 이용하여 크루스칼 알고리즘 구현해보기

소개글

"합집합찾기(union-find)알고리즘을 이용하여 크루스칼 알고리즘 구현해보기"에 대한 내용입니다.

목차

없음

본문내용

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

#define TRUE 1
#define FALSE 0

#define MAX_VERTICES 100
#define INF 1000

int parent[MAX_VERTICES]; // 부모 노드
// 초기화
void set_init(int n)
{
for (int i = 0; i < n; i++)
parent[i] = -1;
}
// curr가 속하는 집합을 반환한다.
int set_find(int curr)
{
if (parent[curr] == -1)
return curr; // 루트
while (parent[curr] != -1) curr = parent[curr];
return curr;
}

// 두개의 원소가 속한 집합을 합친다.
void set_union(int a, int b)
{
int root1 = set_find(a); // 노드 a의 루트를 찾는다.
int root2 = set_find(b); // 노드 b의 루트를 찾는다.
if (root1 != root2) // 합한다.
parent[root1] = root2;
}

struct Edge { // 간선을 나타내는 구조체
int start, end, weight;
};

typedef struct GraphType {
int n; // 간선의 개수
struct Edge edges[2 * MAX_VERTICES];
} GraphType;

// 그래프 초기화
void graph_init(GraphType* g)
{
g->n = 0;
for (int i = 0; i < 2 * MAX_VERTICES; i++) {
g->edges[i].start = 0;

참고 자료

없음