下载文档原格式
最⼩⽣成树（普⾥姆算法）：所谓⽣成树，就是n个点之间连成n-1条边的图形。
⽽最⼩⽣成树，就是权值（两点间直线的值）之和的最⼩值。
⾸先，要⽤⼆维数组记录点和权值。
如上图所⽰⽆向图：int map[7][7];map[1][2]=map[2][1]=4;map[1][3]=map[3][1]=2;......然后再求最⼩⽣成树。
具体⽅法是：1.先选取⼀个点作起始点，然后选择它邻近的权值最⼩的点（如果有多个与其相连的相同最⼩权值的点，随便选取⼀个）。
如1作为起点。
visited[1]=1;pos=1;//⽤low[]数组不断刷新最⼩权值，low[i](0<i<=点数)的值为：i点到邻近点（未被标记）的最⼩距离。
low[1]=0; //起始点i到邻近点的最⼩距离为0low[2]=map[pos][2]=4;low[3]=map[pos][3]=2;low[4]==map[pos][4]=3;low[5]=map[pos][5]=MaxInt; //⽆法直达low[6]=map[pos][6]=MaxInt;2.再在伸延的点找与它邻近的两者权值最⼩的点。
//low[]以3作当前位置进⾏更新visited[3]=1;pos=3;low[1]=0; //已标记，不更新low[2]=map[1][2]=4; //⽐5⼩，不更新low[3]=2; //已标记，不更新low[4]=map[1][4]=3; //⽐1⼤，更新后为：low[4]=map[3][4]=1;low[5]=map[1][5]=MaxInt;//⽆法直达，不更新low[6]=map[1][6]=MaxInt;//⽐2⼤，更新后为：low[6]=map[3][6]=2;3.如此类推...当所有点都连同后，结果最⽣成树如上图所⽰。
所有权值相加就是最⼩⽣成树，其值为2+1+2+4+3=12。
⾄于具体代码如何实现，现在结合POJ1258例题解释。
