BFS\DFS\A*\Dijkstra\Prim算法等的简介

(一)

    首先来说说广度优先算法(BFS)和深度优先算法(DFS)。这两种遍历方法在其他图的算法中多有应用。

    广度优先搜索算法的特点就是需要先访问完每个顶点的邻接结点(二叉树就两个),不深入,保存这个节点,再访问下一层的。所以常用的就是队列“先进先出”的特性存储结点。

    而深度优先算法(DFS)的特点就是访问完 一个顶点的一个邻接结点后,接着以这个邻接结点为顶点访问下一个。所以常用的就是栈“后进先出”的特性存储结点。

   二者的相同点就是:算法的复杂度都为O(V+E),其中广度优先算法存储占用内存多,能够得到全局最优解;而深度优先算法占用内存少些,一定条件下得到接近解,运行的速度快。

(二)

   A*算法又叫A-Star算法,是静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法,在游戏寻路中应用较多。

   它的特点是,寻路过程中,即考虑与当前点与初始点的距离,又考虑当前点与目标点的距离,这样就避免了盲目搜索全局点的问题。

(三)

   Dijkstra算法用于构建单源点的最短路径树(MST)(有向图无向图,非负),而Prim算法,多应用于树,构建最小生成树等(无向图)。

   形象一点来说,Dijkstra算法用于构建两个村庄路径最短,而Prim算法用于构建几个村庄道路最短。也就是说,Dijkstra的加上了当前顶点到下一个结点的距离,而Prim考虑的只有全局相邻节点最小距离的权值。

相关文章

相关标签/搜索