求救~!C语言 最小生成树问题

来源:百度知道 编辑:UC知道 时间:2024/05/25 07:02:11
问题:有十个顶点,点点相连,权在程序运行时由用户输入,求最小生成树!急用!请各位大侠帮帮忙!谢谢!

普里姆算法描述:
假设 N=(V,E)是一个带权图,TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始,重复执行下述操作:在所有u∈U,v∈V-U的边(u,v) ∈E中找一条权值最小的边(u,v)并入集合TE,同时v并入U,直至U=V为止。此时TE中必有n-1边,则T=(V,{TE})为N的最小生成树。
为实现这个算法需附设一个辅助数组 closedge,以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U,在辅助数组中存在一个相应分量closedge[I-1],它包括两个域,其中lowcost存储该边上的权:显然, closedge[I-1].Lowcost=Min{cost(u,vi)|uEU} vex域存储该边依附的在U中的顶点。