PRIM算法实验报告
篇一：prim算法实验报告算法实验报告学院：xxx班级：xxx学号：xxx姓名：xxxprim篇二：prim最小生成树算法实验报告算法分析与设计之prim学院：软件学院学号：201421031059姓名：吕吕一、问题描述1.prim的定义prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。
(强调的是树，树是没有回路的)。
2.实验目的选择一门编程语言，根据prim算法实现最小生成树，并打印最小生成树权值。
二、算法分析与设计1.prim算法的实现过程基本思想：假设g＝(v，e)是连通的，te是g上最小生成树中边的集合。
算法从u＝{u0}（u0∈v）、te＝{}开始。
重复执行下列操作：在所有u∈u，v∈v－u的边(u，v)∈e中找一条权值最小的边(u0,v0)并入集合te中，同时v0并入u，直到v＝u为止。
此时，te中必有n-1条边，t=(v，te)为g的最小生成树。
prim算法的核心:始终保持te中的边集构成一棵生成树。
2.时间复杂度prim算法适合稠密图，其时间复杂度为o(n^2)，其时间复杂度与边得数目无关，n为顶点数，而看ruskal算法的时间复杂度为o(eloge)跟边的数目有关，适合稀疏图。
三、数据结构的设计图采用类存储，定义如下：classgraph{private:int*verticeslist;int**edge;intnumvertices;intnumedges;intmaxvertices;graph();~graph();boolinsertvertex(constintvertex);boolinsertedge(intv1,intv2,intcost);intgetvertexpos(intvertex
prim算法
A.Prim算法： procedure prim(v0:integer); var lowcost,closest:array[1..maxn] of integer; i,j,k,min:integer; begin for i:=1 to n do begin lowcost[i]:=cost[v0,i];closest[i]:=v0; end; for i:=1 to n-1 do begin {寻找离生成树最近的未加入顶点k} min:=maxlongint; for j:=1 to n do if (lowcost[j]< min) and (lowcost[j]< >0) then begin min:=lowcost[j]; k:=j; end; lowcost[k]:=0; {将顶点k加入生成树} {生成树中增加一条新的边k到closest[k]} {修正各点的lowcost和closest值} for j:=1 to n do if cost[k,j]< lwocost[j] then begin lowcost[j]:=cost[k,j]; closest[j]:=k; end; end; end;{prim}
关于prim 算法 帮忙分析
prim算法得到的就是最小生成树。
近似最优大概是指用最小生成树算法计算哈密尔顿圈之类的
