Kruskal`s algorithm

소개

(숙제5 : Kruskal`s algorithm)
(숙제6 : 숙제5를 이용한 Graphic User Interface)

크루스칼 알고리즘을 c++을 이용해서 GUI를 구현했습니다.
매우 어려운 과제 였으나 훌룡하게 소화. 좋은 레폿완성! ㅋㅋ

소스코드, 실행화면, 분석, 모두 있습니다.

목차

숙제 5. Kruskal`s Algorithm
함수원형
추가된 함수
Kruskal`s Algorithm 소스코드
Kruskal`s Algorithm 시간 복잡도

숙제 6. Graphic User Interface
실행화면
정보입력창
경고창
주요 코드

본문내용

☑ 함수원형
void sort(int m, Edge *E); // Edge정렬 함수
void Kruskal(int n, int m, Edge *E, Edge *F); // Kruskal`s Algorithm
void Initial(int n); // n개의 서로소 부분집합을 초기화
void makeset(int i); // i노드 생성
int CountEdge(Edge *F); // F집합의 Edge 개수 Count
set_pointer find(int i); // i가 포함된 집합의 포인터를 리턴
bool equal(set_pointer p, set_pointer q); // p와 q가 같은 집합을 가리키는 지 확인
void merge(set_pointer p, set_pointer q); // q와 q가 가리키는 집합을 합병
universe U; // nodetype의 구조체 U 선언

Kruskal`s Algorithm 은 교재에 나와있는 함수를 그대로 사용했다.(부록 C)


☑ 추가된 함수
그래프에서 이음선을 가중치를 기준으로 비오름차순으로 정렬하는 함수
sort(int m, Edge *E) // 이음선의 수, 이음선 집합
이음선의 수를 계산하는 함수
CountEdge(Edge *f); // MST를 만드는 이음선의 집합


☑ Kruskal`s Algorithm 소스코드

참고자료

· 없음