ㅏ 최소 스패닝 트리 (MST) 로 정의된다 스패닝 트리 가능한 모든 스패닝 트리 중에서 최소 가중치를 갖는 트리
ㅏ 스패닝 트리 그래프의 모든 정점을 포함하는 연결된 무방향 그래프의 트리형 하위 그래프로 정의됩니다. 또는 Layman의 표현을 빌리자면 트리를 형성하는 그래프 가장자리의 하위 집합입니다( 비순환 ) 여기서 그래프의 모든 노드는 트리의 일부입니다.
최소 스패닝 트리는 스패닝 트리의 모든 속성을 가지며, 가능한 모든 스패닝 트리 중에서 가능한 최소 가중치를 갖는다는 추가 제약 조건을 갖습니다. 스패닝 트리와 마찬가지로 그래프에 대해 가능한 MST가 많을 수도 있습니다.
스패닝 트리의 속성:
스패닝 트리는 아래에 언급된 원칙 :
- 꼭짓점 수( 안에 ) 그래프와 스패닝 트리는 동일합니다.
- 스패닝 트리에는 총 정점 수보다 1 적은 고정된 수의 가장자리가 있습니다( 그리고 = V-1 ).
- 스패닝 트리는 다음과 같습니다. 연결이 끊어진 , 즉 구성 요소의 소스는 하나만 있어야 하며 그 이상은 없어야 합니다.
- 스패닝 트리는 다음과 같아야 합니다. 비순환, 어느 트리에 순환이 없다는 의미입니다.
- 스패닝 트리의 총 비용(또는 가중치)은 스패닝 트리의 모든 간선 가중치의 합으로 정의됩니다.
- 그래프에는 여러 개의 스패닝 트리가 있을 수 있습니다.
최소 스패닝 트리:
ㅏ 최소 스패닝 트리 (MST) 로 정의된다 스패닝 트리 가능한 모든 스패닝 트리 중에서 최소 가중치를 갖습니다.
최소 스패닝 트리는 스패닝 트리의 모든 속성을 가지며, 가능한 모든 스패닝 트리 중에서 가능한 최소 가중치를 갖는 추가 제약 조건을 갖습니다. 스패닝 트리와 마찬가지로 그래프에 대해 가능한 MST가 많을 수도 있습니다.
- 위 예시 그래프의 MST를 살펴보겠습니다.
최소 스패닝 트리
최소 스패닝 트리를 찾는 알고리즘:
주어진 그래프에서 최소 스패닝 트리를 찾는 몇 가지 알고리즘이 있으며 그 중 일부는 아래에 나열되어 있습니다.
Kruskal의 최소 스패닝 트리 알고리즘:
이는 연결된 무방향 그래프에서 최소 스패닝 트리를 찾는 데 널리 사용되는 알고리즘 중 하나입니다. 이것은 먼저, 그래프의 모든 모서리를 가중치별로 정렬합니다.
이 알고리즘은 그래프의 연결된 구성 요소를 추적하기 위해 DSU(Disjoint-Set) 데이터 구조를 사용하여 효율적으로 구현될 수 있습니다. 이는 네트워크 설계, 클러스터링, 데이터 분석 등 다양한 실무 응용 분야에서 사용됩니다.
기사를 따르십시오. Kruskal의 최소 스패닝 트리 알고리즘 알고리즘에 대한 더 나은 이해와 구현을 위해.
Prim의 최소 스패닝 트리 알고리즘:
이것도 그리디 알고리즘이다. 이 알고리즘에는 다음과 같은 작업 흐름이 있습니다.
- 임의의 정점을 선택한 다음 이를 MST에 추가하는 것으로 시작됩니다.
- 그런 다음 MST의 한 정점을 아직 MST에 없는 다른 정점에 연결하는 최소 가장자리 가중치를 반복적으로 확인합니다.
- 이 과정은 모든 정점이 MST에 포함될 때까지 계속됩니다.
각 반복에 대한 최소 가중치 가장자리를 효율적으로 선택하기 위해 이 알고리즘은 Priority_queue를 사용하여 현재 최소 가장자리 가중치로 정렬된 정점을 저장합니다. 또한 저장 중인 데이터 유형을 고려하여 적합한 배열 또는 기타 데이터 구조를 사용하여 MST를 동시에 추적합니다.
이 알고리즘은 색상, 질감 또는 기타 기능을 기반으로 한 이미지 분할과 같은 다양한 시나리오에서 사용할 수 있습니다. 라우팅의 경우 배달 트럭이 따라갈 수 있는 두 지점 사이의 최단 경로를 찾는 것과 같습니다.
기사를 따르십시오. Prim의 최소 스패닝 트리 알고리즘 이 알고리즘을 더 잘 이해하고 구현하기 위해.
스리데비
Boruvka의 최소 스패닝 트리 알고리즘:
이는 연결된 무방향 그래프의 최소 스패닝 트리를 찾는 데 사용되는 그래프 순회 알고리즘이기도 합니다. 이것은 가장 오래된 알고리즘 중 하나입니다. 알고리즘은 그래프의 각 꼭지점을 자체 트리로 시작하여 최소 스패닝 트리를 반복적으로 구축하는 방식으로 작동합니다. 각 반복에서 알고리즘은 트리를 다른 트리에 연결하는 가장 저렴한 가장자리를 찾고 해당 가장자리를 최소 스패닝 트리에 추가합니다. 이는 최소 스패닝 트리를 찾는 Prim의 알고리즘과 거의 유사합니다. 알고리즘에는 다음과 같은 작업 흐름이 있습니다.
- 그래프의 각 정점을 자체 트리로 사용하여 나무 숲을 초기화합니다.
- 포리스트의 각 나무에 대해 다음을 수행합니다.
- 다른 나무에 연결하는 가장 저렴한 가장자리를 찾으십시오. 최소 스패닝 트리에 이러한 간선을 추가합니다.
- 추가된 가장자리로 연결된 나무를 병합하여 숲을 업데이트합니다.
- 포리스트에 최소 확장 트리인 하나의 트리만 포함될 때까지 위 단계를 반복합니다.
알고리즘은 우선순위 큐와 같은 데이터 구조를 사용하여 구현되어 트리 사이에서 가장 저렴한 가장자리를 효율적으로 찾을 수 있습니다. Boruvka의 알고리즘은 최소 스패닝 트리를 찾는 간단하고 구현하기 쉬운 알고리즘이지만, 모서리가 많은 큰 그래프의 경우 다른 알고리즘만큼 효율적이지 않을 수 있습니다.
기사를 따르십시오. Boruvka의 최소 스패닝 트리 알고리즘 이 알고리즘을 더 잘 이해하고 구현하기 위해.
최소 스패닝 트리(Minimum Spanning Tree)의 속성과 특성에 대해 자세히 알아보려면 여기.
최소 스패닝 트리의 응용:
- 네트워크 설계 : 스패닝 트리는 네트워크 설계에서 모든 노드를 연결하는 데 필요한 최소 연결 수를 찾는 데 사용할 수 있습니다. 특히 최소 스패닝 트리는 가장 저렴한 간선을 선택하여 연결 비용을 최소화하는 데 도움이 될 수 있습니다.
- 이미지 처리 : 스패닝 트리는 이미지 처리에서 유사한 강도나 색상의 영역을 식별하는 데 사용할 수 있으며 이는 분할 및 분류 작업에 유용할 수 있습니다.
- 생물학 : 스패닝 트리와 최소 스패닝 트리는 생물학에서 종이나 유전자 간의 진화 관계를 나타내는 계통수를 구성하는 데 사용될 수 있습니다.
- 소셜 네트워크 분석 : 스패닝 트리와 최소 스패닝 트리는 소셜 네트워크 분석에서 개인이나 그룹 간의 중요한 연결과 관계를 식별하는 데 사용될 수 있습니다.
MST의 인기 있는 면접 문제
| 1. | 모든 도시를 연결하는 데 필요한 최소 비용 찾기 | 관행 |
최소 스패닝 트리에 대한 몇 가지 FAQ:
1. 주어진 그래프에 대해 여러 개의 최소 신장 트리가 있을 수 있습니까?
예, 동일한 최소 총 가중치를 갖는 여러 간선 세트가 있는 경우 그래프에는 여러 개의 최소 스패닝 트리가 있을 수 있습니다.
2. Kruskal 알고리즘과 Prim 알고리즘을 유방향 그래프에 사용할 수 있나요?
아니요. Kruskal의 알고리즘과 Prim의 알고리즘은 무방향 그래프용으로만 설계되었습니다.
3. 연결이 끊긴 그래프가 최소 스패닝 트리를 가질 수 있나요?
아니요, 연결이 끊긴 그래프는 모든 정점에 걸쳐 있지 않기 때문에 스패닝 트리를 가질 수 없습니다. 따라서 최소 스패닝 트리도 가질 수 없습니다.
4. Dijkstra 알고리즘을 사용하여 최소 신장 트리를 찾을 수 있습니까?
아니요, Dijkstra의 알고리즘은 가중치 그래프에서 두 정점 사이의 최단 경로를 찾는 데 사용됩니다. 최소 스패닝 트리를 찾도록 설계되지 않았습니다.
5. Kruskal과 Prim 알고리즘의 시간 복잡도는 얼마입니까?
Kruskal과 Prim의 알고리즘은 모두 다음과 같은 시간 복잡도를 갖습니다. 오(ElogE) , 여기서 E는 그래프의 간선 수입니다.