글 읽기 - ★최소비용 신장트리에 대해 질문. 답변 부탁드려요

rdd6584 7년 전 0

밑에는 제 프림 코드입니다.

prim(0, n)일 때는 정답

prim(4, n)일 떄는 오답

prim(9, n)일 떄는 정답 이런식으로 매우 불안정한 값들이 나왔습니다.

크루스칼로 작성한 코드도 오답처리 되었구요.

아마도 간선중에 같은 값이 있을 경우 경우에따라 각각 다른 트리가 만들어져서 이런 현상이 발생하는거 같은데

완벽하게 문제를 해결할 수 있는 알고리즘이 있을까요?

#include<stdio.h>
#define TRUE 1
#define FALSE 0

#define MAX 1000
#define INF 1000L

int weight[MAX][MAX];

int selected[MAX];
int dist[MAX];
long long int sum = 0;

int get_min_vertex(int n)
{
	int v, i;
	for (i = 0; i < n; i++)
		if (!selected[i]) {
		v = i;
		break;
	}
	for (i = 0; i < n; i++)
		if (!selected[i] && (dist[i] < dist[v])) v = i;
	return (v);
}

void prim(int s, int n)
{
	int i, u, v;

	for (u = 0; u < n; u++)
	{
		dist[u] = INF; selected[u] = FALSE;
	}
	dist[s] = 0;
	for (i = 0; i < n; i++) {
		u = get_min_vertex(n);
		selected[u] = TRUE;
		if (dist[u] == INF) return;
		sum += dist[u];
		for (v = 0; v < n; v++)
			if (weight[u][v] != INF)
				if (!selected[v] && weight[u][v] < dist[v])
					dist[v] = weight[u][v];
	}
}

int main()
{
	int n, m;
	scanf("%d", &n);
	scanf("%d", &m);
	int temp1, temp2, temp3;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			weight[i][j] = INF;

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &temp1, &temp2, &temp3);
		weight[temp1-1][temp2-1] = temp3;
		weight[temp2-1][temp1-1] = temp3;
	}

	prim(4, n);

	printf("%lld", sum);
}

rdd6584 7년 전 0

혹은 문제가 없다면, 제 코드에서 어떤점이 틀린걸까요?

rhs0266 7년 전 0

프림은 간선을 n-1번 추가합니다.

n번째 get min vertex 호출의 리턴값이 쓰레기값일수가 있네요

rdd6584 7년 전 0

답변 감사합니다.

그런데 맨처음에 dist에 0값이 들어가기 때문에 n번째에 끝나야하는게 맞지않나요?

그리고 제 밑에 n-1번 더했을때 멈추는 또다른 프림코드에서도 같은 prim 시작정점에 따라서 같은 결과를 보이네요..

#include<stdio.h>
#define TRUE 1
#define FALSE 0
#define MAX 1000

typedef struct {
	int val;
	int x, y;
}element;
typedef struct {
	int heap_size;
	element heap[500002];
}HeapType;
HeapType heap;

int weight[MAX][MAX];
int selected[MAX];
long long sum = 0;
int n, m; int count = 0;

void init(HeapType *h)
{
	h->heap_size = 0;
}
void insert(HeapType *h, element item)
{
	int i;
	i = ++(h->heap_size);

	while ((i != 1) && (item.val < h->heap[i / 2].val)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;
}
element delete(HeapType *h)
{
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size--)];
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		if ((child < h->heap_size) && (h->heap[child].val) > h->heap[child + 1].val)
			child++;
		if (temp.val <= h->heap[child].val) break;
		h->heap[parent] = h->heap[child];

		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

void prim(int s)
{
	element temp;
	selected[s]++;

	for (int i = 0; i < n; i++)
		if (weight[s][i] && !selected[i])
		{
			temp.val = weight[s][i];
			temp.x = s;
			temp.y = i;
			insert(&heap, temp);
		}

	do
	{temp = delete(&heap);
	} while (selected[temp.y]);
	sum += temp.val;
    count++;
    
    if(count == n-1)
        return;
    
    
	prim(temp.y);
}

int main()
{
	scanf("%d", &n);
	scanf("%d", &m);
	int temp1, temp2, temp3;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			weight[i][j] = 0;

	for (int i = 0; i < n; i++)
		selected[i] = 0;

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &temp1, &temp2, &temp3);
		weight[temp1 - 1][temp2 - 1] = temp3;
		weight[temp2 - 1][temp1 - 1] = temp3;
	}

	prim(0);

	printf("%lld", sum);
}