Skip to content

Latest commit

 

History

History
192 lines (157 loc) · 5.54 KB

README.md

File metadata and controls

192 lines (157 loc) · 5.54 KB
Raw

Minimum Spanning Tree

최소 신장 트리(MST)

  • 신장 트리(Spanning Tree)

    • 트리는 사이클이 없는 무방향 그래프(Undirected Acyclic Connected Graph)
    • 트리 T가 그래프 G의 모든 정점을 포함하는 부분 그래프이자 트리라면, T는 G의 신장 트리
    • 트리의 성질에 의해 그래프의 정점이 V개라면, 신장 트리는 V-1 개의 간선을 갖게 됨

  • 최소 신장 트리(Minimum Spanning Tree)

    • 신장 트리 중에서 간선의 합이 최소인 트리
    • 신장 트리를 구할 수 있는 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 있음

MST

크루스칼 알고리즘(Kruskal's algorithm)

  • 간선의 비용을 오름차순으로 정렬해 가장 낮은 비용의 간선을 선택
  • 선택한 간선의 두 정점이 같은 그룹이라면 다음 간선을 선택하고, 그렇지 않다면 두 정점을 같은 그룹으로 묶은 뒤 해당 간선을 최소 신장 트리에 추가함
  • 최소 신장 트리에 추가된 간선의 개수가 V-1 개가 될 때까지 위 과정 반복
  • 시간복잡도는 O(E log E)

kruskal1

kruskal2

연습문제

#include <bits/stdc++.h>

using namespace std;

int find(int);
void merge(int, int);

vector<int> parent, level;

int main(void) 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int v, e;
    cin>>v>>e;
    parent=vector<int>(v+1);
    level=vector<int>(v+1,1);
    for (int i = 0; i<=v; ++i) {
        parent[i]=i;
    }
    vector<pair<int, pair<int, int>>> edge(e);
    for (int i = 0; i<e; ++i) {
        cin>>edge[i].second.first>>edge[i].second.second>>edge[i].first;
    }
    sort(edge.begin(),edge.end());
    
    int cnt = 0;
    int res = 0;
    for (int i = 0; i<e; ++i) {
        int cost = edge[i].first;
        int v1 = edge[i].second.first;
        int v2 = edge[i].second.second;

        if (find(v1)==find(v2)) {
            continue;
        }
        merge(v1,v2);
        res+=cost;
        ++cnt;
        if (cnt==v-1) {
            break;
        }
    }
    cout << res;

    return 0;
}

int find(int u)
{
    if (u==parent[u]) {
        
        return u;
    }

    return parent[u]=find(parent[u]);
}

void merge(int u, int v)
{
    u=find(u); 
    v=find(v); 
    if (u==v) {
        
        return; 
    }
    if (level[u]>level[v]) {
        swap(u,v); 
    }
    parent[u]=v;
    if (level[u]==level[v]) {
        ++level[v]; 
    }

    return;
}

프림 알고리즘(Prim's algorithm)

  • 임의의 정점을 선택해 최소 신장 트리에 추가하고, 해당 정점과 연결된 모든 간선을 heap에 추가함
  • heap에서 비용이 가장 작은 간선을 꺼냄
    • 만약 해당 간선이 최소 신장 트리에 포함되어 있는 두 정점을 연결한다면 다음 간선을 꺼냄
    • 만약 해당 간선이 최소 신장 트리에 포함되어 있는 정점 u와 포함되지 않은 정점 v를 연결한다면, v를 최소 신장 트리에 추가함
  • 최소 신장 트리에 추가된 간선의 개수가 V-1 개가 될 때까지 위 과정 반복
  • 시간복잡도는 O(E log E)

prim1

prim2

prim3

연습문제

#include <bits/stdc++.h>

using namespace std;

int main(void) 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int v, e;
    cin>>v>>e;
    vector<vector<pair<int, int>>> adj_list(v+1);
    for (int i = 1; i<=e; ++i) {
        int a, b, c;
        cin>>a>>b>>c;
        adj_list[a].push_back({c,b});
        adj_list[b].push_back({c,a});
    }

    // cost, u, v
    priority_queue<pair<int, pair<int, int>>,
        vector<pair<int, pair<int, int>>>,
        greater<pair<int, pair<int, int>>>> pq;
    vector<bool> is_used(v+1);
    is_used[1]=true;
    for (auto next : adj_list[1]) {
        pq.push({next.first,make_pair(1,next.second)});
    }

    int cnt = 0;
    int res = 0;
    while (1) {
        auto cur = pq.top();
        pq.pop();

        int cost = cur.first;
        // int v1 = cur.second.first; // optional
        int v2 = cur.second.second;
        if (is_used[v2]) {
            continue;
        }

        is_used[v2]=true;
        res+=cost;
        ++cnt;
        if (cnt==v-1) {
            break;
        }
        for (auto next : adj_list[v2]) {
            if (!is_used[next.second]) {
                pq.push({next.first,make_pair(v2,next.second)});
            }
        }
    }
    cout << res;
    
    return 0;
}
이전 - Disjoint-set 목록 다음 - Floyd-Warshall