创建图以将Kruskal算法强制为最坏情况 [英] Create graph to force Kruskal's algorithm to worst case

问题描述

在最坏的情况下，我想通过许多节点来强制执行kruskal算法.它应该是什么样的图?我被困住了.

I wanna make a grpah with many nodes to force kruskal algorithm in worst case scenario. What kind of graph should it be ? I im stuck .

推荐答案

假设您正在实现具有双联集的kruskal算法，并使用稳定且快速"的算法对边缘进行排序，那么您将具有 O(E log E ).您还可以具有 E = O(V ^ 2)，因此最坏的情况也将是 O(E log V).我们可以得出结论，运行时间主要由堆操作决定，因此通常算法在考虑所有边缘之前就终止，因此在实践中速度更快.考虑到所有这些，为了重现最坏的情况，要做的就是最大化图形，考虑到每个顶点都有连接到所有其他顶点的边.

Supposing you are implementing kruskal algorithm with dijoint sets, and sorting the edges with a stable and "fast" algorithm you will have O(E log E) worst case. You can also have E = O(V^2), so worst case will also be O(E log V). We can conclude that running time is dominated by heap operations so typically the algorithm terminates before considering all edges, so faster in practice. Considering all of this, in order to reproduce the worst case scenario all you have to do is maximize your graph, considering that each vertex will have edges connecting to all other vertexes.

这篇关于创建图以将Kruskal算法强制为最坏情况的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！