题目要求是求最小生成树。
最小生成树有Prim算法和Kruskal算法。其中Prim算法意思很简单，把节点分成两类I,II.
I是指已经连接的点；
II是指还没有连接的点；
我们每次从I和II中都选择一个点，其中这两个点的距离，是所有I中点与II中点配对中距离最小的两个点，并将II中的这个点加到I中；
重复上述过程，知道I中的点是全部点为止；
伪代码：
void Prim( S , T )
{
S = {1};
while(T!=空集）
（i,j）={wij|wij 是i∈S,j∈T中最短的一条边}
S=S+{j};
T=T-{j};
}
阅读(658) | 评论(0) | 转发(1) |
