Sollin 알고리즘으로 최소 신장 트리 구성하기

각 컴포넌트가 최소 비용 연결을 고르는 방식

Sollin 알고리즘은 그래프의 최소 신장 트리(MST)를 만드는 방법이다. 1977년 프랑스 수학자 Georges Sollin이 제안했으며, 한 번의 단계에서 여러 트리가 각자 최소 가중치 간선을 선택할 수 있다는 점에서 Kruskal이나 Prim과 구분된다.

이 특성은 여러 컴포넌트의 선택을 병렬로 처리할 수 있게 한다. 따라서 분산 컴퓨팅 환경에서 최소 비용 연결 구조를 구성할 때 활용할 수 있다.

독립된 트리를 병합해 전체 그래프로 확장한다

처음에는 모든 정점이 각각 하나의 트리다. 알고리즘은 각 트리에서 다른 트리로 향하는 간선 가운데 가중치가 가장 작은 간선을 찾는다. 선택된 간선으로 트리를 합치고, 모든 정점이 하나의 트리가 될 때까지 이 과정을 반복한다.

같은 간선을 두 트리가 선택했더라도 실제 병합에는 하나의 간선만 사용한다. 새로 추가할 수 있는 간선이 더 이상 없으면 과정이 끝나며, 연결된 모든 정점을 포함하는 최소 신장 트리가 남는다.

⤢✕

간선 선택이 병합으로 이어지는 예

다음 그래프를 기준으로 진행 과정을 볼 수 있다.

⤢✕

초기에는 A, B, C, D, E가 각각 독립된 트리다. 첫 반복에서 선택되는 최소 간선은 다음과 같다.

A: A-B(4)
B: B-C(3)
C: C-B(3), 이미 선택된 간선
D: D-B(5)
E: E-D(6)

중복을 제거하면 A-B(4), B-C(3), D-B(5), E-D(6)가 남는다. 이 간선들을 적용하면 모든 정점이 하나의 트리로 연결되므로 알고리즘은 종료된다.

⤢✕

이 최소 신장 트리의 총 가중치는 4 + 3 + 5 + 6 = 18이다.

Kruskal과 Prim의 선택 단위가 다르다

Sollin은 여러 트리에서 동시에 최소 가중치 간선을 고른다. 반면 Kruskal은 전체 그래프의 간선을 가중치 순으로 검토하면서 사이클이 생기지 않도록 선택한다. Prim은 하나의 트리에서 시작해 인접 정점으로 향하는 최소 가중치 간선을 계속 추가한다.

알고리즘	시간 복잡도	특징
Sollin	O(E log V)	병렬 처리에 적합하며 여러 간선을 동시에 선택
Kruskal	O(E log E)	간선 정렬이 필요하고 Union-Find 자료구조 활용
Prim	O(E log V)	우선순위 큐를 활용하며 밀집 그래프에 효율적

⤢✕

의사 코드로 보는 선택과 병합

구현에서는 컴포넌트별 최소 외부 간선을 찾고, 중복을 제거한 뒤 Union 연산으로 트리를 합친다.

function Sollin(Graph G):
    // 초기화: 각 정점을 독립된 트리로 설정
    Forest F = makeSet(G.vertices)

    // 모든 정점이 하나의 트리로 연결될 때까지 반복
    while F.numTrees > 1:
        // 각 트리에서 최소 가중치 외부 간선 찾기
        foreach Tree T in F:
            Edge e = findMinExternalEdge(T, G)
            if e exists:
                markForAddition(e)

        // 중복 간선 제거
        Edges selectedEdges = removeDuplicates(markedEdges)

        // 선택된 간선들로 트리 병합
        foreach Edge e in selectedEdges:
            F.union(e.source.tree, e.destination.tree)

    return F as MST

병렬·분산 환경에서 고려할 수 있는 적용 영역

통신 네트워크를 구성할 때는 모든 노드를 최소 비용으로 연결하는 구조를 찾는 데 사용할 수 있다. 광케이블 네트워크에서 도시 간 연결 비용을 줄이는 설계나, 한국의 지방 도시 간 인터넷 백본 네트워크 구축이 이에 해당한다.

전력 그리드에서는 발전소와 변전소를 잇는 최소 비용 전력망을 구성하는 데 적용할 수 있다. 여러 지역을 함께 고려해야 하는 대규모 전력망 설계나 신재생 에너지 발전소와 기존 전력망의 연결 최적화도 같은 범주다.

클러스터 환경에서는 노드 간 통신 경로와 데이터 센터 내부 네트워크 토폴로지를 설계할 때 활용할 수 있다. 여러 서브넷이 동시에 최적 경로를 계산해야 하는 상황과 맞는다.

구현 복잡도와 확장 방식

Sollin 알고리즘은 여러 결정을 동시에 수행하므로 병렬 처리에 적합하고, 분산 시스템에도 자연스럽게 적용할 수 있다. 대규모 그래프를 처리하는 경우에도 활용 가능하다.

반면 Kruskal이나 Prim보다 구현이 복잡하며, 중복 간선을 처리하는 로직이 추가된다. 순차 처리 환경에서는 다른 MST 알고리즘보다 효율성이 떨어질 수 있고, 일반적인 교육과정에서는 상대적으로 덜 다뤄진다.

CUDA나 OpenMP를 이용하면 각 트리의 최소 간선 선택을 GPU 또는 멀티코어에서 병렬화할 수 있다. 분산 시스템에서는 각 서브 클러스터가 독립적으로 최소 간선을 계산하고, 마스터 노드가 중복 제거와 병합을 결정하는 방식으로 구성할 수 있다.

그래프 변화에 대응하는 증분 업데이트도 가능하다. 기존 MST에서 소수의 간선만 변경해 새 MST를 빠르게 계산하는 방식은 실시간 네트워크 트래픽 관리 등에 활용할 수 있다.

인프라 연결 비용을 다룰 때의 선택지

Sollin 알고리즘은 대규모 IT 인프라의 비용 최적화, 분산 시스템 간 연결 구조 설계, 네트워크 토폴로지 설계에 적용할 수 있다. 데이터 센터 내부 네트워크와 클라우드 인프라의 리소스 최적화에서도 고려 대상이 된다.

특히 여러 컴포넌트가 동시에 최소 연결을 찾아야 하는 대규모 분산 환경에서는 Sollin의 병렬 처리 특성이 두드러진다.