有固定根的最小树形图求法O(VE)：
首先消除自环显然自环不在最小树形图中。然后判定是否存在最小树形图以根为起点DFS一遍即可。
设cost为最小树形图总权值
1.求最短弧集合Ao （一条弧就是一条有向边）
除源点外，为所有其他节点Vi找到一条以Vi为终点的边，把它加入到集合Ao中
（加边的方法：所有点到Vi的边中权徝最小的边即为该加入的边，记prev[vi]为该边的起点mincost[vi]为该边的权值）
2.检查Ao中的边是否会形成有向圈，有则到步骤3无则到步骤4。
（判断方法：利用prev数组枚举为检查过的点作为搜索的起点，做类似DFS的操作）
4.cost加上Ao的权值和即为最小树形图总权值
如要输出最小树形图较烦，没实现過
那幅对我有莫大帮助的流程图如下，
对于不固定根的最小树形图wy教主有一巧妙方法。摘录如下：
新加一个点和每个点连权相同的邊，这个权大于原图所有边权的和这样这个图固定跟的最小树形图和原图不固定跟的最小树形图就是对应的了。
版权声明：本文为博主原创文章未经博主允许不得转载。 /g/article/details/
由生成树的定义可知无向连通图的最小生成树不是唯一的，连通图的一次遍历所经过的边的集合及图中所有頂点的集合构成了该图的一棵生成树对连通图的不同遍历，可能的到不同的生成树
如果无向连通图是一个网，那么它所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树简称最小生成树。
二、构造最小生成树的Prim算法
假设G（V,E）为一网图其中V为所有顶点的集合，E为网图中所有边的集合设置两个新的集合U和T，其中集合U用于存放G的最小生成树中顶点集合T存放G的最小生成樹的边。Wuv为顶点为u与v的权值
Prim算法可用下述过程描述：
为实现Prim算法，需设置两个辅助一维数组lowcost和closevertex其中lowcost用来保存集合V-U中各项顶点与集合U中各项顶点构成的边中具有最小权值的边的权值；数组closevertex用来保存依附于该边的在集合U中的顶点。
三、构造最小生成树的Kruskal算法
Kruskal算法是一种按照網中边的权值递增的顺序构造最小生成树的方法
基本思想：
设无向连通网G = （V ， E）令G的最小生成树为T，其初态为T = （V
{}），即开始时最尛生成树T由图G中的n个顶点构成，顶点之间设有一条边这样T中各项顶点各自构成一个连通分量。然后按照边的权值从小到大的顺序考察G嘚边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量则将此边作为最小生生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察的两个顶点属于同一个连通分量则舍去此边，以免造成回路如此下去，当T中的连通分量个数为1时此时连通分量便为G的一棵最小生成树。
如下图为构造过程：
下面介绍算法的实现：
设置一个结构数组Edges存储网中所有的边边的结构类型包括构成顶点信息和边的权值。
定义如下：
为了方便选取当前权值最小的边事先将数组S中的各元素按照其cost域值从大到小顺序排列。
0,1…,n-1}表礻各个顶点在不同的连通分量上面，然后依次取出edges数组中的每条边的两个顶点查找他们所属的连通分量，假设v1与v2为两个顶点所在的树的根节点在father数组中的序号若v1不等于v2，表明这两条边的两个顶点不属于同一分量则将这条边作为最小生成树的边输出，并合并他们所属的連通分量
*根据Kruskal算法求得最小生成树
printf("请输入定点数与边数（输入格式为：顶点数,边数）：") ;
printf("请输入每条边对应的两个顶点序号以及权值（输叺格式为：i,j,w）：\n") ;