普里姆和Kruskal的算法的复杂性 [英] Prim and Kruskal's algorithms complexity

问题描述

由于配重块无向连通图。 W：ê - > {1,2,3,4,5,6,7} - 这意味着，只有7的权重可能。 我需要用Prim算法在O（N + M），并Kruskal算法为O找到一个生成树（M * A（M，N））。

Given an undirected connected graph with weights. w:E->{1,2,3,4,5,6,7} - meaning there is only 7 weights possible. I need to find a spanning tree using Prim's algorithm in O(n+m) and Kruskal's algorithm in O( m*a(m,n)).

我不知道如何做到这一点，确实需要如何的权重可以帮助我在这里的一些指导。

I have no idea how to do this and really need some guidance about how the weights can help me in here.

推荐答案

您可以边的权重排序更快。

You can sort edges weights faster.

在秩算法不需要0（M LG M）排序，你只可以使用数排序（或任何其他O（M）算法）。因此，最终的复杂性是那么O（M）为工会找到相分拣和O（MA（M））。总之它是O（MA（M））。

In Kruskal algorithm you don't need O(M lg M) sort, you just can use count sort (or any other O(M) algorithm). So the final complexity is then O(M) for sorting and O(Ma(m)) for union-find phase. In total it is O(Ma(m)).

有关的Prim算法的情况下。你并不需要使用堆，则需要7列出/队列/阵列/什么（有固定的时间插入和检索），每个重量。然后当你正在寻找您最便宜的检查出边，是这些名单中的一个非空（从最便宜的一个），并使用该优势。因为图7是一个常数，整个算法运行在O（M）的时间。

For the case of Prim algorithm. You don't need to use heap, you need 7 lists/queues/arrays/anything (with constant time insert and retrieval), one for each weight. And then when you are looking for cheapest outgoing edge you check is one of these lists is nonempty (from the cheapest one) and use that edge. Since 7 is a constant, whole algorithms runs in O(M) time.

这篇关于普里姆和Kruskal的算法的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！