如果采用邻接矩阵作为图的存储结构，则求最小生成树的Prim算

[单选题]

如果采用邻接矩阵作为图的存储结构，则求最小生成树的Prim算法的时间复杂度为（）

```
O(n^2)
```
```
O(n)
```
```
O(n+e)
```
```
O(1)
```

Rnanprince

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

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

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

即n^2;

编辑于 2018-05-17 17:42:42 回复(0)