자료구조] 크루스칼 그린 다음, 전부 잘 연결 되었는지 확인하는 함수

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

#define MAX_EDGES 50000000 //오천만 반드시 수정
#define MAX_VERTICES 10000
#define TRUE 1
#define FALSE 0
#define HEAP_FULL(n) (n == MAX_EDGES-1)  //간선의 정보를 담는 힙
#define HEAP_EMPTY(n) (!n)

int numVertices;
int numEdges;

//int currWeight = 0;

typedef struct edge {
	int from, to;
	int weight;
}edge;

edge e[MAX_EDGES];   //간선 노드

struct node {
	int vertex;   
	int visit;
	struct node *link;
}; //노드포인터, 간선만큼의 그래프 포인터

typedef struct node* nodePointer; 
nodePointer graph[MAX_VERTICES]; //그래프의 노드(정점 숫자, 링크 가짐)

edge Minheap[MAX_EDGES];  //가중치용 최소힙
edge tMinheap[MAX_EDGES];
int nmin = 0;
//우선, 파일에서 세 번째 요소를 불러와 마이너 힙을 구성하자

void insert_min_heap(edge item, int *nmin);
edge delete_min_heap(int *nmin);
void connect(int, int);
nodePointer findest(int);

 

 

 

//e[i]의 start 또는 dest를 받아온다
nodePointer findest(int vert) //nodePointer graph[] +  node* nodePointer;
{
//printf("%d and %d\n", vert, graph[vert]->vertex);
	if (graph[vert]->link!= graph[vert])
//받아온 정점의 link가 자기 자신이 아닐 때
	{
		nodePointer imsi = findest(graph[vert]->link->vertex);
		graph[vert]->link = imsi->link; //재귀선언
//printf("vis cha %d", graph[vert]->vertex);
	}
//printf("vis %d\n", graph[vert]->vertex);
	graph[vert]->visit = TRUE;
	return graph[vert]->link;
}

void connect(int st, int des) {
	nodePointer imsi1=findest(st); 
	nodePointer imsi2=findest(des);
	st = imsi1->vertex; //e[i]의 start와 dest를 받아와, findest(76행)
	des = imsi2->vertex; //각자 저장된 건, st나 des vertex와 연결된 정점
// printf("링크 %d %d \n", graph[st]->link, graph[des]->link);
// compare V with U.
	if (graph[st]->link->vertex < graph[des]->link->vertex) {
		for (int i = 0; i < numVertices; i++) {
			if (graph[i]->link->vertex == graph[des]->vertex)
				graph[i]->link = graph[st]->link;
		}

		graph[des]->link = graph[st]->link;
// graph[des]->visit = TRUE;

// printf("링크1: %d %d\n",
// graph[st]->link->vertex, graph[des]->link->vertex);
	}
	else {
		for (int i = 0; i < numVertices; i++) {
			if (graph[i]->link->vertex == graph[st]->vertex)
				graph[i]->link = graph[des]->link;
        }

		graph[st]->link = graph[des]->link;
// graph[st]->visit = TRUE;

// printf("링크2: %d %d\n",
// graph[st]->link->vertex, graph[des]->link->vertex);
	}
}

 

void insert_min_heap(edge item, int *nmin) {

	int i;
	if (HEAP_FULL(*nmin)) {
		fprintf(stderr, "The heap is full.\n");
		exit(1);
	}

	i = ++(*nmin);
	while ((i != 1) && (item.weight < Minheap[i / 2].weight)) {
		Minheap[i] = Minheap[i / 2];
		i /= 2;
    }
	Minheap[i] = item;
}

 

edge delete_min_heap(int *nmin) {
	int parent, child;
	edge item, temp;

	if (HEAP_EMPTY(*nmin)) {
//printf("%d\n", nmin);
		fprintf(stderr, "The heap is empty");
	exit(1);
	}

	item = Minheap[1];
	temp = Minheap[(*nmin)--];
	parent = 1;
	child = 2;

 	while (child <= *nmin) {
	if ((child < *nmin) && (Minheap[child].weight
    > Minheap[child + 1].weight))
    	child++;

 	if (temp.weight <= Minheap[child].weight) 
    	break;
	Minheap[parent] = Minheap[child];
	parent = child;
	child *= 2;
    }
	
    Minheap[parent] = temp;
	return item;
} 

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

#define MAX_EDGES 50000000 //오천만 반드시 수정
#define MAX_VERTICES 10000
#define TRUE 1
#define FALSE 0
#define HEAP_FULL(n) (n == MAX_EDGES-1)  //간선의 정보를 담는 힙
#define HEAP_EMPTY(n) (!n)

int numVertices;
int numEdges;

//int currWeight = 0;

typedef struct edge {
int from, to;
int weight;
}edge;
edge e[MAX_EDGES];   //간선 노드

