minimum spanning tree tutorial
이 C ++ 자습서에서는 그래프 및 응용 프로그램에서 MST를 찾기위한 Prim 및 Kruskal의 알고리즘과 함께 최소 스패닝 트리 (MST)가 무엇인지 설명합니다.
스패닝 트리는 가능한 최소 가장자리를 포함하고 순환이없는 모든 정점으로 구성된 그래프의 하위 집합으로 정의 할 수 있습니다. 스패닝 트리는 연결을 끊을 수 없습니다.
모든 연결 및 무 방향 그래프에는 하나 이상의 스패닝 트리가 있습니다. 연결이 끊어진 그래프에는 모든 정점을 포함 할 수 없으므로 스패닝 트리가 없습니다.
=> 전체 C ++ 자습서 목록을 탐색하려면 여기를 참조하십시오.
학습 내용 :
C ++의 스패닝 트리
다음 연결된 그래프를 고려하십시오.
위와 같이 3 개의 정점이 포함 된 연결된 그래프에 대해 3 개의 스패닝 트리가 있습니다. 일반적으로 N이 그래프의 노드 수이면 완전한 연결된 그래프의 최대 값은 N입니다.N-2스패닝 트리의 수. 따라서 위의 그래프에서 N = 3, 따라서 3(3-2)= 3 개의 스패닝 트리.
스패닝 트리의 일부 속성은 다음과 같습니다.
- 연결된 그래프에는 스패닝 트리가 둘 이상있을 수 있습니다.
- 그래프의 모든 스패닝 트리에는 동일한 수의 노드와 간선이 있습니다.
- 스패닝 트리에서 하나의 가장자리를 제거하면 최소한의 연결 그래프의 연결이 끊어집니다.
- 반면에 스패닝 트리에 하나의 가장자리를 추가하면 최대 비순환 따라서 루프를 생성합니다.
- 스패닝 트리에는 루프 나 순환이 없습니다.
최소 스패닝 트리 (MST) 란?
최소 스패닝 트리는 연결된 가중치 그래프의 다른 모든 스패닝 트리 중에서 최소 가중치를 포함하는 트리입니다. 그래프에 대해 둘 이상의 최소 스패닝 트리가있을 수 있습니다.
그래프에서 최소 스패닝 트리를 찾는 데 사용되는 가장 인기있는 두 가지 알고리즘이 있습니다.
여기에는 다음이 포함됩니다.
- Kruskal의 알고리즘
- Prim의 알고리즘
이 두 알고리즘에 대해 논의 해 보겠습니다!
Kruskal의 알고리즘
Kruskal의 알고리즘은 연결된 그래프에서 MST를 찾는 알고리즘입니다.
Kruskal의 알고리즘은 다음과 같은 그래프 G의 하위 집합을 찾습니다.
- 그것은 모든 정점을 가진 나무를 형성합니다.
- 가중치의 합은이 그래프에서 형성 할 수있는 모든 스패닝 트리 중 최소값입니다.
Kruskal 알고리즘의 단계 순서는 다음과 같습니다.
- 먼저 가장 낮은 가중치에서 가장 높은 것까지 모든 가장자리를 정렬합니다.
- 가장 낮은 무게로 가장자리를 잡고 스패닝 트리에 추가하십시오. 사이클이 생성되면 에지를 폐기하십시오.
- 모든 정점이 고려 될 때까지 1 단계와 같이 가장자리를 계속 추가합니다.
Kruskal의 알고리즘을위한 의사 코드
다음은 Kruskal의 알고리즘에 대한 의사 코드입니다.
이제 Kruskal의 알고리즘 그림을 보겠습니다.
이제 우리는 최소 가중치가 2-4 인 모서리를 선택합니다.
다음으로 가장 짧은 가장자리 2-3을 선택합니다.
그런 다음 가장 짧은 에지를 가진 다음 에지를 선택하고 이는 사이클을 생성하지 않습니다.
크롬을위한 최고의 무료 광고 차단기는 무엇입니까
다음 단계는 순환을 형성하지 않도록 가장 짧은 가장자리를 선택하는 것입니다. 이것은 0-1입니다.
보시다시피 모든 정점을 다루었으며 여기에 최소 비용으로 스패닝 트리가 있습니다.
다음으로 C ++를 사용하여 Kruskal의 알고리즘을 구현합니다.
#include #include #include using namespace std; #define graph_edge pair class Graph { private: int V; // number of nodes in graph vector> G; // vector for graph vector> T; // vector for mst int *parent; public: Graph(int V); void AddEdge(int u, int v, int wt); int find_set(int i); void union_set(int u, int v); void kruskal_algorithm(); void display_mst(); }; Graph::Graph(int V) { parent = new int(V); for (int i = 0; i 산출:
Kruskal의 알고리즘에 따른 최소 스패닝 트리 (MST) :
가장자리 : 무게
2-4 : 1
2-3 : 2
0-1 : 3
0-3 : 3
위의 Kruskal 알고리즘 그림에서 사용한 것과 동일한 예제 그래프를 프로그램에서 사용했습니다. 이 구현에서는 두 개의 벡터를 사용합니다. 하나는 그래프를 저장하고 다른 하나는 최소 스패닝 트리를 저장합니다. 가중치가 가장 적은 모서리를 재귀 적으로 찾아 모든 정점이 덮일 때까지 MST 벡터에 추가합니다.
Prim의 알고리즘
Prim의 알고리즘은 그래프 트리에 걸친 최소값을 찾는 또 다른 알고리즘입니다. 그래프 가장자리로 시작하는 Kruskal의 알고리즘과 달리 Prim의 알고리즘은 꼭지점으로 시작합니다. 하나의 정점으로 시작하여 모든 정점이 덮일 때까지 최소한의 가중치로 가장자리를 계속 추가합니다.
Prim의 알고리즘의 단계 순서는 다음과 같습니다.
- 임의의 정점을 시작 정점으로 선택하고 최소 스패닝 트리를 초기화합니다.
- 다른 정점에 연결되는 가장자리를 찾습니다. 가중치가 최소 인 모서리를 찾아 스패닝 트리에 추가합니다.
- 스패닝 트리를 얻을 때까지 2 단계를 반복합니다.
Prim의 알고리즘을위한 의사 코드
이제 Prim의 알고리즘에 대한 그림을 보겠습니다.
이를 위해 Kruskal 알고리즘 그림에서 사용한 것과 동일한 예제 그래프를 사용합니다.
노드 2를 임의의 정점으로 선택하겠습니다.
다음으로 2에서 가중치가 가장 적은 모서리를 선택합니다. 모서리 2-4를 선택합니다.
다음으로, 아직 스패닝 트리에없는 다른 정점을 선택합니다. 우리는 가장자리 2-3을 선택합니다.
이제 위의 정점에서 가중치가 가장 적은 가장자리를 선택하겠습니다. 가중치가 가장 적은 모서리 3-0이 있습니다.
다음으로 정점 0에서 가중치가 가장 적은 가장자리를 선택합니다. 이것이 가장자리 0-1입니다.
위의 그림에서 우리는 이제 그래프의 모든 정점을 다루고 최소 비용으로 완전한 스패닝 트리를 얻었음을 알 수 있습니다.
이제 Prim의 알고리즘을 C ++로 구현해 보겠습니다.
이 프로그램에서도 위의 예제 그래프를 입력으로 사용하여 프로그램에서 제공 한 출력을 그림과 비교할 수 있습니다.
프로그램은 다음과 같습니다.
#include #include using namespace std; #define INF 9999 // graph contains 5 vertices #define V 5 // an array G that stores adjacency matrix for input graph int G(V)(V) = { {0, 3, 0, 3, 0}, {3, 0, 0, 0, 4}, {0, 0, 0, 2, 1}, {3, 3, 2, 0, 0}, {0, 4, 1, 0, 0}}; int main () { int num_edge; // number of edge // mst_vertex - array to track vertices selected for spanning tree int mst_vertex(V); // set selected false initially memset (mst_vertex, false, sizeof (mst_vertex)); // set number of edge to 0 num_edge = 0; //let 0th vertex be the first to be selected mst_vertex(0) = true; int x; // row int y; // col // print details of MST cout<<'The Minimum Spanning Tree as per Prim's Algorithm:'< G(i)(j)) { min = G(i)(j); x = i; y = j; } } } } } cout << x << ' - ' << y << ' : ' << G(x)(y); cout << endl; mst_vertex(y) = true; num_edge++; } return 0; } 산출:
Prim의 알고리즘에 따른 최소 스패닝 트리 :
가장자리 : 무게
0-1 : 3
0-3 : 3
3-2 : 2
2-4 : 1
스패닝 트리의 응용
최소 스패닝 트리의 일부 응용 프로그램은 다음과 같습니다.
# 1) 통신 네트워크 설정 : 통신 링크를 사용하여 통신 네트워크를 설정하려는 경우 두 지점 간의 통신 링크 설정 비용은 MST를 사용하여 가장 잘 결정됩니다.
# 2) 군집 분석 : 최소 스패닝 트리를 찾고 가장 비싼 k-1 개의 에지를 삭제하여 K- 클러스터링 문제를 해결하는 데 사용할 수 있습니다.
# 3) 도로 / 철도 네트워크 배치 : 도시 간 또는 도시 내에 다양한 도로 또는 철도 네트워크를 설치할 때 프로젝트 비용은 매우 중요한 요소입니다. 최소 스패닝 트리를 사용하여 최소 비용으로 최상의 경로를 찾을 수 있습니다.
# 4) 주택 시설 계획 : 전기, 수도, 하수 등과 같은 여러 주택에 공급할 시설도 최적의 비용이 필요하며 이는 MST를 사용하여 이루어집니다.
# 5) 출장 세일즈맨 문제 해결 : MST를 사용하여 각 지점을 한 번 이상 방문해야하는 출장 세일즈맨 문제를 해결할 수 있습니다.
결론
최소 스패닝 트리는 그래프 g의 하위 집합이며이 하위 집합에는 그래프의 모든 정점이 있으며 정점을 연결하는 간선의 총 비용은 최소입니다.
그래프에서 최소 스패닝 트리를 찾기 위해 두 가지 알고리즘, 즉 Kruskal과 Prim을 논의했습니다. 스패닝 트리의 응용 프로그램도이 자습서에서 설명했습니다.
=> 여기에서 최고의 C ++ 교육 자습서를 확인하십시오.
추천 도서
