链接
无向图：
无向图的意思是，边没有方向。
树：
-
树是一类特殊的图，树是由
节点和无向边构成的； -
所有的树都是
无向图，但是无向图未必是树； -
树有一些性质，但并非所有图都有这些性质；
-
树是连通图。
连通图的意思是，任何节点之间都至少有一条路径。 -
在树中，任何两个节点之间，有且只有一条路径；
-
树中没有回路。即，从一个节点出发，不能沿着某条路径再回到这个节点。
-
如果树有n个节点，那么树一定有n-1条边。多一条边会形成回路，少一条边会失去连通性。
树有三大要素：
- 1.连通；
- 2.无环 (没有回路)；
- 3.无向；
如果一个图满足上面三个条件，那么这个图一定是树。
下图是一个图，但它不是一棵树，因为它有回路。
下面这个图不是树，因为它不是连通图。
生成树：
给定一个连通的无向图，我们可以把他变成一棵生成树，保留所有节点，保留n-1条边，得到的子图必须满足两个性质：
- 图是连通的；
- 图没有回路 ；
如果子图满足这两个性质，那么子图就叫做生成树Spanning Tree。
最小生成树：
给定一个图，不只有一种生成树，在所有生成树中，我们最感兴趣的是最小生成树(Minimum Spanning Tree)。
最小生成树的意思是让权重之和最小。
下图左边是一个连通的无向图，有7个节点，12条边。边上的数字表示每条边的权重。我们要寻找他的生成树.
我们要保留全部的7个节点，但是要从12条边中选出6条边。
方案1：
其中一种方案就是，用红色表示要保留的边，其他的边都去掉，这样就得到了右边的图。右边的图就是一棵树，被称为生成树Spanning Tree。
生成树要保留所有节点，保留一部分边，最终得到的子图必须是一棵树。树是连通的，而且没有回路，否则就不是树。
右边的生成树的每条边的权重都加起来，2+4+2+7+5+1=21。
生成树并不唯一，可以由同一张图，获得不同的生成树。
方案2：
如下图，是另一种方案，生成树的权重加起来是25。
方案3：
如下图，又是一种方案，生成树的权重加起来是26。
所以，生成树并不唯一，一个无向图中可以包含很多种生成树。而我们关心的是最小生成树(Minimum Spanning Tree)。最小生成树的意思是让权重之和最小。
方案4：
下面这种方案的生成树，权重之和等于16，他是所有生成树中权重之和最小的，它就称为最小生成树。
没有生成树的图：
需要说明的是，并非任何图都有生成树。
下面这个图就没有生成树，因为它不是连通图。
它可以分成两部分，这两部分之间没有边相连，所以，也不可能通过删除一些边，让这个图变得连通，所以找不到生成树。
最小生成树的实际应用
村里各户的铺路问题：
村里都是土路，现在市长需要给村里铺上水泥路，有条件：
- 1.保证每两家之间都必须能通过走水泥路到达；
- 2.要让铺路的成本最低；即，水泥路的总长度最短。
可以把原来所有的房子和土路看做是一个无向图，每户房子看做是节点，土路看做是边。我们要选择图中的一部分边来铺水泥路，铺路要保证图的连通性。
下面是其中一种可行方案，并不一定是最优方案，最优方案得通过计算水泥路总长度计算出来。
链接: 最小生成树 Minimum Spanning Trees
本文链接：https://my.lmcjl.com/post/2471.html
4 评论