最小生成树
图论中的一些问题被称为最小跨度树。在图论中，树是将所有顶点连接在一起的一种方式，因此从任何一个顶点，到树的任何其他顶点，正好有一条路径。如果图代表了许多由道路连接的城市，可以选择一些道路，使每一个城市都可以从其他城市到达，但从一个城市到另一个城市的道路不超过一条。
一个图形可以有不止一棵跨接树，就像选择城市之间的道路可能有不止一种方式。
大多数时候，图都是加权的；两个城市之间的每个连接都有一个权重：在某条道路上旅行可能要花费一些费用，或者一个连接可能比另一个连接长，这意味着在这个连接上旅行需要更多的时间。在图论的语言中，这些连接称为边。
最小跨度树是一棵树。它与其他树的不同之处在于，它将连接到边上的权重总数最小化。根据图的外观，可能有多个最小跨度树。在一个图中，所有的边都有相同的权重，每棵树都是一棵最小跨度树。如果所有的边都有不同的权重(也就是说：没有两个边的权重相同)，那么正好有一棵最小跨度树。
平面图的最小生成树。每条边都标有权重，这里的权重大致与长度成正比。
寻找最小跨度树
第一次尝试
可以很简单的做出一个能发现最小生成树的算法。
函数MST(G,W) :T = {} 当T没有形成生成树时: 在E中 找到对T安全的最小加权边 T = T union {(u,v)} return T在这种情况下，"安全"意味着包括边缘不会在图中形成一个循环。循环意味着从一个顶点开始，到其他一些顶点，最后再回到起点，而不会两次使用同一条边。
历程
捷克科学家奥塔卡-博鲁夫卡在1926年开发了第一个已知的寻找最小生成树的算法。他想解决寻找摩拉维亚地区用电的有效覆盖问题。今天，这个算法被称为博鲁夫卡算法。今天常用的还有两种算法。其中一种是1930年由Vojtěch Jarník提出的，1957年由Robert Clay Prim付诸实践。Edsger Wybe Dijkstra在1959年重新发现了它，并称之为Prim算法。另一种算法叫做Kruskal算法，由Joseph Kruskal在1956年发表。这三种算法都是贪婪的，并且在多项式时间内运行。
迄今为止最快的最小生成树算法是由Bernard Chazelle开发的。该算法基于软堆，是一种近似的优先级队列。其运行时间为O(m α(m,n))，其中m是边的数量，n是顶点的数量，α是Ackermann函数的经典函数倒数。函数α的增长速度极慢，因此，出于所有实际目的，它可以被认为是一个不大于4的常数；因此，Chazelle的算法需要非常接近线性的时间。
这个问题的最快算法是什么？这是计算机科学中最古老的未决问题之一。显然有一个线性的下限，因为我们至少必须检查所有的权重。如果边缘权重是整数，且位长有界，那么已知确定性算法，运行时间为线性。对于一般的权重，有随机化算法，其预期运行时间是线性的。
这个问题也可以用分布式的方式来解决。如果把每个节点看作是一台计算机，除了自己的连接链路外，没有一个节点知道任何东西，那么仍然可以计算出分布式最小生成树。
问题和答案
问：什么是图论中的最小生成树？答：最小生成树是指在图论中使附在边上的总权重最小的树。
问：什么是图论中的树？
答：树是图论中连接所有顶点的一种方式，因此从任何一个顶点到树的任何其他顶点只有一条路径。
问：在代表城市的图论场景中，选择道路的目的是什么？
答：在代表城市的图论方案中选择道路的目的是使每个城市都能从其他每个城市到达，但从一个城市到另一个城市的可能途径不超过一种。
问：一个图可以有一个以上的生成树吗？
答：是的，一个图可以有一个以上的生成树。
问：最小生成树和图论中的其他树有什么区别？
答：最小生成树将附在边上的总权重降到最低，而其他树则没有这个特点。
问：图论中的边是什么？
答：边是图论中两个顶点之间的连接。
问：在一个图中，能否有不止一棵具有不同加权边的最小生成树？
答：是的，根据图形的外观，可能有不止一棵最小生成树。
