PRIM（Prim’s）算法是一种用于在加权无向图中找到最小生成树的贪心算法。它由Robert C. Prim在1957年提出，是Kruskal算法的另一种实现。本文将详细介绍PRIM算法的工作原理，并使用C语言进行实现，同时分享一些实战技巧。 #define V 5 // 顶点数 int minKey(int key[], int mstSet[]) { for (int v = 0; v < V; v++)
if (key[v] < min && mstSet[v] == 0)
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]]);
}
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; // 初始化第一个顶点的键值为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);
}
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;
}
实战技巧
初始化键值和集合
：在算法开始时，初始化所有顶点的键值为无穷大，并将所有顶点标记为未包含在最小生成树中。
选择最小键值
：在每次迭代中，选择键值最小的顶点，并将其添加到最小生成树中。
更新键值
：在添加顶点到最小生成树后，更新所有未包含顶点的键值，以确保它们始终指向最小生成树中的最短边。
优化性能
：使用邻接矩阵或邻接表来表示图，根据具体情况选择合适的数据结构以提高性能。
通过以上步骤和技巧，您可以有效地使用PRIM算法来找到加权无向图的最小生成树。
PRIM算法概述
PRIM算法的基本思想是从一个顶点开始，逐步增加边，直到所有顶点都被包含在最小生成树中。算法每次选择连接已包含顶点集合和未包含顶点集合的最短边，将其添加到最小生成树中。
算法步骤
选择图中的一个顶点作为起始点，将其加入最小生成树。
从起始点出发，遍历所有未加入最小生成树的顶点，找到连接最小生成树和未包含顶点的最短边。
将找到的最短边添加到最小生成树中，并将对应的顶点加入最小生成树。
重复步骤2和3，直到所有顶点都被包含在最小生成树中。
C语言实现
以下是一个使用C语言实现的PRIM算法示例：
#include
#include
int min = INT_MAX, min_index;