一、生成树的概念
一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的(n-1)条边。
如果在一棵生成树上添加一条边，必定构成一个环。
一棵有n个顶点的生成树(连通无回路图)有且仅有(n-1)条边，如果一个图有n个顶点和小于(n-1)条边，则是非连通图。
如果它多于(n-1)条边，则一定有回路。但是，有(n-1)条边的图不一定都是生成树。
最小生成树：图的所有生成树中具有边上的权值之和最小的树。
按照生成树的定义，n个顶点的连通图的生成树有n个顶点、n-1条边。
因此，构造最小生成树的准则有三条：
（1）必须只使用该图中的边来构造最小生成树；
（2）必须使用且仅使用n-1条边来连接图中的n个顶点；
（3）不能使用产生回路的边。
二、无向图的连通分量和生成树
在对无向连通图进行遍历时，仅需调用遍历过程（DFS或BFS）一次，从图中任一顶点出发，便可以遍历图中的各个顶点。
对非连通图，则需多次调用遍历过程，每次调用得到的顶点集连同相关的边就构成图的一个连通分量。
设G=(V，E)为连通图，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T和B，其中T是遍历图过程中走过的边的集合，B是剩余的边的集合：T∩B=Φ，T∪B=E(G)。显然，G'=(V，T)是G的极小连通子图，即G'是G的一棵生成树。
1.普里姆（Prim）算法
假设G=(V，E)是一个具有n个顶点的带权连通无向图，T=(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造最小生成树T的步骤如下：
（1）初始化U={v}。v到其他顶点的所有边为候选边；
（2）重复以下步骤n-1次，使得其他n-1个顶点被加入到U中：
① 从候选边中挑选权值最小的边输出，设该边在V-U中的顶点是k，将k加入U中；
② 考察当前V-U中的所有顶点i，修改候选边：若(i,k)的权值小于原来和顶点k关联的候选边，则用(v,i)取代后者作为候选边。
(a)图G
(b)图G的最小生成树
步骤解析：
①以顶点0作为源点，从它的相邻路径找出一条权值最小的边：0->5，U{0,5}，lowcost[0]=10，closet[0]=5
②在剩下顶点中，找到第二条权值最小的边：5->4,U{0,5,4}，lowcost[5]=25，closet[5]=4
③重复步骤2，在选取过程中保证不产生回路
普里姆（Prim）算法如下：
#define INF 32767 //INF表示∞void Prim(MGraph g,int v)
{ int lowcost[MAXV];
int min;
int closest[MAXV],i,j,k;
for (i=0;i<g.n;i++) //给lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //找出(n-1)个顶点
{ min=INF;
for (j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k记录最近顶点的编号
}
printf(" 边(%d,%d)权为:%d\n",closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<g.n;j++) //修改数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
lowcost[i]表示顶点i（i ∈ V－U）到U中所有顶点的最小代价，从顶点i到U中最小代价的顶点用closest[i]表示。
2.克鲁斯卡尔(Kruskal)算法
克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。
假设G=(V，E)是一个具有n个顶点的带权连通无向图，T=(U，TE)是G的最小生成树。
（1）置U的初值等于v（即包含有G中的全部顶点），TE的初值为空集（即图T中每一个顶点都构成一个分量）。
（2）将图G中的边 按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE ；否则舍弃， 直到TE中包含(n-1)条边为止 。
(c))图G'
(d))图G'的最小生成树
把每个顶点看作一棵树，形成森林，将森林转换为一棵树的过程
步骤解析：
①以顶点0作为源点，，直接从图G'中找到一个权值最小的顶点：5
②在剩下顶点中，找到第二条权值最小的顶点：6
③重复步骤2，在选取过程中保证不产生回路
克鲁斯卡尔算法如下：
typedef struct
{ int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
} Edge;
void Kruskal(MGraph g)
{ int i,j,u1,v1,sn1,sn2,k;
int vset[MAXV];
Edge E[MaxSize]; //存放所有边
k=0; //E数组的下标从0开始计
for (i=0;i<g.n;i++) //由*生的边集E
for (j=0;j<g.n;j++)
if (g.edges[i][j]!=0 && g.edges[i][j]!=INF)
{ E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];
k++;
}
InsertSort(E,g.e);//采用直接插入排序对E数组按权值递增排序
for (i=0;i<g.n;i++) //初始化辅助数组
vset[i]=i;
k=1; //k表示当前构造生成树的第几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<g.n) //生成的边数小于n时循环
{ u1=E[j].u;v1=E[j].v; //取一条边的头尾顶点
sn1=vset[u1];
sn2=vset[v1]; //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合
{ printf(" (%d,%d):%d\n",u1,v1,E[j].w);
k++; //生成边数增1
for (i=0;i<g.n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
}
改进克鲁斯卡尔算法：
采用并查集求解（改进克鲁斯卡尔算法）：
void Kruskal(MGraph g){ int i，j，k，u1，v1，sn1，sn2;
UFSTree t[MAXSize];
Edge E[MAXSize];
k=1; //e数组的下标从1开始计
for (i=0;i<g.n;i++) //由*生的边集E
for (j=0;j<g.n;j++)
if (g.edges[i][j]!=0 && g.edges[i][j]!=INF)
{ E[k].u=i;E[k].v=j;
E[k].w=g.edges[i][j];
k++;
}
HeapSort(E，g.e); //采用堆排序对E数组按权值递增排序
MAKE_SET(t，g.n); //初始化并查集树t
k=1; //k表示当前构造生成树的第几条边，初值为1
j=1; //E中边的下标，初值为1
while (k<g.n) //生成的边数小于n时循环
{ u1=E[j].u;
v1=E[j].v; //取一条边的头尾顶点编号u1和v2
sn1=FIND_SET(t，u1);
sn2=FIND_SET(t，v1); //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属不同集合，该边是最小生成树的一条边
{ printf(" (%d，%d):%d\n"，u1，v1，E[j].w);
k++; //生成边数增1
UNION(t，u1，v1);//将u1和v1两个顶点合并
}
j++; //扫描下一条边
}
}
本算法的时间复杂度是O(elog2e)。由于它与n无关，只与e有关，所以克鲁斯卡尔算法适合于稀疏图。