显然这三种情况都不是树，第一种是因为图中的边有方向了。有了方向之后，图中连通的情况就被破坏了。在我们认知当中树应该是全连通的，就好像自然界中的一只蚂蚁，可以走到树上任何位置。不能全连通，自然就不是树。情况2也不对，因为有了环，树是不应该有环的。自然界中的树是没有环的，不存在某根树枝自己绕一圈，同样，我们逻辑中的树也是没有环的，否则我们递归访问永远也找不到终点。第三种情况也一样，有些点孤立在外，不能连通，自然也不是树。
那我们总结一下，就可以回答这个问题。树是什么？树就是可以全连通（无向图），并且没有环路的图。
从图到树
从刚才的分析当中，我们得到了一个很重要的结论，树的本质就是图，只不过是满足了一些特殊性质的图。这也是为什么树的很多算法都会被收纳进图论这个大概念当中。
从全连通和没有环路这两个性质出发，我们又可以得到一个很重要的结论，对于一棵拥有n个节点的树而言，它的边数是固定的，一定是n-1条边。如果超过n-1条边，那么当中一定存在环路，如果小于n-1条边，那么一定存在不连通的部分。但注意，它只是一个必要条件，不是一个充分条件。也就是说并不是n个点n-1条边就一定是树，这很容易构造出反例。
这个结论虽然很简单，但是很有用处，它可以解决一个由图转化成树的问题。
也就是说当下我们拥有一个复杂图，我们想要根据这个图生成能够连通所有节点的树，这个时候应该怎么办？如果我们没有上面的性质，会有一点无从下手的感觉。但有了这个性质之后，就明确多了。我们一共有两种办法，第一种办法是删减边，既然是一个复杂图，说明边的数量一定超过n-1。那么我们可以试着删去一些边，最后留下一棵树。第二种做法与之相反，是增加边。也就是说我们一开始把所有的边全部撤掉，然后一条一条地往当中添加n-1条边，让它变成一棵树。
我们试着想一下，会发现删减边的做法明显弱于添加边的方法。原因很简单，因为我们每一次在删除边的时候都面临是否会破坏树上连通关系的拷问。比如下图：
如果我们一旦删去了AB这条边，那么一定会破坏整个结构的连通性。我们要判断连通关系，最好的办法就是我们先删除这条边，然后试着从A点出发，看看能否到达B点。如果可以，那么则认为这条边可以删除。如果图很大的话，每一次删除都需要遍历整张图，这会带来巨大的开销。并且每一次删除都会改变图的结构，很难缓存这些结果。
因此，删除边的方式并不是不可行，只是复杂度非常高，正因此，目前比较流行的两种最小生成树的算法都是利用的第二种，也就是添加边的方式实现的。
到这里，我们就知道了，所谓的最小生成树算法，就是从图当中挑选出n-1条边将它转化成一棵树的算法。
解决生成问题
我们先不考虑边上带权重的情况，我们假设所有边都是等价的，先来看看生成问题怎么解决，再来进行优化求最小。
如果采用添加边的方法，面临的问题和上面类似，当我们选择一条边的时候，我们如何判断这条边是有必要添加的呢？这个问题需要用到树的另外一个性质。
由于没有环路，树上任意两点之间的路径，有且只有一条。因为如果存在两点之间的路径有两条，那么必然可以找到一个环路。它的证明很简单，但是我们很难凭自己想到这个结论。有了这个结论，就可以回答上面的那个问题，什么样的边是有必要添加的？也就是两个点之间不存在通路的时候。如果两个点之间已经存在通路，那么当前这条边就不能添加了，否则必然会出现环。如果没有通路，那么可以添加。
所以我们要做的就是设计一个算法，可以维护树上点的连通性。
但是这又带来了一个新的问题，在树结构当中，连通性是可以传递的。两个点之间连了一条边，并不仅仅是这两个点连通，而是所有与这两个点之间连通的点都连通了。比如下图：
这张图当中A和B连了一条边，这不仅仅是A和B连通，而是左半边的集合和右半边集合的连通。所以，虽然A只是和B连通了，但是和C也连通了。AC这条边也一样不能被加入了。也就是说A和B连通，其实是A所在的集合和B所在的集合合并的过程。看到集合的合并，有没有一点熟悉的感觉？对嘛，上一篇文章当中我们讲的并查集算法就是用来解决集合合并和查询问题的。那么，显然可以用并查集来维护图中这些点集的连通性。
如果对并查集算法有些遗忘的话，可以点击下方的传送门回顾一下：
利用并查集算法，问题就很简单了。一开始所有点之间都不连通，那么所有点单独是一个集合。如果当前边连通的两个点所属于同一个集合，那么说明它们之间已经有通路了，这条边不能被添加。否则的话，说明它们不连通，那么将这条边连上，并且合并这两个集合。
于是，我们就解决了生成树这个问题。
从生成树到最小生成树
接下来，我们为图中的每条边加上权重，希望最后得到的树的所有权重之和最小。
比如，我们有下面这张图，我们希望生成的树上所有边的权重和最小。
观察一下这张图上的边，长短不一。根据贪心算法，我们显然希望用尽量短的边来连通树。所以Kruskal算法的原理非常简单粗暴，就是对这些边进行长短排序，依次从短到长遍历这些边，然后通过并查集来维护边是否能够被添加，直到所有边都遍历结束。
可以肯定，这样生成出来的树一定是正确的，虽然我们对边进行了排序，但是每条边依然都有可能会被用上，排序并不会影响算法的可行性。但问题是，这样贪心出来的结果一定是最优的吗？
这里，我们还是使用之前讲过的等价判断方法。我们假设存在两条长度一样的边，那么我们的决策是否会影响最后的结果呢？
两个完全相等的边一共只有可能出现三种情况，为了简化图示，我们把一个集合看成是一个点。第一种情况是这两条边连通四个不同的集合：
