克鲁斯卡尔算法的时间复杂度为多少
发布网友
发布时间：2022-05-29 19:22
共3个回答
热心网友
时间：2023-11-10 12:12
时间复杂度为O(|E|log|E|)，其中E和V分别是图的边集和点集。
基本思想是先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树。
反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。
扩展资料：
克鲁斯卡尔算法证明
假设G=(V,E) 是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。该算法的基本思想是：将图G中的边按权值从小到大的顺序依次选取。
若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为最小生成树。
克鲁斯卡尔算法，至多对e条边各扫描一次，每次选择最小代价的边仅需要O(loge)的时间。因此，克鲁斯卡尔算法的时间复杂度为O(eloge)。
参考资料来源：百度百科——克鲁斯卡尔算法
热心网友
时间：2023-11-10 12:12
假设G=(V,E) 是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。该算法的基本思想是：将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为最小生成树。
例如，按克鲁斯卡尔算法构造图7.12(a)的最小生成树的过程如图中(b)、(c)、...、(f)所示。在图(a)中，按权值递增顺序依次考虑边(1,3),(4,6),(2,5),(3,6),(1,4),(2,3),(3,5), (1,2),(5,6)和(3,4)，因为前四条边上的权值最小，而且又满足不在同一个连通分量上(不形成回路)的条件，所以依次将它们加入到T中。接着要考虑当前权值最小的边(1,4)，因该边的两个端点在同一个连通分量上(即形成回路)，故舍去这条边。然后再选择边(2,3)加入到T中，便得到要求的一棵最小生成树。
上述的克鲁斯卡尔算法，至多对e条边各扫描一次，每次选择最小代价的边仅需要O(loge)的时间。因此，克鲁斯卡尔算法的时间复杂度为O(eloge)。
由于一个网(带权图)中会有权值相同的边，所以从不同的顶点出发，可以得到不同的最小生成树。例如，在前例中的图(a)，如若从顶点v2出发，会得到一棵完全不同的MST。
热心网友
时间：2023-11-10 12:13
