历安毛子代枚大等 最小生成树 XIDIAN UNIVERSITY 3.克鲁斯卡尔算法(Kruskal Algorithm) 第一步：在带权连通图中，将边的权值排序； 第二步：从权值最小的边开始，判断是否需要选择这条边。判断 的依据是边的两个顶点是否已连通，如果连通则继续下一条；如 果不连通，那么就选择使其连通。 连通时，要做如下判断：这两个点是否在己找到点的集合中 出现过？①.如果两个点都没有出现过，那么将这两个点都加入已 找到点的集合中；②如果其中一个点在集合中出现过，那么将另 一个没有出现过的点加入到集合中；③如果这两个点都出现过， 则不用加入到集合中。 第三步：循环第二步，直到图中所有的顶点都在子图中，即得到 最小生成树。 63. 克鲁斯卡尔算法(Kruskal Algorithm) 第一步：在带权连通图中，将边的权值排序； 第二步：从权值最小的边开始，判断是否需要选择这条边。判断 的依据是边的两个顶点是否已连通，如果连通则继续下一条；如 果不连通，那么就选择使其连通。 连通时，要做如下判断： 这两个点是否在已找到点的集合中 出现过？ ①.如果两个点都没有出现过，那么将这两个点都加入已 找到点的集合中；②.如果其中一个点在集合中出现过，那么将另 一个没有出现过的点加入到集合中；③.如果这两个点都出现过， 则不用加入到集合中。 第三步：循环第二步，直到图中所有的顶点都在子图中，即得到 最小生成树。 最小生成树 6