Kruskal의 최소 스패닝 트리 알고리즘 - C++의 탐욕 알고리즘

스패닝 트리는 모든 정점을 연결하는 방향성 무방향 그래프 하위 그래프입니다. 그래프에는 스패닝 트리가 많이 있을 수 있습니다. 각 그래프의 최소 스패닝 트리(MST)는 다른 모든 스패닝 트리와 동일하거나 작은 가중치를 갖습니다. 스패닝 트리의 가장자리에 가중치가 할당되고 그 합은 각 가장자리에 할당된 가중치입니다. V는 그래프의 정점 수이므로 최소 스패닝 트리는 간선 수(V - 1)를 가지며, 여기서 V는 간선 수입니다.

Kruskal 알고리즘을 사용하여 최소 스패닝 트리를 찾습니다

• 모든 모서리는 가중치를 기준으로 내림차순이 아닌 순서로 정렬되어야 합니다.

• 가장 작은 면을 선택하세요. 루프가 형성되지 않으면 가장자리가 포함됩니다.

• 스패닝 트리에 (V-1) 모서리가 생길 때까지 2단계를 수행해야 합니다.

이 경우 탐욕스러운 접근 방식을 사용하라는 지시를 받습니다. 그리디 옵션은 가중치가 가장 작은 모서리를 선택하는 것입니다. 예를 들어 이 그래프의 최소 스패닝 트리는 (9-1)= 8개의 모서리입니다.

After sorting:

Weight  Src    Dest
21       27    26
22       28    22
22       26    25
24       20    21
24       22    25
26       28    26
27       22    23
27       27    28
28       20    27
28       21    22
29       23    24
30       25    24
31       21    27
34       23    25

이제 정렬을 기반으로 모든 가장자리를 선택해야 합니다.

루프가 형성되지 않았기 때문에 가장자리 26-27->가 포함됩니다.

루프가 형성되지 않았기 때문에 가장자리가 28-22->를 포함합니다.

루프가 형성되지 않았기 때문에 가장자리 26-25->를 포함합니다.

Edge 20-21->는 루프가 형성되지 않았기 때문에 포함되었습니다.

Edge 22-25->는 루프가 형성되지 않았기 때문에 포함되었습니다.

Edge 28-26-> 루프 형성으로 인해 삭제

Edge 22-23-> > 루프가 형성되지 않아 포함됨

Edge 27-28-> 루프 형성으로 인해 삭제

Edge 20 -27->포함 루프가 형성되지 않았기 때문에

Edge 21-22->루프가 형성되었기 때문에 폐기

Edge 23-24->루프가 형성되지 않았기 때문에 포함

에지 개수가 (V-1)이므로 알고리즘은 여기서 끝납니다.

Example

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Edge {
   int src, dest, weight;
};
struct Graph {
   int V, E;
   struct Edge* edge;
};
struct Graph* createGraph(int V, int E){
   struct Graph* graph = (struct Graph*)(malloc(sizeof(struct Graph)));
   graph->V = V;
   graph->E = E;
   graph->edge = (struct Edge*)malloc(sizeof( struct Edge)*E);
   return graph;
}
struct subset {
   int parent;
   int rank;
};
int find(struct subset subsets[], int i){
   if (subsets[i].parent != i)
      subsets[i].parent
   = find(subsets, subsets[i].parent);
   return subsets[i].parent;
}
void Union(struct subset subsets[], int x, int y){
   int xroot = find(subsets, x);
   int yroot = find(subsets, y);
   if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
   else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
   else{
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
   }
}
int myComp(const void* a, const void* b){
   struct Edge* a1 = (struct Edge*)a;
   struct Edge* b1 = (struct Edge*)b;
   return a1->weight > b1->weight;
}
void KruskalMST(struct Graph* graph){
   int V = graph->V;
   struct Edge
   result[V];
   int e = 0;
   int i = 0;
   qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
   struct subset* subsets
   = (struct subset*)malloc(V * sizeof(struct subset));
   for (int v = 0; v < V; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
   }
   while (e < V - 1 && i < graph->E) {
      struct Edge next_edge = graph->edge[i++];
      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);
      if (x != y) {
         result[e++] = next_edge;
         Union(subsets, x, y);
      }
   }
   printf("Following are the edges in the constructed MST\n");
   int minimumCost = 0;
   for (i = 0; i < e; ++i){
      printf("%d -- %d == %d\n", result[i].src,
      result[i].dest, result[i].weight);
      minimumCost += result[i].weight;
   }
   printf("Minimum Cost Spanning tree : %d",minimumCost);
   return;
}
int main(){
   /* Let us create the following weighted graph
   30
   0--------1
   | \       |
   26| 25\ |15
   | \ |
   22--------23
   24 */
   int V = 24;
   int E = 25;
   struct Graph* graph = createGraph(V, E);
   graph->edge[0].src = 20;
   graph->edge[0].dest = 21;
   graph->edge[0].weight = 30;
   graph->edge[1].src = 20;
   graph->edge[1].dest = 22;
   graph->edge[1].weight = 26;
   graph->edge[2].src = 20;
   graph->edge[2].dest = 23;
   graph->edge[2].weight = 25;
   graph->edge[3].src = 21;
   graph->edge[3].dest = 23;
   graph->edge[3].weight = 35;
   graph->edge[4].src = 22;
   graph->edge[4].dest = 23;
   graph->edge[4].weight = 24;
   KruskalMST(graph);
   return 0;
}

Output

Following are the edges in the constructed MST
22 -- 23 == 24
20 -- 23 == 25
20 -- 21 == 30
Minimum Cost Spanning tree : 79

결론

이 튜토리얼에서는 Kruskal의 최소 스패닝 트리 알고리즘(Greedy 방법 및 C++ 코드)을 사용하여 이 문제를 해결하는 방법을 보여줍니다. 이 코드를 Java, Python 및 기타 언어로 작성할 수도 있습니다. 크루스칼(Kruskal)의 개념을 모델로 한 것이다. 이 프로그램은 주어진 그래프에서 가장 짧은 스패닝 트리를 찾습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.

위 내용은 Kruskal의 최소 스패닝 트리 알고리즘 - C++의 탐욕 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!