본 프로그램을 구현하기 위해서는 그래프, 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 알고리즘의 각 단계를 나타낸 것이다.