[알고리즘] kruskal 알고리즘

등록일 2002.11.28 한글 (hwp) | 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>
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서