采用普利姆算法和克鲁斯卡尔算法求最小生成树

### 普利姆算法和克鲁斯卡尔算法实现最小生成树的步骤及代码示例 #### 1. 普利姆算法（Prim Algorithm） 普利姆算法的核心思想是从图中的任意一个顶点开始，逐步将与当前树相邻的权值最小的边加入到树中，直到所有顶点都被包含在树中为止。以下是其实现步骤： - 初始化：选择任意一个顶点作为起始点，将其加入到最小生成树中。 - 构造过程：从当前树的所有相邻边中，选择一条权值最小且未被选择的边，并将其对应的顶点加入到树中。 - 终止条件：当所有顶点都被加入到树中时，算法结束。 下面是使用C语言实现普利姆算法的代码示例： ```c #include <stdio.h> #include <limits.h> #define V 5 // 图的顶点数 int minKey(int key[], int mstSet[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) { if (mstSet[v] == 0 && key[v] < min) { min = key[v]; min_index = v; } } return min_index; } void printMST(int parent[], int graph[V][V]) { printf("Edge Weight\n"); for (int i = 1; i < V; i++) { printf("%d - %d %d \n", parent[i], i, graph[i][parent[i]]); } } void primMST(int graph[V][V]) { int parent[V]; int key[V]; int mstSet[V]; for (int i = 0; i < V; i++) { key[i] = INT_MAX; mstSet[i] = 0; } key[0] = 0; parent[0] = -1; for (int count = 0; count < V - 1; count++) { int u = minKey(key, mstSet); mstSet[u] = 1; for (int v = 0; v < V; v++) { if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) { parent[v] = u; key[v] = graph[u][v]; } } } printMST(parent, graph); } ``` #### 2. 克鲁斯卡尔算法（Kruskal Algorithm） 克鲁斯卡尔算法的核心思想是按照边的权值从小到大排序，依次选择权值最小的边加入到最小生成树中，同时确保不会形成回路。为此，通常使用并查集来判断两个顶点是否已经连通。以下是其实现步骤： - 边排序：将图中的所有边按照权值从小到大进行排序。 - 并查集初始化：为每个顶点分配一个独立的集合。 - 边选择：依次遍历排序后的边，如果该边连接的两个顶点不属于同一个集合，则将该边加入到最小生成树中，并合并这两个顶点所在的集合。 - 终止条件：当选择了 `V-1` 条边时，算法结束。 下面是使用C语言实现克鲁斯卡尔算法的代码示例： ```c #include <stdio.h> #include <stdlib.h> struct Edge { int src, dest, weight; }; struct Graph { int V, E; struct Edge* edge; }; 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"); for (i = 0; i < e; ++i) printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight); } ``` ###