当前位置：首页 > news >正文

Kruskal和Prim

news 2024/11/13 12:08:26

Kruskal和Prim是两种常用的求解最小生成树（Minimum Spanning Tree, MST）的算法。它们用于在一个加权无向图中找到一棵包含所有顶点且总权重最小的树。

Kruskal算法

介绍：
Kruskal算法采用贪心策略，从小到大选择边，并检查是否形成环。如果形成环，则不选择该边，否则选择该边。Kruskal算法通常使用并查集（Union-Find）来检测环。

步骤：

将所有边按权重从小到大排序。
初始化一个空的最小生成树。
依次选择排序后的边，如果加入该边不形成环，则将该边加入最小生成树。
当最小生成树包含所有顶点时，算法结束。

特点：

适用于稀疏图（边较少）。
时间复杂度为O(E log E)，其中E为边的数量。

#include <stdio.h>
#include <stdlib.h>#define V 4  // 顶点数量// 定义边结构体
typedef struct Edge {int src, dest, weight;
} Edge;// 并查集结构体
typedef struct Subset {int parent, rank;
} Subset;Edge edge[V * (V - 1) / 2];  // 存储所有边
Subset subsets[V];           // 存储所有子集
int E;  // 边的数量// 查找根节点
int find(Subset subsets[], int i) {if (subsets[i].parent != i)subsets[i].parent = find(subsets, subsets[i].parent);return subsets[i].parent;
}// 合并两个子集
void unionSubsets(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 compare(const void *a, const void *b) {return (*(Edge *)a).weight - (*(Edge *)b).weight;
}// Kruskal算法
void kruskalMST(int graph[V][V]) {int i, u, v, w, x, y;Edge result[V];  // 存储最小生成树的边int e = 0;  // 已选择的边数量// 初始化边数组for (i = 0; i < V - 1; i++) {for (j = i + 1; j < V; j++) {if (graph[i][j]) {edge[E].src = i;edge[E].dest = j;edge[E].weight = graph[i][j];E++;}}}// 排序边qsort(edge, E, sizeof(Edge), compare);// 初始化并查集for (i = 0; i < V; i++) {subsets[i].parent = i;subsets[i].rank = 0;}printf("Edge \tWeight\n");for (i = 0; i < E; i++) {u = edge[i].src;v = edge[i].dest;w = edge[i].weight;x = find(subsets, u);y = find(subsets, v);if (x != y) {result[e].src = u;result[e].dest = v;result[e].weight = w;e++;unionSubsets(subsets, x, y);printf("%d - %d \t%d \n", u, v, w);}// 如果最小生成树包含所有顶点，则结束if (e == V - 1)break;}
}int main() {int graph[V][V] = {{0, 2, 0, 6},{2, 0, 3, 8},{0, 3, 0, 5},{6, 8, 5, 0}};kruskalMST(graph);return 0;
}

Prim算法

介绍：
Prim算法也采用贪心策略，从任意一个顶点开始，逐步扩展最小生成树。每次选择权重最小的连接树中顶点和树外顶点的边。Prim算法通常使用优先队列（例如最小堆）来高效选择最小边。

步骤：

从任意一个顶点开始，将其加入最小生成树。
初始化一个优先队列，存储所有连接树中顶点和树外顶点的边。
从优先队列中取出权重最小的边，将对应的顶点加入最小生成树。
更新优先队列，加入新的连接树中顶点和树外顶点的边。
重复步骤3和4，直到最小生成树包含所有顶点。

特点：

适用于稠密图（边较多）。
时间复杂度为O(E log V)，其中E为边的数量，V为顶点的数量。

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>#define V 5  // 顶点数量// 找到最小权重边的索引
int minKey(int key[], bool mstSet[]) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++)if (mstSet[v] == false && key[v] < min)min = key[v], min_index = v;return min_index;
}// 打印最小生成树
void printMST(int parent[], int graph[V][V]) {printf("Edge \tWeight\n");for (int i = 1; i < V; i++)printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}// Prim算法
void primMST(int graph[V][V]) {int parent[V];  // 存储构建的最小生成树int key[V];     // 用于选择最小权重边bool mstSet[V]; // 表示顶点是否包含在最小生成树中// 初始化所有键值为无穷大for (int i = 0; i < V; i++)key[i] = INT_MAX, mstSet[i] = false;// 从第一个顶点开始，键值为0key[0] = 0;parent[0] = -1;  // 第一个顶点是根节点// 构建最小生成树for (int count = 0; count < V - 1; count++) {// 从未处理的顶点中选择键值最小的顶点int u = minKey(key, mstSet);// 将选择的顶点加入最小生成树mstSet[u] = true;// 更新相邻顶点的键值for (int v = 0; v < V; v++)if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])parent[v] = u, key[v] = graph[u][v];}// 打印构建的最小生成树printMST(parent, graph);
}int main() {int graph[V][V] = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};primMST(graph);return 0;
}

区别

驱动方式不同：
- Kruskal算法是边驱动的算法。它首先将所有边按照权重从小到大排序，然后依次选择权值最小的边，如果选择的边不会形成环路，则将其加入生成树中。
- Prim算法是顶点驱动的算法。它从一个初始顶点开始，每次选择距离当前生成树最近的顶点，并将其加入生成树中，直到所有顶点都被加入。
数据结构实现不同：
- Kruskal算法通常使用并查集来检测是否形成环路，以保证生成树的连通性。
- Prim算法通常使用优先队列或最小堆来实现，以快速找到距离当前生成树最近的顶点。
时间复杂度不同：
- Kruskal算法的时间复杂度为O(E log E)，其中E是边的数量，因为它需要对所有边进行排序。
- Prim算法的时间复杂度在稠密图（边数量接近顶点数量的平方）上为O(V^2)，其中V是顶点的数量；在稀疏图（边数量远小于顶点数量的平方）上，Prim算法的时间复杂度可以优化到O(E log V)。
适用场景不同：
- Kruskal算法更适合处理稀疏图，因为其时间复杂度与边的数量相关，而稀疏图的边数量相对较少。
- Prim算法更适合处理稠密图，因为其时间复杂度不受边的数量的影响。