1. 최소스패닝트리 알고리즘

(= MST, 최소신장트리)

• 스패닝 트리란

  • 그래프의 모든 정점이 연결 되어있다.
    (= 연결그래프)
  • 사이클이 존재하지 않는다. 트리라고 볼 수 있다.
    (= 트리는 사이클이 없는 그래프)
  • 한 그래프에서 스패닝 트리는 여러 개 나올 수 있다.
    (원본 그래프는 무방향, 사이클 존재, 모든 정점이 연결 되어있다.)

최소스패닝트리란 스패닝트리 중에서
가중치의 합이 최소가 되는 트리를 찾는 문제 유형이다.

가장 핵심인 부분은 어떻게 사이클이 없는 스패닝트리를 구하는가이다.

1-1. 크루스칼 O(ElgE)

https://www.acmicpc.net/problem/1922

• 무방향그래프에서만 사용 가능 / 음수가중치 상관없음 /
  Greedy / Union-Find

A.설명

• 크루스칼은 모든 간선의 가중치를 오름차순으로 정렬하고,
  작은 간선부터 하나씩 추가해 나간다. (Greedy)
• 추가하다가 사이클이 생긴다면, 해당 간선은 추가하지 않는다.
• 그렇게 모든 간선을 추가하면 끝.
• 사이클이 존재하는지 판단하기 위해 Union-Find방식 사용
• Union-Find 방식으로 정점의 부모를 설정하고,
  확인시 부모가 같다면, 사이클이 형성된다고 판단, 연결하지 않는다.
• 추가로 무방향(=양방향) 그래프이지만, 한 번만 추가한다.
  그 이유는, 한 정점을 기준으로 다르게 보는 것이 아니라
  간선 자체를 기준으로 보기 때문이다.
  (프림은 두 번 connection을 추가해야한다.)

B. 전형적인 구현 방식

자료구조
1. 사이클을 확인하기 위한 부모 배열
int parent[1001]
2. 연결을 담을 벡터.
cost, u, v 순서고, cost를 맨 앞에 둔 이유는
크루스칼에 따라 간선을 오름차순 정렬하기 위함.
vector<pair<int, pair<int, int>>> connection

구현법
1. 우선 Union-Find 함수 3개를 구현한다.

• getParent
  • 가장 이해하기 힘든 부분
  • 현재 한 점의 루트노드를 반환.
  • 루트노드를 찾기 위해 재귀가 일어나는데,
    재귀가 되며, 부모를 루트노드로 수정해나감.
• unionParent
  • getParent로 2개의 정점 a, b의 루트노드를 가져오고,
    둘의 루트노드가 다르다면, a의 parent를 b로 설정한다.
  • void 형이라 반환 없다.
• findParent
  • a와 b의 루트노드를 가져오고,
    둘의 루트노드가 같다면, true, 다르다면 false를 반환.

2. 연결을 받고, sort를 통해 간선을 오름차순 정렬
3. parent 배열은 parent[i] = i로 본인은 본인으로 초기화
4. 크루스칼 - 1번만 제대로 구현했다면 아래처럼 간단.

• 뽑은 간선을 추가하면 사이클이 생길지 확인한다.

