[자료구조]Graph - MST(Minimum Spanning Tree) 설계

목차

1. Instruction
1.1 overall descriptioin
1.2 requirements
1.3 sample input/output

2. Overall System Class Design
2.1 Relationships between classes
2.2 Present class ADTs

3. Data Structure Diagram
3.1 Stack
3.2 Binary Search Tree : Insert
3.3 Binary Search Tree : Delete
3.4 Binary Search Tree : Update
3.5 Binary Search Tree : Search & Print

4. Algorithm Specfication
4.1 Pseudocodes
4.2 Performance Evaluation

5. Discussion and Conclusion

본문내용

본 프로그램은 총 11개의 클래스로 구성되어 있는데, 전체 네트워크를 표현하기 위해서 라우터를 CVertex 클래스로 정의하여 그래프 구조를 이용함으로써 가상 네트워크를 구성하였다. 또한 세션 요청을 원하는 멀티캐스트 유저 그룹들의 정보를 CGroup에 저장하고 그룹들이 사용하는 네트워크의 링크는 CEdge로 정의하여 그룹이 그 정보를 가지고 있게 하였다.
모든 그룹들은 CGroupList 클래스가 관리하고, 그룹마다 Minimum Spanning Tree를 이용하여 최소 링크 비용을 구하기 위해서 CMinHeap클래스를 작성하여 그룹이 MST를 구성시 Kruskal 알고리즘을 사용할 때 최소 비용의 edge들을 MinHeap에서 꺼내서 구성하도록 하였다.
모든 그룹이 MST를 구성하여 총 비용이 가장 큰 순으로 할당을 시도하게 되는데 이를 위하여 CMaxHeap을 구현하였고, 할당에 성공한 그룹들은 CFile클래스를 이용하여 파일에 출력하도록 하였다.
프로그램의 실행 및 관리는 CScheduler클래스의 멤버함수로 작성하여 프로그램의 전체적인 실행 흐름을 파악하기 쉽게 하였고, CVertex를 제외한 나머지 클래스들은 friend 함수를 가급적 자제함으로써 예상치 못한 필드값의 변동을 예방하였다.


1) Make Graph
n개의 vertex와 e개의 edge를 갖는 무방향 그래프는 n개의 head vertex와 2e개의 리스트 노드가 필요하다. 이 때 head vertex를 구성하기 위해서는 n개의 vertex를 생성하여 그래프 클래스 내 저장하므로 n의 시간이 걸리고, 각각의 vertex를 잇기 위해서는 모든 head vertex에 대한 edge의 총 수가 e개 만큼 필요하다.
결국 head vertex를 구성하기 위한 시간은 n이고 각각의 연결을 하기 위한 시간은 e이므로 그래프를 구성하기 위한 시간복잡도는 O(n+e)가 된다.

참고 자료

없음

압축파일 내 파일목록

2000120007_v1.0_실습 레포트(Assignment2).doc
2000120007_v1.0_설계 레포트(Assignment2).doc