struct node {
int vertex;   
int visit;
struct node *link;
}; //노드포인터, 간선만큼의 그래프 포인터
typedef struct node* nodePointer; 
nodePointer graph[MAX_VERTICES]; //그래프의 노드(정점 숫자, 링크 가짐)

edge Minheap[MAX_EDGES];  //가중치용 최소힙
edge tMinheap[MAX_EDGES];
int nmin = 0;
//우선, 파일에서 세 번째 요소를 불러와 마이너 힙을 구성하자

void insert_min_heap(edge item, int *nmin);
edge delete_min_heap(int *nmin);
void connect(int, int);
nodePointer findest(int);

 

 

 

//e[i]의 start 또는 dest를 받아온다
nodePointer findest(int vert) //nodePointer graph[] +  node* nodePointer;
{
//printf("%d and %d\n", vert, graph[vert]->vertex);
if (graph[vert]->link!= graph[vert])
//받아온 정점의 link가 자기 자신이 아닐 때
{
nodePointer imsi = findest(graph[vert]->link->vertex);
graph[vert]->link = imsi->link; //재귀선언
//printf("vis cha %d", graph[vert]->vertex);
}
//printf("vis %d\n", graph[vert]->vertex);
graph[vert]->visit = TRUE;
return graph[vert]->link;
}

void connect(int st, int des)
{
nodePointer imsi1=findest(st); 
nodePointer imsi2=findest(des);
st = imsi1->vertex; //e[i]의 start와 dest를 받아와, findest(76행)
des = imsi2->vertex; //각자 저장된 건, st나 des vertex와 연결된 정점
// printf("링크 %d %d \n", graph[st]->link, graph[des]->link);
// compare V with U.
if (graph[st]->link->vertex < graph[des]->link->vertex)
{
for (int i = 0; i < numVertices; i++)
{
if (graph[i]->link->vertex == graph[des]->vertex)
graph[i]->link = graph[st]->link;
}

graph[des]->link = graph[st]->link;
// graph[des]->visit = TRUE;

// printf("링크1: %d %d\n",
// graph[st]->link->vertex, graph[des]->link->vertex);
}
else
{
for (int i = 0; i < numVertices; i++)
{
if (graph[i]->link->vertex == graph[st]->vertex)
graph[i]->link = graph[des]->link;
}

graph[st]->link = graph[des]->link;
// graph[st]->visit = TRUE;

// printf("링크2: %d %d\n",
// graph[st]->link->vertex, graph[des]->link->vertex);
}
}

 

void insert_min_heap(edge item, int *nmin) {

int i;
if (HEAP_FULL(*nmin)) {
fprintf(stderr, "The heap is full.\n");
exit(1);
}

i = ++(*nmin);
while ((i != 1) && (item.weight < Minheap[i / 2].weight)) {
Minheap[i] = Minheap[i / 2];
i /= 2;
}
Minheap[i] = item;
}

 

edge delete_min_heap(int *nmin) {
int parent, child;
edge item, temp;

if (HEAP_EMPTY(*nmin)) {
//printf("%d\n", nmin);
fprintf(stderr, "The heap is empty");
exit(1);
}

item = Minheap[1];
temp = Minheap[(*nmin)--];
parent = 1;
child = 2;

 

while (child <= *nmin) {
if ((child < *nmin) && (Minheap[child].weight
> Minheap[child + 1].weight)) child++;

 

if (temp.weight <= Minheap[child].weight) break;
Minheap[parent] = Minheap[child];
parent = child;
child *= 2;
}
Minheap[parent] = temp;
return item;
} 

 

-------------------------------------

크루스칼 자체는 흔하니까 넘어가도록 하고,

가장 애를 먹었던 부분은 '과연 어떻게 해야 모든 것이 연결되었는지 알 수 있는가' 였다.

이를 위해 선택한 방법은 바로, 무식하게 노드가 연결될 때마다, 해당 노드의 link를, 가장 작은 값으로 가리키는 것이었다.

 

즉, 예를 들면 5와 3이 연결되면, 5가 3을 가리킨다. 이후에, 5와 8이 연결되면, 8은 5를 가리킨 다음, 해당 5가 또 가리키는 게 있는지 확인한 다음, 있다면 그것(3)을 가리키게 하는 것이었다.

이런 방식으로 끝까지 해나가면, 만일 그래프가 완전히 하나로 이뤄진다면 모든 노드가 하나의 값을 가리키게 될 터이다.

이렇게 되면, 그래프가 나뉘게 되면(1 3 5의 연결과 2 4의 연결로 두개로 나뉜 그래프) 각각 다른 값을 가리키게 되므로, 최종적으로는 disconnected가 된다.

 

원래 이 때의 의도는 bfs나 dfs를 이용하거나, 혹은 union과 disjoint를 활용하는 방법인데

나 나름대로 무식한 방법의 union을 만들었다고 생각한다.