Prim算法可以搜索赋权图中的最小生成树，这也是ACM、面试、考研的热门话题。我们来详细看看Prim (prim)算法求最小生成树的思路，并用C语言举例说明。
Prim算法思想：
从任意顶点v0开始，选择最近的顶点v1形成树T1，然后将与T1最近的顶点v2连接起来形成树T2，重复该过程，直到所有顶点都在树中。
最小生成树：权重最小的生成树。
生成树和最小生成树的应用：连接N个城市需要N-1条边线。边上的重量可以解释为线的成本。最小生成树代表最小化其成本的生成树。
网络的最小生成树必须解决以下两个问题：
1.尽可能选择权重小的边，但不能形成环；
2.选择N-1条合适的边来连接N个顶点；
MST性质：设g=(v，e)是连通网络，U是顶点v的非空子集，若(U，v)是具有最小权的边，其中uU，v v-u，必有包含边(U，v)的最小生成树。
Prim算法假设G=(v，e)是连通的，TE是G上最小生成树中的边的集合，算法从u={u0} (u0 v)和te={}开始。重复以下操作：
在uU，v v-u的所有边(U，v)E中，找出权重最小的边(u0，v0)合并到集合TE中，而v0合并到U中，直到v=u。
此时TE中必有n-1条边，T=(V，TE)是g的最小生成树。
Prim算法的核心：始终保持TE中的边集形成生成树。
注：prim算法适用于稠密图，其时间复杂度为O (n 2)，与边数无关，而kruskal算法的时间复杂度为O(eloge)，与边数有关，因此适用于稀疏图。
举一个简单的例子来说明具体的实现方法：
g:图，用邻接矩阵表示
Vcount:表示图形的顶点数。
Max _ vertexes:图中节点的最大数量
无限：无限
数组存储从0开始。
由于最小生成树包含每个顶点，所以顶点是否被选中可以直接用数组标记为已用[max _ vertices]；(我们这里直接使用程序代码中的变量定义，这样比较好理解)；当一个数组被选中，然后标记它。现在，有一个问题，如何选择最小的加权边。注意这里对最小加权边有限制，边的一个顶点必须在选中的顶点中，另一个顶点当然在未选中的顶点集中。我的第一个想法是穷举搜索，即在一个集合中选择一个顶点，在另一个集合中寻找最小值。虽然很容易理解，但显然效率不是很高。严为民的《数据结构》提供了更好的解决方案：设置两个辅助数组，低成本[max _ vertices]和闭集[max _ vertices]，低。对于每个顶点v v-u，闭集ge [v]，闭集[max _ vertices]记录u中边所附着的顶点。
Prim算法步骤：
T0存储生成树的边，初始值为空。
输入加权图的加权邻接矩阵C=(Cij)nn(若两点无边界，则其大小为无穷大)。
为每个顶点v添加一个属性L(v):从表v到T0的最小直接距离。
(1) T0，V1={v0}，C(T0)=0
(2)对于任意v V，L(v)C(v，v0)
(3)如果V==V1，则停止，否则转到下一步。
(4)在V-V1中求一点U使得L (U)=min {L (V) | V (VV1)}，记住在V1中与U相邻的点是w .
(5)T0T0{(u，w)}，C(T0) C(T0) C(u，w)，V1V1{ u }
(6)对任意v (VV1)若c (v，u) l (v)则l (v)=c (v，u)否则l (v)不变。
(7)转到3。
c实现示例
prim.txt中的内容：
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
5 6 6
4 6 2
程序代码：
#includestdo.h
#includestring.h
#包含stdlib.h
# Define finity 1000000//定义两个不直接相邻的顶点之间的距离。
# Define max _ vertexs 6//定义图形中的顶点数
typedef int Graph[max _顶点][max _顶点]；//侧面的重量
void prim(Graph G，int vcount，int father[])
{
int i，j，k；
int低成本[max _ vertexs]；//最小代价边上的权值
int closeset[max _ vertex]，used[max _ vertex]；//依附在U中的顶点；标记是否已被选中
int min
int result=0；//记录最短距离权值的和
for(I=0；ivcounk ) //初始化所有数组，把最短距离初始化为其他顶点到一结点的距离
{
低成本[I]=G[0][I]；
闭集[I]=0；
已用[I]=0；
父亲[I]=-1；
}
已用[0]=1;
for(I=1；I=vcount-1；我)
{
j=0；
最小值=无穷大；
for(k=1；kcountk ) //for循环得到离结点最近的顶点j
如果((!已用)(低成本[k]
{
最小值=低成本[k]；
j=k；
}
父[j]=闭集[j]；
printf('%d %d\n '，j 1，father[j]1)；//输出当前找到的结点，该顶点依附的上一个结点
result=result G[j][closeset[j]]；
已用[j]=1；//把第j个顶点并入了U中
for(k=1；k
如果(!已用[k](G[j][k]保留到k的最短路径
{
低成本[k]=G[j][k]；
闭集[k]=j；
}
}
printf('%d '，结果);
}
int main()
{
文件* fr
int i，j，权重；
图表g；
int fat赫尔[max _ vertex]；
for(I=0；imax _顶点；我)
for(j=0；jmax _ vertexer我)
G[i][j]=无穷大；
fr=fopen('prim.txt '，' r ')；
如果(!fr)
{
printf('fopen失败\ n’)；
出口(1);
}
while(fscanf(fr，' %d%d%d '，I，j，weight)！=EOF)
{
G[i-1][j-1]=重量；
G[j-1][i-1]=重量；
}
prim(G，max _顶点，胖赫尔)；
返回0;
}
测试的结果如下：
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。