최소신장트리

사요·2021년 12월 2일
MST알고리즘크루스칼프림
1

알튜비튜

목록 보기
15/16

모든 사진 자료에 관한 출처는 아래 알튜비튜 - 튜터링에 있음을 밝힙니다.
https://github.com/Altu-Bitu/Notice

최소 신장 트리 (MST)

  • 하나의 그래프로 만들 수 있는 트리들을 신장트리 (Spanning Tree)라고 부름
  • 신장 트리 중 간선의 가중치 합이 가장 작은 트리가 최소 신장 트리
  • MST를 구하는 알고리즘으로는 크루스칼, 프림이 있음

크루스칼

  • 유니온 파인드 알고리즘을 이용해 MST를 구하는 알고리즘

  • 유니온 파인드에서 같은 집합이라면 사이클이 발생한다면 점을 이용

  • 가중치가 가장 작은 간선부터 선택하며 사이클이 발생하지 않는다면 트리에 포함

  • 유니온 파인드의 시간 복잡도가 O(1)에 가깝기 때문에 간선을 정렬하는 시간 복잡도만 고려.

  • 간선이 많지 않을 때 주로 사용

  • 간선의 수를 E라고 할때, 시간 복잡도는 O(ElogE) .

크루스칼 기본 원리 및 과정

간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까? (그리디식접근)

: 일단 모든 노드를 최대한 적은 비용으로 연결만 시키면 되기 때문에 모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 제일 적은 간선부터 차근차근 그래프에 포함시킨다. 이때 간선을 포함시켰을때 사이클을 형성한다면 해당 간선을 포함하지 않는다. 사이클 판단 여부에는 유니온파인드 알고리즘을 활용한다.

: 위 그림은 7-8 간선을 MST에 포함시킬지 말지 판단하는 과정이다. 우선 간선 7-8을 포함시켰을때 사이클이 발생하는지 여부를 판단하기 위해 유니온파인드 알고리즘을 사용한다. 정점 7의 부모는 3 정점 8의 부모 또한 3이다. 따라서 두 정점은 이미 같은 집합에 속해있으므로 7-8을 연결하면 사이클이 형성된다. 따라서 7-8 간선은 포함시키지 않고 다음 최소 비용을 가진 간선으로 차례를 넘긴다.

[구현코드]

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>


/*
MST 구하기 - VER.kruskal
가장 작은 가중치를 가진 간선부터 더해나가는 그리디식 알고리즘.
해당 간선을 추가했을때 사이클이 발생하지 않는 다면 트리에 포함.
사이클 발생여부는 유니온 파인드 알고리즘을 활용.
*/

using namespace std;
typedef tuple<int, int, int> tp; //u->v를 연결하는 가중치 w의 간선을 (w,u,v)로 저장

vector<int> parent;

//Find 연산
int findParent(int node) {
    if (parent[node] < 0) //값이 음수면 루트 정점
        return node; // 입력한 node가 속한 집합의 representative node가 자기자신이므로 그대로 반환.
    return parent[node] = findParent(parent[node]); //그래프 압축하며 루트 정점 찾기
}

//Union 연산 -> 사이클 발생 여부 판단.
bool unionInput(int x, int y) {
    int xp = findParent(x);
    int yp = findParent(y);

    if (xp == yp) //같은 집합에 있다면 유니온 할 수 없음(왜냐하면 사이클이 발생)
        return false;
    if (parent[xp] < parent[yp]) { // xp 집합의 크기가 yp집합보다 크다면 ( 크기를 음수로 저장하므로 부등호는 반대) 
        parent[xp] += parent[yp]; //새로운 루트 xp
        parent[yp] = xp; // 집합yp에 속했던 정점들이 모두 집합 xp에 속하도록 갱신됨.
    }
    else { // xp 집합의 크기가 yp집합보다 작다면
        parent[yp] += parent[xp]; //새로운 루트 yp
        parent[xp] = yp; // 집합xp에 속했던 정점들이 모두 집합 yp에 속하도록 갱신됨.
    }
    return true;
}

//kruskal
int kruskal(int v, priority_queue<tp, vector<tp>, greater<>>& pq) { // v : 정점 개수.
    int cnt = 0, sum = 0;

    while (cnt < v - 1) { //사용한 간선의 수가 v-1보다 작을 동안 ( MST에서 간선수는 항상 정점수-1개)
        int weight = get<0>(pq.top());
        int x = get<1>(pq.top());
        int y = get<2>(pq.top());
        pq.pop();

        if (unionInput(x, y)) { //유니온이 가능하다면 (= 사이클이 발생하지 않는다면)
            cnt++; //사용한 간선 하나 추가
            sum += weight; // 전체의 가중치 합 더함.
        }
    }
    return sum;
}

int main() {
    int v, e, a, b, c;
    priority_queue<tp, vector<tp>, greater<>> pq; //가장 작은 가중치를 지닌 간선을 뺴오기 위한 방법으로 벡터 저장해서 정렬하기 or 우선순위 큐 사용하기

    //입력
    cin >> v >> e;
    parent.assign(v + 1, -1); //parent[i]는 i의 부모정점 저장.
    while (e--) {
        cin >> a >> b >> c;
        pq.push({ c, a, b });
    }

    //연산 & 출력
    cout << kruskal(v, pq);
}

