MST : 그래프의 모든 정점을 연결할 수 있는 최소비용의 트리 만들기
신장트리(Spanning Tree) : 무방향으로 모든 정점을 포함하는 트리
. 깊이우선트리(DFS) 신장트리 : Depth가 높고 길죽하게 생성되는 트리
. 너비우선(BFS) 신장트리 : Depth는 낮지만 넓게 생성되는 트리
구현방법 2가지
1. 크루스칼 알고리즘 : 간선을 하나씩 선택해서 MST를 만듬
a. 최초에 모든 간선을 가중치에 따라 오름차순으로 정렬
b. 간선의 가중치가 낮은 간선을 선택, (Union-Find로 사이클 여부 체크)
c. 모든 간선이 선택될때까지 반복
-> 중간단계에서는 하나의 트리가 아닌 여러개의 트리가 생성되며 최종적으로 하나의 트리로 연결됨
2. 프림 알고리즘 : 하나의 정점에서 연결된 간선들 중에서 가중치가 낮은 간선을 선택하며 MST를 만듬
=> 다익스트라와 비슷 (차이점이 무엇일까???)
a. 임의의 정점을 시작정점으로 선택하여 우선순위 큐에 추가
b. 인접한 정점과 연결된 간선 중 최소 가중치의 간선 선택 (우선순위 큐 활용)
c. 모든 정점이 선택될 때까지 반복
다익스트라와 프림알고리즘 차이
- 다익스트라는 두 정점 사이의 최단거리를 구하는 것
- 프림은 모든 정점을 연결하는 최소비용을 구하는 것
| 1. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다. 2. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다. 3. 프림이 다익스트라를, 다익스트라가 프림을 보장해주지 않는다. -> 최소스패닝트리가 최단경로트리를, 최단경로트리가 최소스패닝트리를 보장하지 않는다 출처 : https://coding-insider.tistory.com/entry/Prim-vs-Dijkstra-%ED%94%84%EB%A6%BC-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EB%B9%84%EA%B5%90 |
백준 1197
문제 : https://www.acmicpc.net/problem/1197
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
풀이 :https://machine-geon.tistory.com/156
[BAEKJOON_1197 - JAVA] 최소 스패닝 트리(MST)
문제 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는..
machine-geon.tistory.com
'IT Tech > Application' 카테고리의 다른 글
| 벨만포드 알고리즘 (0) | 2022.09.17 |
|---|---|
| 트리 : 우선순위 큐 (1) | 2022.09.16 |
| 다익스트라와 관련 알고리즘 : 벨만포드, BFS, 플로이드워셜 (0) | 2022.09.16 |
| 다익스트라 (0) | 2022.09.13 |
| DDD 바운디드 컨텍스트 기반 마이크로서비스 도출 (0) | 2022.02.04 |
