본 프로그램을 구현하기 위해서는 그래프, Minimum Spanning Tree, 힙, 집합 구조에 대한 이해가 필요하다. 다음은 프로그램을 구현하기 위하여 사용되는 구조에 대한 설명들이다.
인터넷 멀티캐스트 기반의 환경을 구성하기 위해서는 그래프 구조가 쓰이는데, 그림 1은 그래프의 예에 대해서 나와 있다.
그래프는 정점(V)과 간선(E)으로 구성되는데, G1과 G2는 E의 방향이 나타나 있지 않은데 그럴 경우 V(0) 를 u, V(1)을 v라 했을 때 간선(u, v)와 (v, u)는 동일한 간선을 나타내고 이러한 그래프를 무방향 그래프라 한다. G3는 간선이 방향을 가지고 있는데 이 경우 <u,v>와 <v,u>의 간선은 서로 다른 종류이며 이러한 그래프를 방향 그래프라 한다. 또한 G1처럼 정점이 자신을 제외한 나머지 모든 정점에 대해서 간선을 가지고 있으면 완전그래프라 한다. G2는 트리구조처럼 생겼는데 트리 역시 그래프의 파생구조이므로 그래프라 불릴 수 있다.
이번 과제에서 사용할 그래프는 방향성이 없는 무방향 그래프(undirected graph)인데 이는 인터넷 멀티캐스트 환경에서 라우터 간의 링크 비용이 두 라우터의 순서에 상관없이 동일하기 때문이다.
그래프는 행렬 또는 인접리스트, 다중리스트 형태로 나타낼 수 있다.
그래프를 행렬을 이용하여 구현할 경우 정점의 수가 n이라고 할 때 n²의 공간을 필요로 한다. 이 그래프에 있는 간선의 수를 알고자 하거나 또는 그래프가 연결되어 있는지에 대해서 알고자 하는 경우엔 인접행렬에서는 n²-n개의 항(대각항들은 0)을 조사해 보아야 하므로 최소한 O(n²)의 시간이 필요하다. 또한 간선이 많지 않은 희소 그래프(sparse graph) 사용하지 않음에도 불구하고 잡혀있는 메모리가 많음으로 낭비이다.
인접 리스트에서는 인접 행렬의 n행들을 n개의 연결 리스트로 표현한다. 즉, 그래프 G의 각 정점에 대해 한 개의 연결 리스트가 존재한다. 리스트 i에 있는 노드들은 정점 i로부터 인접되어 있는 정점들을 나타낸다. 각 노드는 적어도 두 개의 필드, 즉 data와 link필드를 가진다. data 필드는 정점 i에 인접한 정점의 번호를 저장한다.
무방향 그래프의 각 정점의 차수는 그 정점에 대한 인접리스트에 속한 노드의 수가 되므로 그래프의 간선의 수는 O(n+e) 시간에 구할 수 있다. 이는 인접행렬을 이용하여 구현한 그래프보다 속도면에서 나은 면을 보이며 본 프로그램은 바로 이 인접리스트를 이용하여 구현하였다.
파일에서 각 라우터와 링크에 대한 정보를 읽어와서 그래프를 구성하였으면 각 그룹들이 세션을 배정받기 위하여 화상 회의 때 사용하는 라우터들을 최소 비용으로 사용할 수 있도록 링크를 설정해야 한다.
그래프에서 최소의 연결비용으로 모든 정점을 잇는 트리를 최소 비용 신장 트리(minimum cost spanning tree)라고 하며 이 방식을 이용하여 각 그룹들의 최소 링크 비용을 구하게 된다.
MCST를 구하기 위한 알고리즘은 여러 가지가 있는데 그 중에서 본 프로그램에서 활용할 알고리즘은 Kruskal 알고리즘인다.
Kruskal 알고리즘은 한 번에 하나씩 T에 간선을 추가해 가면서 최소 비용 신장 트리 T를 구축하는 방법인데, T에 포함될 간선을 비용의 크기 순으로 선택해 간다. 이미 T에 포함된 간선들과 사이클을 형성하지 않는 간선만을 T에 추가하고, 그래프는 연결되어 있고 n>0개의 정점을 가지므로 정확하게 n-1개의 간선만이 T에 포함되게 된다.
아래 그림 2는 Kruskal 알고리즘의 각 단계를 나타낸 것이다.
그림 2의 (a) 그래프로부터 최소 비용 신장 트리를 구해보자. 먼저 선택된 간선이 없는 상태에서 시작한다. (b)는 간선이 선택되지 않은 현재 그래프를 나타낸다. 간선 (0,5)에 대한 포함 여부를 제일 먼저 고려한다. 이 간선은 트리에 추가된다. 그 결과로 그림 (c)의 트리가 된다. 다음으로 간선(2,3)이 다시 트리에 포함(d)된다. 다음 고려되는 간선은 (1,6)이다. 이 간선을 포함해도 사이클이 형성되지 않으므로 트리에 포함시켜 (e)를 얻는다.
간선(1,2)도 마찬가지로 트리에 포함(f)된다. 아직 고려되지 않은 간선 중에서 최소 비용은 (6,3)이다. 이것은 바로 다음에 고려한다. 이 간선을 트리에 포함시키면 사이클이 형성(g)되므로 거부된다. 간선(4,3)이 다음에 고려되고 트리에 추가되어 (g)가 된다. 다음으로 고려되는 간선은 (6,4)이다. 이 간선은 사이클을 형성하므로 거부된다. 최종적으로, 간선(5,4)가 트리에 포함된다. 이로서 신장트리가 완성된다.
레코드의 수를 n이라고 했을 때, 파일의 레코드를 읽기 위한 loop는 레코드의 수인 n번을 호출하게 되므로, O(n)의 시간복잡도를 가진다.
2) Save recoard to CData object
하나의 레코드의 필드의 수를 m이라고 하자.
이 레코드를 읽어들여서 해당 Command에 따른 함수를 호출하게 된다. 각각의 함수들은 나머지 레코드의 필드를 잘라서 각각 데이터 객체에 저장하게 되는데, SaveInsertRecord는 loop를 m번만큼 수행하여 모든 필드를 데이터에 저장하고(m), SaveDeleteRecord는 if-else 내의 loop를 m-c1만큼 수행하여 필드를 데이터에 저장하며, SaveUpdateRecord는 m-c2만큼 필드를 저장하고 if-else내에서 나머지 필드를 m-c3만큼 저장한다. SavePrintRecord는 m만큼의 필드를 저장한다.
즉, SaveInsertRecord는 m = O(m), SaveDeleteRecord는 m-c1 = O(m), SaveUpdateRecord는 (m-c2) + (m-c3) = O(m), SavePrintRecord는 m = O(m)이다.
어떠한 Command를 수행하더라고 시간복잡도는 O(m)이므로 이 함수의 전체적인 시간복잡도 역시 O(m)이 된다.
3) Insert Node to BST
트리의 노드 수를 n이라고 하자.
삽입될 노드는 loop 내에서 현재 위치한 트리의 노드의 크기와 작은지 큰지를 비교하며 한쪽 트리로만 이동하게 된다. 즉, 트리의 균형이 최악의 경우가 아니라면 트리의 높이는 log2c1(n+c2)을 가지게 되는데(완전 이진트리의 높이는 log2(n+1)이다) 중간에 같은 값의 노드가 있다면 비교 loop를 빠져나오게 되므로 전체적으로 log2c1(n+c2-c3)의 시간복잡도를 가진다. 그런데 삽입시 이름트리와 전화번호트리 두 곳에서 삽입을 하므로 log2c1(n+c2-c3) * 2 = 2log2c1(n+c2-c3) = 2log2n = O(log2n)의 시간복잡도를 가진다.
하지만 트리의 균형이 최악이라면 트리는 선형리스트와 같은 구조를 지니게 되므로 삽입시 n-c1 = O(n)의 시간복잡도를 가지게 된다.
4) Delete Node from BST(by name and phone)
트리의 노드 수를 n이라고 하자.
삭제될 노드는 loop 내에 같은 값을 가진 노드가 있는지를 비교하며 한쪽 트리로 이동하게 된다. 즉 삽입에서와 같은 시간복잡도인 O(log2n)을 가지게 된다. 만약 삭제될 노드를 찾았다면 삭제될 노드의 자식트리에서 교체될 노드를 찾아야 하는데 노드는 아직 트리의 끝에 다다르지 않았으므로 교체될 노드를 찾아서 다시 loop를 돈다고 해도 전체적으로 log2n만큼의 수행을 하는 것과 같다.(전체 트리 검색 = 삭제될 노드 검색 + 교체될 노드 검색)
따라서, 삭제될 노드와 교체될 노드를 찾은 시간복잡도는 O(log2n)이며, 노드의 교체는 상수시간만큼 일어나므로 최종적인 시간복잡도는 O(log2n)을 가지게 된다.
하지만 삽입과 마찬가지로 트리의 균형이 최악이라면 시간복잡도는 O(n)이다.
5) Update Node to BST
업데이트는 노드를 삭제한 후 다시 새로운 데이터값을 가진 노드를 삽입하는 방식이다. 노드의 삽입시 시간복잡도는 log2n이고 삭제 역시 log2n이므로 업데이트의 시간복잡도는 2log2n = O(log2n)을 가지게 된다.
하지만 업데이트 역시 트리의 균형이 최악이라면 삽입(n) + 삭제(n) = O(n)의 시간복잡도를 가지게 된다.
6) Print BST
트리의 노드 수를 n이라고 하자.
이름이 같은 노드, 전화번호가 같은 노드, 모든 노드를 출력시 트리의 모든 노드들은
스택에 꼭 한번씩 삽입이 된다. 즉, loop내에서 n번만큼 수행하므로 O(n)의 시간복잡도를 가진다.
DSAssignment3.pdf
BinomialHeap(Assignment3).zip
