经典的图算法

约定不等于承诺〃 2022-06-07 03:14 161阅读 0赞

第一章、基本遍历  
一、深度优先搜索  
二、广度优先搜索  
此图遍历中最基本的俩种算法，BFS，DFS，入选本图算法十大算法，自是无可争议。  
因为，这俩种搜索算法，应用实为广泛而重要。

关于此BFS、DFS算法，更多，请参考：  
经典算法研究系列：四、教你通透彻底理解：BFS和DFS优先搜索算法  
[http://blog.csdn.net/v\_JULY\_v/archive/2011/01/01/6111353.aspx][http_blog.csdn.net_v_JULY_v_archive_2011_01_01_6111353.aspx]

三、A\*搜索算法  
DFS和BFS在展开子结点时均属于盲目型搜索，也就是说，  
它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。  
在运气不好的情形中，均需要试探完整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。

A\*算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。  
而A\*算法最为核心的部分，就在于它的一个估值函数的设计上：  
f(n)=g(n)+h(n)  
其中f(n)是每个可能试探点的估值，它有两部分组成：  
一部分，为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。  
一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。

更多，请参考：  
经典算法研究系列：一、A\*搜索算法  
[http://blog.csdn.net/v\_JULY\_v/archive/2010/12/23/6093380.aspx][http_blog.csdn.net_v_JULY_v_archive_2010_12_23_6093380.aspx]

附：  
Flood Fill  
LeeMaRS、wtzyb4446：  
图形学中Flood Fill是满水法填充，是用来填充区域的。  
就好比在一个地方一直到水，水会往四周满延开，直到高地阻挡。

Flood Fill就是从一个点开始往四周寻找相同的点填充，直到有不同的点为止。  
我们用的Flood Fill和这个差不多原理,就是BFS的一种形式.

假设在(i,j)滴好大一滴红墨水,然后水开始漫开,向它的上下左右染色,也就是(i-1,j),(i+1,j),(i,j-1),(i,j+1)这四个点.然后在分别再从这四个点开始向周围染色…直到碰到某种边界为止.

把这个转化为BFS的思想,就是队列中初始元素是(i,j),然后把(i,j)扩展状态,得到(i-1,j),(i+1,j),(i,j-1),(i,j+1)这四个状态,加入队列.把(i,j)出列,继续扩展下一个结点…如此

第二章、最短路径算法  
四、Dijkstra  
Dijkstra 算法，又叫迪科斯彻算法（Dijkstra），  
算法解决的是有向图中单个源点到其他顶点的最短路径问题。

此Dijkstra 算法已在本BLOG内俩篇文章中，有所具体阐述，请参见：  
I、经典算法研究系列：二、Dijkstra 算法初探  
[http://blog.csdn.net/v\_JULY\_v/archive/2010/12/24/6096981.aspx][http_blog.csdn.net_v_JULY_v_archive_2010_12_24_6096981.aspx]  
II、经典算法研究系列：二之续、彻底理解Dijkstra算法  
[http://blog.csdn.net/v\_JULY\_v/archive/2011/02/13/6182419.aspx][http_blog.csdn.net_v_JULY_v_archive_2011_02_13_6182419.aspx]

五、Bellman-Ford  
Bellman-Ford：  
求单源最短路，可以判断有无负权回路（若有，则不存在最短路），  
时效性较好，时间复杂度O（VE）。

附：  
SPFA：  
是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k<

[http_blog.csdn.net_v_JULY_v_archive_2011_01_01_6111353.aspx]: http://blog.csdn.net/v_JULY_v/archive/2011/01/01/6111353.aspx
[http_blog.csdn.net_v_JULY_v_archive_2010_12_23_6093380.aspx]: http://blog.csdn.net/v_JULY_v/archive/2010/12/23/6093380.aspx
[http_blog.csdn.net_v_JULY_v_archive_2010_12_24_6096981.aspx]: http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx
[http_blog.csdn.net_v_JULY_v_archive_2011_02_13_6182419.aspx]: http://blog.csdn.net/v_JULY_v/archive/2011/02/13/6182419.aspx