프림

  • 특정 정점에서 시작하여 접근할 수 있는 정점 중 가중치가 가장 작은 정점을 우선으로 접근
  • 시작점으로부터의 누적거리를 고려하는 다익스트라와 달리 간선 자체의 가중치만 고려
  • 시작점이 특별하게 주어진 경우에 주로 사용
  • 시간 복잡도는 다익스트라와 같은 O(VlogV+ElogV) (prioirity queue에서 min heap을 활용할 경우)
  • 가중치가 가장 작은 정점을 구하는 방식 (우선순위큐, 단순배열, 피보나치힙)에 따라 logV 부분의 시간복잡도는 변화할 수 있음.

프림 기본 원리 및 과정

MST에 포함되는 정점 - MST에 포함되지 않는 정점들 사이를 잇는 간선 중 가중치가 최소인 간선을 찾아서 MST에 포함시키자!

과정 :

  1. 임의의 start 정점을 하나 선택하여 우선순위 큐에 넣는다.

  1. 우선순위 큐에서 정점을 하나 꺼낸다.

    (우선순위에 의해 비용이 가장 작은 정점이 우선순위 큐를 빠져나온다.)

    Q. 프림 알고리즘에서 우선순위큐말고 그냥 큐를 쓰면 결과가 달라질까? 비용이 가장 작은 정점을 꺼내오는 이유는 무엇일까?

  2. 우선순위 큐에서 꺼낸 정점이 이미 방문한 정점이라면, 다시 우선순위 큐에서 새로운 정점을 꺼낸다.

  1. 우선순위 큐에서 꺼낸 정점이 아직 방문하지 않은 정점이라면, 방문처리를 하고 정점의 비용을 더한다.
  1. 위의 정점과 연결된 다른 정점들 중 방문하지 않은 정점들의 정보를 우선순위 큐에 넣음
  1. 우선순위 큐가 비어있을 때까지 2~5번 과정을 반복

: 위 그림은 우선순위 큐에서 2번정점을 꺼냈을때의 상황이다. dist[i]는 i정점을 MST에 포섭(?)시키는데 든 비용이 저장되어있다. 2번 정점과 연결된 모든 정점(3,4)들을 확인하여 미방문 정점이면서 더 짧은 간선을 통해 갈 수 있다면 dist 배열을 각각 dist[3]=9, dist[4]=9 로 갱신시킨다. 그리고 해당 정점의 가중치를 갱신시키고 우선순위큐에 넣는다.

[구현코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
const int INF = 1e6;
typedef pair<int, int> ci; // 가중치 w와 연결된 정점v 를 (w,v)로저장

int prim(int v, int start, vector<vector<ci>>& graph) { // v: 정점 수. start : 시작정점 

    int sum = 0; // 비용(가중치)총 합


    // 가중치 총 합만 리턴하면 되므로 dist배열은 필요하지 x
   vector<int> dist(v + 1, INF); //각 정점까지의 비용 (없어도 상관없으나, 사용하면 메모리를 좀 더 아낄 수 있음)
    vector<bool> visited(v + 1, false); //정점 방문 여부 (다익스트라와 달리 프림에선 필요!)
    priority_queue<ci, vector<ci>, greater<>> pq;

    //초기화
    dist[start] = 0;
    pq.push({ 0, start }); // 가중치, 정점

    while (!pq.empty()) {


        //가중치가 가장 적은 정점을 빼옴.
        int weight = pq.top().first; //간선 가중치
        int node = pq.top().second; //현재 정점
        pq.pop();

        if (visited[node]) //이미 확인했던 정점
            continue;
        sum += weight; //MST 간선 가중치 총 합에 더해줌
        visited[node] = true; //방문 처리

        for (int i = 0; i < graph[node].size(); i++) { //연결된 모든 node확인.
            int next_node = graph[node][i].first;
            int next_weight = graph[node][i].second;

            if (!visited[next_node] && next_weight< dist[next_node] ) { //미방문 정점(이면서 더 짧은 간선을 통해 갈 수 있다면)
                dist[next_node] = next_weight;
                pq.push({ next_weight, next_node }); // 가중치 갱신
            }
        }
    }
    return sum;
}

int main() {
    int v, e, a, b, c;

    //입력
    cin >> v >> e;
    vector<vector<ci>> graph(v + 1, vector<ci>(0));
    while (e--) { //무방향 그래프이므로 쌍방으로 저장.
        cin >> a >> b >> c;
        graph[a].emplace_back(b, c); //a ->b . 를 잇는 가중치 c의 간선
        graph[b].emplace_back(a, c); //b ->a . 를 잇는 가중치 c의 간선
    }

    //연산 & 출력
    cout << prim(v, 1, graph);
}

마무리

  • 그래프에서 만들 수 있는 모든 트리를 신장트리라고 칭함
  • 그 중 간선의 가중치 총 합이 가장 작은 트리가 최소 신장 트리(MST)
  • MST를 구하는 알고리즘은 크루스칼, 프림이 있음
  • 크루스칼은 유니온 파인드 알고리즘을 활용하고, 프림은 다익스트라와 유사
  • 간선이 적다면 크루스칼, 간선이 많거나 시작정점이 주어지면 프림
profile
사요
하루하루 나아가는 새싹 개발자 🌱
이전 포스트

트리

다음 포스트

위상정렬

0개의 댓글