图论编程实现PRIM实验报告

《图论编程实现PRIM实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、PRIM算法生成最小生成树一、实验目的了解PRIM的基本概念以及实现方式。二、实验内容1、设计一个PRIM算法來形成图的最小生成树;个人计算机，MATLAB软件四、编程思路PRIM法的基本思想：从邻接矩阵寻找、最小权值的点，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把该边加入到生成树的边集中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U屮为止。假设G二(V,E)是一个具有n个顶点的带权无向连通图，初始状态为空在所有uWU,vev-u的

2、边(u,v)WE中找一条代价最小的边(f,L),同时将，并入U；重复执行步骤，直到U二V为止。五、调试过程1•程序代码：functionroad二prim(F)N=length(F);%图G的顶点数road=[];%记录路径的边表和权值[uvw]k=0;vis二zeros(1,N);Vis(l)二1;%生成一个顶点数的数组，第一个元素为1,存储权值whilek

3、nwminw二F(i,j);u=i;v=j;%记录最小边的顶点信息endendendend%加入生成树vis(v)二1;k二k+1;road(k,:)=[uvminw];%打印本次选出的最小边路径和权值end2.运行窗口：在运行窗口输入:»f=[inf111;1infinfinf;1infinf1;1inf1inf];»prim(f)则输出：ans=121131141则输出：矩阵前两列表示顶点关系，最后一列表示权值。