if (!findParent(from, to)) // 루트가 달라 사이클이 없다면,
{
	result += cost;
	unionParent(from, to);
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int V, E;
int parent[1001];
vector<pair<int, pair<int, int>>> connection; // 가중치, u, v (가중치 기준 오름차순)

int getParent(int num) 
{
    // 가장 루트노드라면, 루트노드를 반환.
	if (num == parent[num]) return num;

    // 루트 노드가 아니라면, 루트가 나올 때까지 재귀호출함.
    // 재귀호출을 하며, 본인의 부모도 루트노드로 만들어감.
	return parent[num] = getParent(parent[num]);
}

// a와 b의 parent가 다르다면, a의 부모를 b로 둔다.
// (b의 부모를 a로 두어도 상관없다)
void unionParent(int a, int b) 
{
	a = getParent(a);
	b = getParent(b);

	if (a != b) parent[a]= b;
}

// a와 b의 parent가 같은지 비교
bool findParent(int a, int b) 
{
	a = getParent(a);
	b = getParent(b);

	if (a == b) return true;
    else        return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> V >> E;
    
    // 연결 입력
    for(int i=0; i<E; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;

        connection.push_back({w, {u,v}});
    }

    // 1 가중치 기준 오름차순
    sort(connection.begin(), connection.end()); 

    // 2 일단 본인의 부모는 본인으로 초기화
    for(int i=1;i<=V;i++)
    {
        parent[i] = i;
    }

    // 3 크루스칼
    int result = 0; // 트리의 가중치
    for(int i=0; i<E; i++)  // 작은 간선부터 끝까지 뽑는다
    {
        int cost = connection[i].first;
        int from = connection[i].second.first;
        int to = connection[i].second.second;

        // 뽑고서 두 정점의 parent가 다르다면, (find)
        // 사이클이 없으므로 비용을 추가하고, 둘의 parent를 같게 만듦 (union)
        if (!findParent(from, to)) 
        {
			result += cost;
			unionParent(from, to);
		}
    }
    // 그렇게 모든 간선을 오름차순으로 방문하면 결과가 나옴
    cout << result;

    return 0;   
}

C. 경로 찾기

MST는 굳이 경로를 찾지 않는 듯..?
어짜피 모두 연결되어있고, 순서라는 것이 의미가 없으니까

C. 사이클이 있는지 확인

크루스칼에서 같은 조상인지 확인하는 것으로 체크했다.

if (!findParent(from, to)) // 루트가 달라 사이클이 없다면,
{
	result += cost;
	unionParent(from, to);
}

1-2. 프림 O(ElgE)

https://www.acmicpc.net/problem/1922

• 무방향그래프에서만 사용 가능 / 음수가중치 안됨

A.설명

• 프림은 현재 갈 수 있는 간선들 중에서 가장 짧은 간선을 추가해 나간다.
• 간선을 추가하면, 해당 정점은 방문 표시를 한다.
• 추가해야하는 간선의 양쪽 정점이 모두 방문 표시가 되었다면,
  사이클이 생기는 경우이므로 추가하지 않는다.
• 그렇게 모든 정점이 방문 될 때까지 반복.
  (모든 정점의 방문을 확인한다기 보다는, 그냥 V-1번만 반복하는 것)
• 프림은 connection을 양방향에 맞게 2번 추가해야 한다.

B. 전형적인 구현 방식

자료구조
1. 연결을 담을 벡터. 가중치와 다음 점이 담긴다.
vector<pair<int, int>> connection[100001]

		connection[u].push_back({v, w});
		connection[v].push_back({u, w});

2. 프림의 핵심 자료구조. cost, next_node를 오름차순으로.
   priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int >>> pq

구현법
1. 연결을 저장 - 점을 기준으로 탐색해야하므로 양방향 저장
2. 시작점에 대한 visited와 간선들을 추가.
3. 프림

• V-1번 반복하게 된다.
• pq에서 하나씩 빼낸다.
• 이 때, 다음 점이 방문한 점이라면,
  • continue
• 그렇지 않다면,
  • cost 추가 / visited=true / cnt ++
  • 다음 점과 연결된 간선들을 추가

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

using namespace std;

int V, E;
vector<pair<int, int>> connection[100001];
bool visited[100001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> V >> E;

    // 연결 - 양방향
    for (int i = 0; i < E; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;

        connection[u].push_back({w, v});
        connection[v].push_back({w, u});
    }

    // 프림의 핵심 자료구조. {cost, next_node}
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // 암묵적으로 1부터 시작.
    int result = 0;
    visited[1] = true;

    // 시작점에 대한 간선들을 미리 모두 넣음.
    for (auto n : connection[1])
    {
        pq.push({n.first, n.second});   // 비용, 다음 정점
    }

    // 프림 V-1번만 반복 = V개를 연결하는데, 시작점은 포함되어있기 때문.
    int cnt = 0;
    while (cnt < V-1)
    {
        int cost = pq.top().first;
        int next = pq.top().second;
        pq.pop();

        // 1 간선의 다음이 방문한 점이라면, 스킵.
        if (visited[next])
        {
            continue;
        }

        // 2 간선의 다음이 방문하지 않은 점이라면,

        // cost 추가 / 다음 점을 true / cnt를 ++
        result += cost;
        visited[next] = true;
        cnt++;

        // 3 다음점과 연결된 간선들의 목록을 추가.
        for (auto n : connection[next])
        {
            if(!visited[n.second])
            {
                pq.push({n.first, n.second});
            }
        }
    }
    cout << result;

    return 0;
}

C. 사이클이 있는지 확인

프림 알고리즘 자체에서
현재 간선의 다음 정점의 visited가 true라면
사이클이 생길 것이라고 판단하여 생략했다.

현재 간선의 현재 정점은, 알고리즘에 따라
이미 visited가 true가 된 정점이다.

따라서 간선의 양쪽 점의 방문이 이미 true라면 추가하지 않게 된다.

다 하고서 아래 문제 직접 풀어보기
https://www.acmicpc.net/problem/1197