Q：如何通过Prim算法构建最小生成树 A：初始时从图中任取一顶点加入树 T，此时树中只含有一个顶点。之后选择一个与当前 T 中顶点集合距离最近的顶点，并将该顶点和相应的边加入 T。每次操作后 T 中的顶点数和边数都增 1。以此类推，直至图中所有的顶点都并入 T，得到的 T 就是最小生成树。此时 T 中必然有 n-1条边。 通俗来讲，Prim算法构建最小生成树流程如下：
1） 从某顶点 u0 出发，选择与它关联的具有最小权值的边 (u0, v)，将其顶点 v 加入到生成树的顶点集合 U 中。
2） 每一步从一个顶点在 U 中，而另一个顶点不在 U 中的各条边中选择权值最小的边 (u, v),把它的顶点 v 加入到 U 中。
3）直到所有顶点都加入到生成树顶点集合 U 中为止。
Prim算法的简单实现如下：
void Prim(G,T)
{
t=NULL; //初始化空树
U={w}; //添加任一结点 w
while((V-U)!=NULL) //若树中不含全部结点
{
设（u，v）是使 u∈U与v∈（V-U），且权值最小的边；
T=T∪{{u，v}} //边归入树
U=U∪{v}； //顶点归入树
}
}
复制代码
Prim 算法的时间复杂度为 O(n^2),不依赖于|E|，因此它适用于求解边稠密的图的最小生成树。
kruskal算法实现最小生成树
与 Prim 算法从顶点开始扩展最小生成树不同，Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。 Q：如何通过kruskal算法构建最小生成树 A：初始时为只有 n 个顶点而无边的非连通图 T=V，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入 T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至 T 中所有顶点都在一个连通分量上。 通俗来讲，kruskal算法构建最小生成树流程如下：
1）设连通网络 N = { V, E }，构造一个只有 n 个顶点，没有边的非连通图 T = { V, Ø }, 每个顶点自成一个连通分量。
2） 在 E 中选最小权值的边,若该边的两个顶点落在不同的连通分量上，则加入 T 中；否则舍去，重新选择。
