prim算法求最小生成树代码,普里姆算法最小生成树C语言

prim算法求最小生成树代码,普里姆算法最小生成树C语言,Prim(普里姆)算法求最小生成树的思想及C语言实例讲解

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

留言与评论(共有 条评论)
   
验证码: