[알고리즘] 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>
*원하는 자료를 검색 해 보세요.
  • C로 구현한 kruskal 알고리즘입니다.. 0페이지
    C로 구현한 Kruskal 알고리즘입니다..직접 입력하거나 파일입출력도 가능합니다..자료구조 공부하시는 분한테 도움이 될 것 같습니다..
  • [자료구조] Kruskal 알고리즘 2페이지
    void bfs(Graph_Pointer g, int v){int v2;Node_Pointer w;Queue_Pointer front, rear;Head_Pointer h, h2;h = get_head(g, v);if (h == NULL)return;front = re..
  • Kruskal's Algorithm(크루스칼 알고리즘) 0페이지
    크루스칼 알고리즘(Kruskal's Algorithm)을 이용해서 그래프의 최소비용을 계산하는 프로그램입니다.배열을 이용을 하였습니다.
  • Kruskal' algorithm 구현 0페이지
    자료구조 강의를 들으며 Kruskal' algorithm 을 구현했던 소스입니다. 많이 부족하지만....혹시나 도움이 될까해서 올렸습니다. * 크루스칼 알고리즘 - 포리스트에서 어떤 두개의 트리를 연결하는 모든 간선중 가장 가중치가 작은 간선(u,v)를 찾는 것으로 ..
  • Kruskal Algorithm으로 구현한 최소 비용 신장 트리 (GUI 구현됨) 0페이지
    알고리즘 텀 프로젝트로 수행했던 Kruskal 알고리즘을 적용한 최소비용신장 트리 입니다.그래픽(GUI)를 제공하며 오직 자바 환경에서만 돌아가도록 awt와 swing으로 구현 했습니다.쉽게 말해서 그냥 소스코드 풀고 돌리시면 됩니다.^^상단에 점의 수를 입력하시고 K..
  • Kruskal`s algorithm 10페이지
    ☑ 함수원형void sort(int m, Edge *E);// Edge정렬 함수void Kruskal(int n, int m, Edge *E, Edge *F);// Kruskal`s Algorithmvoid Initial(int n);// n개의 서로소 부분집합을 초기..
  • 최소비용신장트리 찾는 프로그램 (Prim, Kruskal) 0페이지
    if(_edgenum==0)return -1;//알고리즘 수행Edge* F=new Edge[_edgenum];INDEX i, j;int count=0, resultnum=0;SETPOINTER p, q;Edge e;_sortEdges(_inputEdges, _edgen..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [알고리즘] kruskal 알고리즘