用普里姆(Prim)算法求具有 n 个顶点 e 条边的图的最

[填空题]

用普里姆(Prim)算法求具有 n 个顶点 e 条边的图的最小生成树的时间复杂度为1；用克鲁斯卡尔(Kruskal)算法的时间复杂度是2。

查看正确选项

Rnanprince

首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点。）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树。

首先，初始化部分所需时间为Ο(|V|+|E|)。其次，在|V|-1次循环过程中，一方面要遍历各个顶点的邻接边，一共需要Ο(|E|)的时间；另一方面在每次循环中查找轻边需要对所有顶点遍历一遍，每次循环需时Ο(|V|)。因此算法的时间复杂度T(n) =Ο(|V|+|E|) +Ο(|E|) + (|V|-1)Ο(|V|) =Ο(|V|^2+|E|) =Ο(|V|^2)。

边数较多可以用Prim，因为它是每次加一个顶点，对边数多的适用。

-------------------------------------------------------------

Kruskal算法在找最小生成树结点之前，需要对权重从小到大进行排序。将排序好的权重边依次加入到最小生成树中，（如果加入时产生回路就跳过这条边，加入下一条边）。当所有的结点都加入到最小生成树中后，就找到了这个连通图的最小生成树。

算法总的时间取决于排序步，即Ο(|E| log |E|)。

边数较少可以用Kruskal,因为Kruskal算法每次查找最短的边。

即n^2;eloge

发表于 2018-05-17 17:40:57 回复(0)