알고리즘 설계실습 '크러스컬 알고리즘 소스코드 및 코드 설명서' 리포트

소개

알고리즘 설계실습 수업시간에 제출한 과제(리포트)입니다.
교수님께서 내주신 문제에 대해 프로그램을 작성하였고, 작성한 프로그램에 대한 설명을 적었습니다.

목차

1. 프로그램 개요
2. 프로그램 구조
3. 프로그램 설계
4. 프로그램 실행결과
5. 결과분석

본문내용

●프로그램 개요
욕심쟁이 방법을 사용하는 크러스컬 알고리즘을 붕괴법칙을 사용하지 않는 경우와 사용하는 경우로 구분하여 구현하였습니다.

●프로그램 구조
첨부된 input_graph 파일의 그래프를 입력으로 받고, 그 그래프를 이용해서 비용 인접 행렬을 만들었습니다. 그렇게 생성한 비용 인접 행렬에서 두 정점들 사이에 있는 가중치들을 추출하여 모든 간선을 가중치를 기준으로 오름차순으로 정렬하였습니다. 그다음에는 배열을 초기화하고, 가중치가 작은 간선부터 선택한 다음 사이클을 형성하지 않는다면(간선의 두 정점이 같은 집합에 속하지 않는다면) 두 집합을 하나로 합쳐가는 크러스컬 알고리즘을 수행하였습니다.

●프로그램 설계
두 개의 정점 u, v와 가중치 weight를 저장하는 구조체 graph를 선언하였습니다.
첨부된 input_graph 파일의 그래프를 입력으로 받아서 비용 인접 행렬을 만들기 위해 read() 함수를 구현하였습니다. 입력 파일에서 값을 분리하여 두 정점은 행과 열을 나타내게 하고, 두 정점의 간선 가중치는 인접 행렬의 성분으로 삽입하여 비용 인접 행렬을 만들었습니다. 그리고 두 정점이 모두 자기 자신이면 가중치는 0이기 때문에, 비용 인접 행렬의 대각선 성분은 모두 0으로 하였습니다.

참고자료

· 없음