[알고리즘] kruskal 알고리즘
- 최초 등록일
- 2002.11.28
- 최종 저작일
- 2002.11
- 8페이지/
한컴오피스
- 가격 1,500원

소개글
kruskal 알고리즘을 C를 사용해서 코딩한 거구요.
위의 교재에 있는 알고리즘을 충실히 구현 했습니다.
소트로는 퀵소트를 사용한 알고리즘 모두 책에 나와있는 것을 기반으로 구현했기 때문에 여타 인터넷 사이트에서 구할 수 없는 것입니다. 제가 다 만들었어요. ^^;
위 교재로 수업듣는 분한테 도움이 많이 될꺼예여~
목차
1.개념
2.진행절차
3.결과화면
4.소스코드
본문내용
- 크루스칼 알고리즘(Kruskal's algorithm) -
개 념
최소비용 신장 트리 문제를 풀기 위한 크루스칼 알고리즘은 각 정점마다 하나씩 그 정점만 포함하는 V의 서로소 부분 집합들을 만드는 것으로 시작한다. 그리고나서 가중치가 작은 것부터 차례로 이음선을 검사한다(같은 가중치에 대해서는 임의로 선택한다). 만약 어떤 이음선이 서로소 부분집압들에 있는 두 정점을 연결하면, 이음선을 추가하고, 두 부분집합을 하나로 합친다.
..................
#include <stdio.h>
struct edge{ /*정점간 가중치 집합을 위한 구조체 선언 */
int pair1;
int pair2;
int weight;
};
struct vertex{ /*정점 집합을 위한 구조체 선언*/
int parent; /*합병시 트리구조로 합병하고 그때의 부모노드*/
int depth; /*깊이를 두어 깊이 비교를 통해 레벨을 낮게 만듦*/
}; /*속도 향상을 위해*/
typedef struct edge edge;
typedef struct vertex vertex;
int Pivotpoint = 0; /*퀵소트시 쓰일 피봇포인트*/
vertex u[5]; /*정점을 위한 집합*/
edge E[8]; /*정점간 가중치를 위한 집합*/
edge F[5]; /*최소비용 신장트리를 위해 선택된 정검간 가중치를 위한 집합*/
int partition(int low, int high, int Pivotpoint);
void makeset(int i) /*정점집합의 초기화 함수*/
{
u[i].parent = i;
u[i].depth = 0;
참고 자료
FOUNDATION OF ALGORITHMS USING C++ PSEUDOCODE <NEAPOLITAN>