﻿ 最小生成树算法之Prim算法-C 语言_软件编程-脚本宝典

# 最小生成树算法之Prim算法

## 最小生成树算法之Prim算法

1.什么是最小生成树算法？

2.Prim算法的步骤是什么？

a.假定图的顶点集合为V，边集合为E.
b.初始化点集合U={u}.//u为V中的任意选定的一点
c.从u的邻接结点中选取一点v使这两点之间的权重最小,然后将v加入集合U中.
d.从结点v出发，重复c步骤，直到V={}.

3.举个例子来说明Prim算法的步骤：

4.Prim算法的具体C语言编程实现：

?

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374 `#include``#include``#include``const` `int` `Max =0x7fffffff;``const` `int` `N=50;`` ` `int` `n;``int` `g[N][N],dis[N],visited[N];`` ` `int` `prim()``{``  ``int` `i,j;``  ``int` `pos,min;``  ``int` `ans=0;``  ``memset``(visited,0,``sizeof``(visited));``  ``visited[1]=1;pos=1;``  ``//assign a value to the dis[N] first``  ``for``(i=2;i<=n;i++)``    ``dis[i]=g[pos][i];``  ``for``(i=1;idis[j])``      ``{``        ``min=dis[j];``        ``pos=j; ``      ``}``    ``}``    ``printf``(``"The node being traversed is :%d\n"``,pos);``    ``ans+=min;``    ``printf``(``"The value of ans is %d\n"``,ans);``    ``//mark the node``    ``visited[pos]=1;``    ``//update the weight``    ``for``(j=1;j<=n;j++)``      ``if``(visited[j]==0&&dis[j]>g[pos][j])``        ``dis[j]=g[pos][j];``  ``}``  ``return` `ans;``}`` ` `int` `main()``{``  ``int` `i=1,j=1;``  ``int` `ans=0;``  ``int` `w;``  ``printf``(``"Please enter the number of the nodes:\n"``);``  ``scanf``(``"%d"``,&n);``  ``for``(i=1;i<=n;i++)``    ``for``(j=1;j<=n;j++)``    ``{``      ``if``(i==j)``        ``g[i][j]=0;``      ``else``        ``g[i][j]=Max;``    ``}``  ``printf``(``"Please enter the number of the edges:\n"``);``  ``int` `edgenum;``  ``scanf``(``"%d"``,&edgenum);``  ``int` `v1,v2;``  ``printf``(``"Please enter the number and the corresponding weight:\n"``);``  ``for``(i=1;i<=edgenum;i++)``  ``{``    ``scanf``(``"%d%d%d"``,&v1,&v2,&w);``    ``g[v1][v2]=g[v2][v1]=w;``  ``}``  ``ans=prim();``  ``printf``(``"The sum of the weight of the edges is:%d\n"``,ans);``  ``system``(``"pause"``);``  ``return` `0;``   ` `}`

5.程序运行后的结果截图

Tags：

﻿
<