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的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。