因该是prim算法
假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:
1:初始化:U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。
2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。
3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。
追问这是一道考试问答图 可以简化一点吗？谢谢
追答指定一个起点。首先讲指定的起点作为已选顶点，然后反复在满足以下条件的边中选一条边，知道所有顶点成为已选顶点为止（选择n-1条边）。条件是一端已选，一端未选。
追问指定一个起点
首先将指定的起点作为已选顶点，然后反复在满足条件（一端已选，一端未选）的边中选一条边
直到所有顶点成为已选顶点为止（选择N-1条边）
这样吗？
我不懂这是啥意思，不知道改卷老师懂不懂
追答嗯
参考资料：http://baike.baidu.com/view/671819.htm#3