[알고리즘] 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>
*원하는 자료를 검색 해 보세요.
  • [알고리즘]크루스칼 알고리즘 (Kruskal`s Algorithm) - 최소신장트리 알고리즘 (Minimum Spanning Tree) 6페이지
    입니다.Kruskal`s Algorithm은 최소신장트리 (Minimum ... 알고리즘 시간의 과제로서 구현한 Kruskal`s Algorithm ... Spanning Tree)를 구현하는 기초적이면서 대표적인 알고리즘
  • 크루스칼 10페이지
    ▣ 문제개요 최소비용 신장트리를 구하는 Kruskal 알고리즘 ... 하나의 간선으로 최소비용 신장트리를 구축한다. 그러나 알고리즘의 각 ... ? Kruskal 실행 ? Prim 실행시 ▣ 느낀점 이번과제는 최소비용 신장트리
  • Kruskal Algorithm으로 구현한 최소 비용 신장 트리 (GUI 구현됨) 0페이지
    비용신장 트리 입니다.그래픽(GUI)를 제공하며 오직 자바 환경에서만 ... 알고리즘 텀 프로젝트로 수행했던 Kruskal 알고리즘을 적용한 최소 ... 풀고 돌리시면 됩니다.^^상단에 점의 수를 입력하시고 Kruskal
  • [컴퓨터 알고리즘]알고리즘 연습문제 4장 5페이지
    최소비용신장트리를 구하고, 수행되는 절차를 단계별로 구하라. 크루스칼 ... )을 이용하여 다음 그래프의 최소비용 신장 트리를 구하라. 그리고 ... ",e); } 6. 크루스칼 알고리즘을 사용하여 연습문제 2의 그래프의
  • [배열로구현된]크루스칼 알고리즘 4페이지
    을 돌린 최소 비용 신장 트리를 F 이음선 집합에 삽입 kruskal(n, m ... )); // 최소비용 신장트리 G = make_array(n); // 배열 만들기 ... , E, F); // 최소 비용 신장 트리 결과 출력 printf
  • 크루스칼 알고리즘(Kruskal`s algorithm) 8페이지
    신장 트리 문제를 풀기 위한 크루스칼 알고리즘은 각 정점마다 하나씩 그 ... . 2. 정점은 5개를 사용하였고 최소비용 신장트리 구축을 위한 예제 ... ];/*최소비용 신장트리를 위해 선택된 정검간 가중치를 위한 집합
  • [전기전자공학] 라우팅이란 무엇인가 34페이지
    라우팅 신장 트리 알고리즘 깊이우선탐색 너비우선탐색 최소비용신장트리 정적 ... 들의 비용(가중치)의 합이 된다. 최소 비용 신장 트리(Minimum ... 이다. 연결 무방향 그래프에서 최소 비용 신장트리를 구하기 위한 알고리즘
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [알고리즘] kruskal 알고리즘