上一篇博文我们提到了图的最短路径问题：。而最短路径问题可以说是这样的一个问题：路已经修好了，该怎么从这儿走到那儿？但是在和图有关的问题中，还有另一种有趣的问题：修路的成本已经知道了，该怎么修路才能尽可能节约成本，同时将这些地方都连起来？
比如我们知道有这么几个城市，它们互相之间还没有路：
经过实地考察后，发现可以修的路以及各条路的修路成本如下：
但是我们的预算有限，需要在修路时尽可能的省钱（也就是尽量减小所有边的权重之和），同时保证图中每一个城市总是能到达图中任意一个城市，该怎么修路呢？对于上图来说，其中一个方案是这样的，其总共的修路成本（即总权重）为8：
另一个方案是这样的，略有不同，不过总成本也是8：
像这样的问题，就是我们今天要讨论的最小生成树问题。为了更准确地说明什么是最小生成树，我们需要先了解一个概念：连通。对于一个无向图而言，如果每个顶点到每个其它顶点都存在路径，则该无向图是连通的。而对于有向图而言，道理相同又稍有变化，在有向图中，若每个顶点到每个其它顶点都存在可行的路径，则该有向图是强连通的。比如下图就不是一个强连通的有向图，其中非v0顶点无法到达v0顶点：
但是如果我们将上面这个有向图的边都变为无向边，我们就会得到一个无向图，此无向图即该有向图的基础图（underlying graph）。如果一个有向图非强连通，但是其基础图是连通的，我们就称该有向图是弱连通的。上面这个有向图就是一个弱连通的有向图。
明白了什么是连通之后，接下来我们说说最小生成树是什么：在一个连通的无向图的所有边中，挑选出足以使所有顶点连通的那些边，且这些边的总权重不能更低，则这些边与所有顶点构成的图就是最小生成树。“最小”的意思是其总权重是最小的，“生成”则是因为这个树是从一个无向图中找出来的，也即生成的。
等等_(:з」∠)_ 不是说“这些边与所有顶点构成的图”吗，怎么就成了树？原因是这样的，如果一个无向图是连通的，那么我们就能找出满足上述条件的那个图，而如果那个图存在，那它一定是一棵树（树是特殊的图嘛，这一点应该要懂的），比如本文前面所找出的最小生成图，显然是一棵树：
为什么称最后找出来的顶点与边的集合为最小生成树，我们已经知道了，而为什么最后找出来的一定是树……咱能不纠结吗 (￣.￣)
好了，接下来讨论下一个问题：有向图可以找出最小生成树吗？答案是可以，只要有向图是强连通的。并且寻找有向图的最小生成树的过程也是基本一样的，因为无向图本就是以有向图的形式存储的（一条无向边拆成两条有向边）。不过因为本文并不打算给出可运行的代码，所以我们的讨论以无向图为基准，主要关注算法的思路，并且不考虑所给图非连通的情况。
想要在图中找出最小生成树，有两种算法可供选择：Prim算法和Kruskal算法。因为Prim算法与寻找最短路径的Dijkstra算法非常非常非常像，所以我们先来讨论一下Prim算法。
Prim算法的思路是这样的：
1.任选一个顶点，将其标为已知，即表示该顶点已在树中（Dijkstra算法中，起点由我们指定）