C++/ 최소 스패닝 트리, Kruskal & Prim algorithm

Spanning Tree (신장 트리) 란

그래프 내의 모든 정점을 포함하는 트리이며, 사이클을 포함해서는 안되는 트리이다.

사이클을 포함하지 않기 때문에 n개의 정점이 존재하면 간선의 개수는 n-1개이다.

Minimum Spanning Tree (최소 신장 트리, MST)

Spanning Tree 중에서 간선의 가중치 합이 최소인 트리를 일컫는다.

-> 네트워크에 있는 모든 정점들을 가장 적은 수, 최소 비용의 간선으로 연결하는 트리를 말한다.

이런 MST를 구현하는데에 잘 알려진 알고리즘으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다.

 

Kruskal MST Algorithm

그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 가는 방식의 알고리즘.

(단순히 추가하는 것이 아닌 사이클을 만들지 않기 위한 조건도 추가해야 함.)

 

노드 방문 여부를 확인하기 위해 Disjoint set을 이용하는 것이 일반적이다.

노드를 방문해가며 추가하는 것이 아닌 단순히 최소값의 간선을 연결시키는 방식이기 때문!

 

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;
unf[10001];
struct Edge{
    int v1;
    int v2;
    int val;
    Edge(int a, int b, int c){
        v1=a;
        v2=b;
        val=c;
    }
    bool operator<(Edge &b){
        return val<b.val;
    }
};

int Find(int v){
    if(v==unf[v]) return v;
    else return unf[v]=Find(unf[v]);
}

Void Union(int a, int b){
    a=Find(a);
    b=Find(b);
    if(a!=b) unf[a]=b;
}
int main(){
    vector<Edge> Ed;
    int i,n,m,a,b,c, cnt=0, res=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        unf[i]=i;
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&a,&b,&c);
        Ed.push_back(Edge(a,b,c));
    }
    Ed.sort(Ed.begin(),Ed.end());

    for(i=0;i<m;i++){ //sort했기 때문에 가중치 오름차순으로 정렬.
        int fa=Find(Ed[i].v1);
        int fb=Find(Ed[i].v2);
        if(fa!=fb){ //이미 연결된 노드들이 아니라면 가중치 더한 후Union.
            res+=Ed[i].val;
            Union(Ed[i].v1, Ed[i].v2);
        }
    }
    printf("%d",res);
    return 0;
}

 

 

 

 

 

 

 

산발적으로 만들어진 트리의 간선들을 합쳐 스패닝 트리를 만드는 크루스칼과 달리,

프림 알고리즘에서는 하나의 시작점으로 구성된 트리에 간선을 하나씩 추가하며 스패닝 트리를 키워간다.

(선택된 간선들은 중간 과정에서도 항상 스패닝 트리를 이루게 됨)

 

이러한 프림 알고리즘의 구현은 Min Priority Queue를 사용해 이루어진다.

Queue에 어떤 한 정점을 추가하고, 방문하지 않은 노드이면 pop 이후 가중치를 더한다.

이후 그 정점에 연결된 모든 노드들을 Queue에 추가하는 방식이다.

 

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int ch[30];
struct Edge{
    int e;
    int val;
    Edge(int a, int b){
        e=a;
        val=b;
    }
    bool operator<(const Edge &b)const{
        return val>b.val; //최소힙으로 리턴.
    }
};
int main(){
    priority_queue<Edge> Q;
    vector<pair<int, int> > map[30];
    int i, n, m, a, b, c, res=0;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d %d %d", &a,&b,&c);
        map[a].push_back(make_pair(b,c));
        map[b].push_back(make_pair(a,c));
    }
    Q.push(Edge(1,0));
    while(!Q.empty()){
        Edge tmp=Q.top();
        Q.pop();
        int v=tmp.e;
        int cost=tmp.val;
        if(ch[v]==0){
            res+=cost;
            ch[v]=1;
            for(i=0;i<map[v].size();i++){
                Q.push(Edge(map[v][i].first, map[v][i].second));
            }
        }
    }
    printf("%d",res);
    return 0;
}

 

1.  최소힙으로 리턴하기 위해 Edge Struct를 구성. Edge에는 꺼내진 정점과 연결된 노드와 그 가중치가 저장될것이다.

 

2. 방문 여부는 ch 배열로 간단하게 작성

 

3. pair 자료형을 담는 벡터에 노드와 간선 정보를 담는다. 무방향 그래프이기 때문에 양방향으로 넣어준다.

 

4. Q에 첫 정점인 1과 가중치 0 을 집어 넣고 시작.

 

5. 빈 큐가 될 때까지 (연결된 노드가 없을 때까지) 루프를 돌며 가장 작은 값의 가중치를 갖는 간선을 더하고, 연결된 정점을 다시 큐에 넣는 것을 반복한다.

 

 

 

두 알고리즘 모두 복잡하지 않은 알고리즘이다.

아직 자료구조가 익숙치 않아서 코드로 연습을 더해봐야겠다!!