最小生成树算法
最新回答
浪居酒家
2026-07-07 10:28:23
最小生成树是一个包含所有顶点的树，且所有边的权值之和最小。图中可能存在多棵最小生成树，但它们的权值之和相同。
Prim算法是一种加点法，从已选节点中选择一个未选节点，该节点与已选节点之间存在一条权值最小的边，即所有已选节点和未选节点间的边中权值最小的边。若存在多个权值相同边，则任选一条。
从任意节点开始，Prim算法可以得到最小生成树。例如，以节点A为起点，连接至A的边中权值最小的边AB，将B添加至树中。接着，从已选节点A、B中选择权值最小的边BD连接至D。然后，选择权值最小的边AC连接至C。最后，选择权值最小的边ED连接至E。至此，得到最小生成树。
Kruskal算法是选边法，将所有边按权值从小到大排序，每次选取权值最小的边，同时保证该边不会与已选边构成回路。重复此过程直至所有节点均被选入，此时选边和节点构成最小生成树。
如图所示，首先选择权值最小的边AB，然后选择权值最小的边EF，接着选择权值最小的边BC，再选择权值最小的边AD，直至所有节点被选入，形成最小生成树。
在Prim算法的实现中，首先将节点存储在一个数组中，定义edge数组表示当前已选节点与未选节点之间的最小边。edge数组初始化为第一个节点到其余节点的边。接下来按照Prim算法逻辑，在未选节点中选择一个与已选节点间最小边的节点。
Prim算法实现代码如下：
c
// Prim算法实现
void prim(int n, int graph[][MAX], int parent[], int dist[], bool mstSet[])
{
// 初始化dist数组和mstSet数组
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX, mstSet[i] = false;
}
// 从任意节点开始
dist[0] = 0;
parent[0] = -1;
for (int count = 0; count < n - 1; count++) {
// 找到未加入树中且与已加入树中节点距离最短的节点
int u = findMin(dist, mstSet);
// 将当前节点加入到树中
mstSet[u] = true;
// 更新与当前节点相邻且距离最小的未加入树中节点的距离
for (int v = 0; v < n; v++)
if (graph[u][v] && !mstSet[v] && graph[u][v] < dist[v])
parent[v] = u, dist[v] = graph[u][v];
}
}
Kruskal算法实现代码如下：
c
// Kruskal算法实现
void kruskal(int n, int graph[][MAX], int parent[], int rank[])
{
// 初始化并查集
for (int i = 0; i < n; i++)
parent[i] = i;
// 按权值排序边
sort(graph, graph + n * n);
int edgeCount = 0, treeCount = n;
int mstWeight = 0;
// 遍历排序后的边，选取权值最小且不构成回路的边
for (int i = 0; i < n * n; i++) {
int u = find(parent, graph[i][0]), v = find(parent, graph[i][1]);
if (u != v) {
// 将边加入最小生成树
mstWeight += graph[i][2];
merge(parent, rank, u, v);
edgeCount++;
}
// 检查是否构成最小生成树
if (edgeCount == n - 1)
break;
}
// 输出最小生成树权值
printf("Minimum Spanning Tree Weight: %d\n", mstWeight);
}
// 查找并查集中的代表节点
int find(int parent[], int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent, parent[i]);
}
// 合并两个集合
void merge(int parent[], int rank[], int x, int y) {
if (rank[x] < rank[y])
parent[x] = y;
else if (rank[x] > rank[y])
parent[y] = x;
else {
parent[y] = x;
rank[x]++;
}
}
以上是Prim算法和Kruskal算法的简要介绍与基本实现。
热门标签
