kruskal

最小生成树即一个图其代价最小的生成树，生成树必须包含图中所有顶点，并使图中任意两个顶点之间存在唯一一条路径，设顶点数为n，则生成树的边数为n - 1，对连接顶点的边赋予权重，权重之和最小的生成树即为最小生成树。图的生成树并不是唯一的，最小生成树也是如此(但代价唯一)。 在实际应用中，假如对n个城市铺设电缆，在确保n个城市是连通的情况下，需要n - 1条线路，如果铺设每条电缆的代价都是不一样的，那么如何使得代价最低？最小生成树就用来可以解决这个问题

BFS（广度优先搜索）：已知图G=(VE)和一个源顶点s，广度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的广度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。 DFS（深度优先搜索）：深度优先算法是一种用于遍历图的算法

完全图：任何两个节点之间都有边。 连通图：任何两个节点之间都有路径。 深度优先搜索：节点优先级=父节点优先级-1，越深的节点优先级越小，越优先

在图论中，一张无向图的线图是能体现其连边状态的一种生成图。有关线图的中文资料很少，但有关它的外文资料非常丰富。在这篇文章中，我将简单介绍线图的定义，以及提出计算线图最小生成树大小的一种方法

贪心算法有很多经典应用，如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、Dijkstra 单源最短路径算法。 贪心算法思想： 针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。 当前情况下，每次选择在消耗同等限制值的情况下，对期望值贡献最大的数据；或者说对期望值贡献同等的情况下，消耗的限制值尽量少

Prim算法是直接查找，多次寻找邻边的权重最小值，而Kruskal是需要先对权重排序后查找的；Kruskal在算法效率上是比Prim快的，因为Kruskal只需一次对权重的排序就能找到最小生成树，而Prim算法需要多次对邻边排序才能找到。 深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点；广度遍历类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。 Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题