转载声明：文章来源https://blog.csdn.net/qq_37857921/article/details/104987599

一、图：

与线性结构和树形结构相比，图是一种更为复杂的数据结构，因为复杂所以也更好玩。在线性数据结构中，元素只能和他的前驱或者后继有关；在树形结构中，元素只能和其父节点或者子节点有关；然而图，他可以跟其他任意一个元素相关，这也就是图的魅力所在。

二、图的应用：

那么我们学图有什么用？我们在离散数学和数据结构中都接触了图的概念，但是图在生活中应用在那边呢？图的应用处于我们生活的处处面面，如：我们去超市购买 巧克力、米、油三样东西，如果在不想逛超市的情况下，我们就会在大脑中思考如何最快，最捷径的方式去买到东西，这中找捷径的方法就是图的一种应用，当然你要学好图，送外卖都可以比别人快。所以好的送外卖的小哥都是图应用的最好实践者。

上述那么多废话，我们怎么去求最短路径？非实际应用中我们有克鲁斯卡尔算法和普里姆算法。下面我们介绍一下克鲁斯卡尔算法。

三、克鲁斯卡尔算法：

先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。

简单的说就是在图中找到所有的点之间的最短路径，然后通过最短路径依次链接，最后形成最小生成树的过程。可能这句话有BUG但是大概思路就是这样。

根据每个点之间的路径长由短向长依次链接，最后生成最小生成数。