数据结构之最小生成树Prim算法
134 浏览量
2023-12-25
14:06:09
上传
评论
收藏 82KB PDF 举报
数据结构之最⼩⽣成树数据结构之最⼩⽣成树Prim算法算法
普⾥姆算法介绍普⾥姆算法介绍
普⾥姆（Prim）算法，是⽤来求加权连通图的最⼩⽣成树算法
基本思想：对于图G⽽⾔，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U⽤于存放G的最⼩⽣成树中的顶点，T存放G的
最⼩⽣成树中的边。 从所有uЄU，vЄ(V-U) (V-U表⽰出去U的所有顶点)的边中选取权值最⼩的边(u, v)，将顶点v加⼊集合U中，将边(u, v)加
⼊集合T中，如此不断重复，直到U=V为⽌，最⼩⽣成树构造完毕，这时集合T中包含了最⼩⽣成树中的所有边。
代码实现代码实现
1. 思想逻辑思想逻辑
（1）以⽆向图的某个顶点（A）出发，计算所有点到该点的权重值，若⽆连接取最⼤权重值#define INF (~(0x1<<31))
（2）找到与该顶点最⼩权重值的顶点（B），再以B为顶点计算所有点到改点的权重值，依次更新之前的权重值，注意权重值为0或⼩
于当前权重值的不更新，因为1是⼀当找到最⼩权重值的顶点时，将权重值设为了0，2是会出现⽆连接的情况。
（3）将上述过程⼀次循环，并得到最⼩⽣成树。
2. Prim算法算法
// Prim最⼩⽣成树
void Prim(int nStart)
{
int i = 0;
int nIndex=0; // prim最⼩树的索引，即prims数组的索引
char cPrims[MAX]; // prim最⼩树的结果数组
int weights[MAX]; // 顶点间边的权值
cPrims[nIndex++] = m_mVexs[nStart].data;
// 初始化"顶点的权值数组"，
// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
for (i = 0; i < m_nVexNum; i++)
{
weights[i] = GetWeight(nStart, i);
}
for (i = 0; i < m_nVexNum; i ++)
{
if (nStart == i)
{
continue;
}
int min = INF;
int nMinWeightIndex = 0;
for (int k = 0; k < m_nVexNum; k ++)
{
if (weights[k]!= 0 && weights[k] < min)
{
min = weights[k];
nMinWeightIndex = k;
}
}
// 找到下⼀个最⼩权重值索引
cPrims[nIndex++] = m_mVexs[nMinWeightIndex].data;
// 以找到的顶点更新其他点到该点的权重值
weights[nMinWeightIndex]=0;
int nNewWeight = 0;
for (int ii = 0; ii < m_nVexNum; ii++)
{
nNewWeight = GetWeight(nMinWeightIndex, ii);
// 该位置需要特别注意
if (0 != weights[ii] && weights[ii] > nNewWeight)
{
weights[ii] = nNewWeight;
}
}
}
// 计算最⼩⽣成树的权重值
int nSum = 0;
资源评论
