인접 리스트로 구현하는 프림(Prim) 최소 신장 트리(MST) 알고리즘

여기서 소개하는 알고리즘은 앞서 살펴본 인접 행렬 기반 프림(Prim) 알고리즘과 원리는 동일합니다. 유일한 차이점은 그래프 G(V, E)를 인접 리스트(adjacency list) 형태로 표현한다는 점입니다.

인접 리스트 표현을 사용할 때의 시간 복잡도는 O(E log V)입니다. 따라서 간선 수가 정점 수에 비해 적은 희소 그래프(sparse graph)에서 특히 효율적으로 동작합니다.

입력과 출력

입력:
비용 행렬(cost matrix):

출력:
Edge: A--B And Cost: 1
Edge: B--E And Cost: 2
Edge: A--C And Cost: 3
Edge: A--D And Cost: 4
Edge: E--F And Cost: 2
Edge: F--G And Cost: 3
Total Cost: 15

알고리즘

prims(g: Graph, start)

입력 − 그래프 g와 시작 정점 'start'

출력 − 간선을 하나씩 추가하여 완성된 최소 신장 트리(MST)

Begin
    두 개의 집합 B, N을 생성
    시작 노드를 집합 B에 추가

    그래프 g의 모든 정점 u에 대해
        u를 집합 N에 추가
    done

    while B ≠ N do
        min := ∞
        그래프 g의 모든 정점 u에 대해
            if u가 집합 B에 속하면 then
                u에 인접한 모든 정점 v에 대해
                    if v가 (N – B)에 속하면 then
                        if min > uv 간선의 비용 then
                            min := uv 간선의 비용
                            parent := u
                            node := v
                    done
            done
        done

        node를 집합 B에 삽입
        parent에서 node로 향하는 간선을 트리에 추가
    done

    트리 반환
End

동작 원리 요약

집합 B는 이미 MST에 포함된 정점들의 집합이고, N은 그래프의 전체 정점 집합입니다. 매 반복마다 B에 속한 정점과 아직 포함되지 않은 정점(N − B)을 연결하는 간선 중 비용이 가장 작은 것을 선택하여 트리에 추가하고, 해당 정점을 B에 삽입합니다. 모든 정점이 B에 포함되면(B = N) 알고리즘이 종료되며, 이때 만들어진 트리가 곧 최소 신장 트리입니다.

C++ 예제 코드

#include<iostream>
#include<list>
#include<set>
using namespace std;

typedef struct nodes {
    int dest;
    int cost;
}node;

class Graph {
    int n;
    list<node> *adjList;
    private:
        void showList(int src, list<node> lt) {
            list<node> :: iterator i;
            node tempNode;

            for(i = lt.begin(); i != lt.end(); i++) {
                tempNode = *i;
                cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
            }
            cout << endl;
        }

    public:
        Graph() {
            n = 0;
        }

        Graph(int nodeCount) {
            n = nodeCount;
            adjList = new list<node>[n];
        }

        void addEdge(int source, int dest, int cost) {
            node newNode;
            newNode.dest = dest;
            newNode.cost = cost;
            adjList[source].push_back(newNode);
        }

        void displayEdges() {
            for(int i = 0; i<n; i++) {
                list<node> tempList = adjList[i];
                showList(i, tempList);
            }
        }

        friend Graph primsMST(Graph g, int start);
};

set<int> difference(set<int> first, set<int> second) {
    set<int> :: iterator it;
    set<int> res;

    for(it = first.begin(); it != first.end(); it++) {
        if(second.find(*it) == second.end())
            res.insert(*it);     //두 번째 집합에 없는 원소만 추가
    }

    return res;     //집합 (first - second) 반환
}

Graph primsMST(Graph g, int start) {
    int n = g.n;
    set<int> B, N, diff;
    Graph tree(n);          //그래프와 같은 노드 수로 트리 생성
    B.insert(start);        //시작 노드를 집합 B에 삽입

    for(int u = 0; u<n; u++) {
        N.insert(u); //모든 정점을 집합 N에 추가
    }

    while(B != N) {
        int min = 9999;             //무한대로 초기화
        int v, par;
        diff = difference(N, B);    //집합 N - B 계산

        for(int u = 0; u < n; u++) {
            if(B.find(u) != B.end()) {
                list<node>::iterator it;
                for(it = g.adjList[u].begin(); it != g.adjList[u].end(); it++) {
                    if(diff.find(it->dest) != diff.end()) {
                        if(min > it->cost) {
                            min = it->cost;     //비용 갱신
                            par = u;
                            v = it->dest;
                        }
                    }
                }
            }
        }

        B.insert(v);
        tree.addEdge(par, v, min);
        tree.addEdge(v, par, min);
    }
    return tree;
}

main() {
    Graph g(7), tree(7);
    g.addEdge(0, 1, 1);
    g.addEdge(0, 2, 3);
    g.addEdge(0, 3, 4);
    g.addEdge(0, 5, 5);
    g.addEdge(1, 0, 1);
    g.addEdge(1, 3, 7);
    g.addEdge(1, 4, 2);
    g.addEdge(2, 0, 3);
    g.addEdge(2, 4, 8);
    g.addEdge(3, 0, 4);
    g.addEdge(3, 1, 7);
    g.addEdge(4, 1, 2);
    g.addEdge(4, 2, 8);
    g.addEdge(4, 5, 2);
    g.addEdge(4, 6, 4);
    g.addEdge(5, 0, 5);
    g.addEdge(5, 4, 2);
    g.addEdge(5, 6, 3);
    g.addEdge(6, 4, 4);
    g.addEdge(6, 5, 3);

    tree = primsMST(g, 0);
    tree.displayEdges();
}

위 예제에서 정점 번호 0~6은 각각 A~G에 대응되며, 무방향 그래프이므로 각 간선을 양방향으로 두 번씩 추가한 것을 볼 수 있습니다.

실행 결과

Edge: A--B And Cost: 1
Edge: B--E And Cost: 2
Edge: A--C And Cost: 3
Edge: A--D And Cost: 4
Edge: E--F And Cost: 2
Edge: F--G And Cost: 3
Total Cost: 15