kruskal

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

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

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