Spanning tree란?
신장 트리, 스패닝 트리 생성 나무 라고 번역되어 쓰이며 노드 간 경로가 오직 하나인 토폴로지이다.
특징
- 모든 정점들의 연결에 끊임이 없어야 한다.
- 간선의 수 + 1 = 정점의 수
단절점, 단절선 구하기 문제 적용
스패팅 트리에서 특정 간선이나 특정 정점을 제거하면 그래프가 2개 이상으로 나뉘어지는 것을 활용하여 단절선과 단절점을 구한다.
11266번: 단절점
첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B
www.acmicpc.net
11400번: 단절선
첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A
www.acmicpc.net
단절점(Articulation Point)와 단절선(Bridge)
하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.다음과 같은 무방향 그래프가 있다고 해봅시
jason9319.tistory.com
MST 란?
Minimum Spanning Tree의 약어로 최소 신장 트리로 번역되어 쓰인다.
어떤 그래프에서 신장 트리를 구한다고 했을 때 구해진 신장 트리 중 가장 연결 비용이 적은 신장 트리를 MST리고 한다.
Kruskal 알고리즘
- 탐욕적 방법을 이용하여 MST를 구하는 알고리즘이다.
- 가장 비용이 적은 간선(edge)를 탐욕적으로 선택하여 MST를 구한다.
- 간선 기준 탐색
Prim 알고리즘
- 신장트리 집합을 단계적으로 확장시켜 MST를 구하는 알고리즘
- 정점 기준 탐색
Reference
https://jason9319.tistory.com/119
http://www.ktword.co.kr/test/view/view.php?m_temp1=3444
'ps' 카테고리의 다른 글
| [백준] B1395 스위치 - 느리게 갱신되는 세그먼트 트리 (0) | 2023.10.31 |
|---|---|
| 최대공약수 구하기 (0) | 2023.04.25 |
| [프로그래머스] 고고학 최고의 발견 (0) | 2023.02.16 |
| [프로그래머스] 등대 (0) | 2023.02.16 |
| [프로그래머스] 퍼즐 조각 채우기 (0) | 2023.02.14 |
