上一篇博客写了图的基本存储于遍历，在此基础上，此篇博客将会介绍图的主要应用—–生成树与最小生成树。
（一）生成树
定义：我总感觉书上定义比较繁琐，因此就自己简单定义了一下（可能不对哦），生成树其实就是：对于一棵树G,若顶点数为n,则在原来图的基础上把边删除到n-1条边且能连通各点就是生成树。，注意生成树不唯一
例如： 
利用遍历方法可以求得生成树，以邻接矩阵为存储方式代码如下：：
int visit[MAXSIZE];//标记顶点是否访问
void DFSGraph(Graph* g, int n)
{
visit[n] = 1;//若访问过就标记为1
for (size_t i = 0; i < g->n; i++)
{
if ( !visit[i]&& g->edge[n][i] == 1 )
{
cout << g->vertex[n] << " "<<i<<endl;//输出生成树的边，其实就是对遍历算法改了输出的位置
DFS(g, i);
}
}
}
void DFSTraveseGraph(Graph *g)
{
for (size_t i = 0; i < g->n; i++)
{
visit[i] = 0;
}
for (size_t i = 0; i < g->n; i++)
{
if (!visit[i])
{
DFS(g, i);//防止连通图
}
}
}(二)最小生成树
定义：我还是按照我的理解叙述吧，书上真的讲的太拖拉，对于一棵树G,若顶点数为n,则在原来图的基础上把边删除到n-1条边且能连通各点但权值和最小就是最小生成树。（如果错了望指教）.
为了求一棵树的最小生成树，有两位比较牛逼的人物给出了两种不同的算法—–PRIM算法与KRUSKAL算法。
（1）PRIM算法：
思想：
1. 首先选取一个起始顶点V0
2. 查看该顶点的所有相邻点之间的边，选取权值最小的一个边，此时该边就是最小生成树的一个边。该边的两个顶点分别为v0 v1
3. 这时查看与v0 v1 两个顶点相连的边，选取权值最小的（但是不能有环出现或者不能重复加入已有的顶点），又得到一棵边，把该边的端点加入进来,此时端点集合为v0 v1 v2
4. 重新按上述步骤添加个点与边直到结束。
其实上述是我自己总结的，下面是官方语言：
1. 首先将初始顶点u加入到U中，对其余的每一个顶点i，将closedge[i]均初始化为到u的边信息。
2. 循环n-1次，做如下处理：
a.从各组最小边closedge[v]中选出最小的最小边closedge[k0]；（v，k0属于V-U）
b.将k0加入U中；
c.更新剩余的每组最小边信息closedge[v]对于以v为中序的那组边，新增加了一条从k0到v的边，如果新边的权值比closedge[v].lowcost小，则将closedge[v].lowcost更新为新边的权值。
例如： 
其演化过程如下： 
代码如下：
void Prim(AdjMatrix gn,VertexData u)
/*从顶点u出发，按普里姆算法构造连通网gn 的最小生成树，并输出生成树的每条边*/
{
k=LocateVertex(gn, u);
closedge[k].lowcost=0; /*初始化，U={u} */
for(i=0;i<gn.vexnum;i++)
if (i!=k) /*对V-U中的顶点i，初始化closedge[i]*/
{
closedge[i].adjvex=u;
closedge[i].lowcost=gn.arcs[k][i].adj;
}
for(e=1;e<=gn.vexnum-1;e++) /*找n-1条边(n= gn.vexnum) */
{
k0=Minium(closedge); /* closedge[k0]中存有当前最小边（u0,v0）的信息*/
u0=closedge[k0].adjvex; /* u0∈U*/
v0=gn.vexs[k0]; /* v0∈V-U*/
printf("%d,%d",u0, v0); /*输出生成树的当前最小边（u0,v0）*/
closedge[k0].lowcost=0; /*将顶点v0纳入U集合*/
for(i=0;i<vexnum;i++) /*在顶点v0并入U之后，更新closedge[i]*/
if(gn.arcs[k0][i].adj<closedge[i].lowcost)
{
closedge[i].lowcost=gn.arcs[k0][i].adj;
closedge[i].adjvex=v0;
}
}
}（2）KRUSKAL算法
思想：
1. 先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点
2. 从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树
3. 若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之
4. 依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。
例如： 
代码如下：
typedef struct Edge
{
int v;
int u;
int w;
}edge;
typedef struct
{
edge *e;
int num; //边数
int nv; //定点数
}Graph;
int cmp(const void *a,const void *b) //按升序排列
{
edge * x = (edge *)a;
edge * y = (edge *)b;
return (x->w)-(y->w);
}
void kruskal(Graph *g)
{
int *x=(int *)malloc(sizeof(int)*g->num);//点所在集合
int i,m,n,c=0;
for(i=1;i<=g->nv;i++)
{
x[i]=i;
}a
qsort(g->e,g->num,sizeof(edge),cmp);
for(i=0;i<g->num&&c<g->nv;i++)
{
//判断边的两点是否在同一个集合
for(m=g->e[i].v;m!=x[m];m=x[m])
x[m]=x[x[m]];
for(n=g->e[i].u;n!=x[n];n=x[n])
x[n]=x[x[n]];
if(m!=n)
{
x[m]=n;
c++;
printf("(%d,%d)->%d\n",g->e[i].v,g->e[i].u,g->e[i].w);
}
}
}