每周学习日记5

正文

• 这周学习了两种图的遍历方法还有普里姆(Prim)算法
  。

深度优先搜索

由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。为了避免这种情况的出现，在实施这一方法时，定出一个深度界限，在搜索达到这一深度界限而且尚未找到目标时，即返回重找，所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解（最短路径）。

广度优先搜索

它是从根节点（起始节点）开始，按层进行搜索，也就是按层来扩展节点。所谓按层扩展，就是前一层的节点扩展完毕后才进行下一层节点的扩展，直到得到目标节点为止。
这种搜索方式的优点是，只要存在有任何解答的话，它能保证最终找到由起始节点到目标节点的最短路径的解，但它的缺点是往往搜索过程很长。

普里姆(Prim)算法

从连通网络 N = { V, E }中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边( u0, v1 ), 将其顶点v1加入到生成树顶点集合U中。
以后每一步从一个顶点在 U 中,而另一个顶点在 (V- U) 中的各条边中选择权值最小的边(u, v), 把它不在U 中的顶点加入到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。

结束语！

明天会更好！.

学习日记5

原文：https://www.cnblogs.com/iGGBond/p/13021965.html