无权无向图,只给出节点个数,怎么用Prim算法求最小生成树

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/05/22 00:08:47

Prim算法的主要运行时间花在过程②的选边中.看起来复杂度是O(VE)=O(V^3)不是么,效率也太低了吧……

为了比较快速地选边,我们用两个数组lowcost、closest动态地维护每一个点到S的最短距离.在某一状态下,lowcost[i]表示所有与i相连且另一端点在S中的边中的权值最小值,closest[i]表示在S中且与i相连的点中与i之间距离最小的点.显然,lowcost[i]=w(i,closest[i]).需要注意的是两个数组记录的都是边而不是路径.若i没有边直接连向S,则lowcost[i]=∞.另外,若i已在S中,则lowcost[i]=0.

设出发点为x.初始时对于任意k∈V,closest[k]=x,lowcost[k]=w（k,x）【w（i,j）表示i、j间的距离.初始化时,若两点间没有边则w（i,j）赋为一个足够大的整数（如maxint）,并且所有点到自身的距离赋为0,即w（i,i）=0】

每一次找出lowcost中不为0的最小值lowcost[i],然后把i加入S（即lowcost[i]:=0）,然后对于图中所有点k,若w(k,i)

如图所示为一个无向带权图,请分别按照Prim算法和Kruskal算法求最小生成树用普里姆（Prim）或克鲁斯卡尔（Kruskal）算法画出下列无向网的最小生成树对于以下无向带权图.利用Prim算法,从V1出发,得到最小生成树的过程中, 求带权图的最小生成树一、实验目的熟练理解求最小生成的Prim算法；锻炼程序设计能力.二、实验内容编程实现求无向带权图的最利用Prim（普里姆）算法构造最小生成树程序求一个源代码要求显示图的邻接矩阵图的邻接表,深度广度优先遍历最小生成树PRIM算法KRUSCAL算法图的连通分 Kruskal算法和Prim算法构造它的一棵最小代价生成树的过程 C语言数据结构克鲁斯卡尔算法求无向网的最小生成树. 对图2所示的无向带权图,用普里姆算法或克鲁斯卡尔算法求其最小生成树求无向图最小环道的算法最好是matlab算法其他算法也可以求最小生成树利用Kruskal算法求图G的一棵最小生成树T,用c语言数据结构课程设计用Kruskal 算法求最小生成树