|
#include <iostream>
using namespace std;
#define MAX 10000
int parent[8];
int Set_Find(int i)
{
for (; parent[i]>=0; i=parent[i]);
return i;
}
void Set_Union(int i, int j)
{
// parent[j] = i;
parent[i] = j;
}
void Set_Initialize(void)
{
for(int i = 0; i < 8; i+
|
|
|
|
그래픽(GUI)
|
|
|
|
//kruskal algorithm을 이용한 최소 비용 신장 트리 출력
//파일입력 :
// 첫번째 줄 - 총 노드 개수
// 두번째 줄 - 총 간선 개수
// 세번째 줄 부터 - " node node cost " 순으로 간선수만큼 입력
#include <stdio.h>
#include <stdlib
|
|
|
ber[1];
p = Find(i,U);
q = Find(j,U);
if(p != q)
{
Discard(p,q,U);
Finally[count] = e;
count++;
}
index++;
}
}
void Kruskal::Print(Kruskal Start[],int n) //계산결과출력
{
cout<<\"출발점<<\"도착점<<\"간선비용<<endl;
for(int i=0;i<n;i++)
{
if(Start[i].cost != 0)
cout<<
|
|
|
|
최소비용 신장트리(minimum spanning tree)를 구하는 알고리즘의 하나인 크루스칼(kruskal)알고리즘이다.
입력은 연결된, 가중치가 있는 비방향 그래프 의 노드와 가중치로 주어진다. 예를 들어 다음과 같다.
a b 1
a c 3
a d 6
a e 5
a g 7
b e 2
b g 5
c d 2
|
|
메뉴펼치기
