一个连通图的生成树是一个极小連通子图它含有图中全部n个顶点和构成树的n-1条边
可以通过遍历方法产生生成树：深度优先生成树和广度优先生成树。生成树不是唯一的
最小生成树：对于带权连通图G，可能有多棵不同的生成树每棵生成树的所有边和权值之和可能不同，其中权值之和最小的生成树称为圖的最小生成树
对于连通图，仅需调用遍历过程一次从图中任一顶点出发，便可以遍历图中的各个顶点产生相应的生成树。
对于非連通图需多次调用遍历过程。每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树所有连通分量的生成树组成非连通图的苼成森林。

重点在于如何判断加入一条边后是否出现回路设置一个连通分量编号数组vset[]，当添加一条边之后将该边所连的两个分量顶点嘚编号置为相同。在遍历边的时候若一条边的两个顶点的编号相同，添加该边会形成回路故要舍弃该边。

Prim算法的时间复杂度为${}^{}$O(eloge)所以Prim算法适用于稠密图而Kruskal算法更适用于稀疏图。