최소 스패닝 트리 알고리즘 (크루스칼, 프림)

최소 스패닝 트리(Minimum Spanning Tree, MST)

그래프의 모든 정점을 사이클이 존재하지 않도록 연결했을 때, 간선의 가중치의 합이 최소인 트리

특징

1. 무방향 그래프
2. 하나의 그래프에서 최소 스패닝 트리는 여러개일 수 있다.
3. 간선의 개수는 N-1개이다

---

크루스칼(Kruskal) 알고리즘

가중치가 낮은 간선일수록 최소 스패닝 트리에 포함될 가능성이 클 것이다.

이런 점을 이용하여 그래프의 모든 간선을 오름차순으로 정렬 후 사이클이 생기지 않도록 트리에 하나씩 추가해보는 알고리즘이다.

사이클을 확인할 때는 유니온 파인드를 이용한다.

알고리즘 구조

// 1. 모든 간선을 우선순위 큐에 넣어 오름차순으로 정렬
sturct cmp {
	bool operater()(Edge& e1, Edge& e2) {
		return e1.cost > e2.cost;
	}
};

priority_queue<Edge, vector<Edge>, cmp> pq;

// 2. 부모를 자기 자신으로 초기화 하기 
vector<int> parent(V + 1); 
for (int i = 1; i <= V; i++) parent[i] = i;

while(count != V - 1)(
	// 3. 우선순위큐에서 가중치가 가장 낮은 간선 꺼내기
	Edge edge = pq.top();
	pq.pop();

	// 4. 두 정점이 이미 연결되어 있는 경우 연결하면 사이클이 된다
	if(find(edge.start) == find(edge.end)) continue;
	
	// 5. 연결되어 있지 않다면 두 정점을 하나의 그룹으로 합치기
	merge(edge.start, edge.end);

	// 6. 현재 간선을 최소 스패닝 트리에 추가
	mst.push_back(edge);

	count ++;
}

int find(int a) {
	if(parent[a] == a) return a;
	return parent[a] = find(parent[a]); // 메모이제이션으로 저장해야한다!
}

void merge(int a, int b) {
	int pa = find(a);
	int pb = find(b);
	parent[pb] = pa; // 한쪽의 부모에 따르기
}

---

프림(Prim) 알고리즘

크루스칼 알고리즘은 산발적으로 만들어진 간선들을 모아 트리를 완성했다.

프림 알고리즘은 하나의 시작점에서 가중치가 작은 간선을 추가해가며 트리를 완성하는 방식이다.

이미 만들어진 트리에 인접한 간선을 확인하며 연결하는 것이다.

알고리즘 구조

****//**** 1. 아무 정점를 선택하여 시작
pq.push({start, 0}); // 시작정점, 가중치

while(!pq.empty()) {
	// 2. 우선순위 큐에서 하나씩 꺼내기
	pair<int, int> cur = pq.top();
	pq.pop();

	// 4. 이미 방문한 정점인지 체크
	if(visited[cur.first]) continue; 
	 	
	// 5. 방문하지 않았다면 트리와 연결
  visited[cur.first] = true;

	// 6. 현재 정점과 연결된 간선을 큐에 넣기
	for(int i=0; i< adj[cur.first].size(); i++) {
		pq.push(adj[cur.first][i]);
	}
}