下列算法中，没有使用贪心策略的是:

[单选题]

下列算法中，没有使用贪心策略的是:

```
Prim算法
```
```
Kruskal算法
```
```
Dijkstra算法
```
```
KMP算法
```

查看答案及解析

gendlee

A.Prim算法 ：属于贪心策略。
最小树生成概念。G=(V, E),首先置S＝{1},只要S是V的真子集，就进行如下的贪心选择，选取满足条件i属于S，j属于V－S，且 matrix[i][j]是最小的边，将j加入到S中，这个过程一直持续到S＝V为止，在这个过程中选择的所有边恰好构

成G的一棵最小生成树。

B. Kruskal算法： 属于贪心策略。

不停地循环，每一次都寻找两个顶点，这两个顶点不在同一个真子集里，且边上的权值最小。 把找到的这两个顶点联合起来。 初始时，每个顶点各自属于自己的子集合，共n个子集合。 每一步操作，都会将两个子集合融合成一个，进而减少一个子集合。 结束时，所有的顶点都在同一个子集合里，这个子集合就是最小生成树。

C .Dijkstra算法: 属于贪心策略

该算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断地做贪心选择来扩充这个集合。

D. KMP算法：不属于贪心算法，而是递推策略。

KMP算法是一种改进的字符串匹配算法。为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀，在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。

编辑于 2015-10-18 15:59:17 回复(0)