概要
介绍了深度优先和广度优先的搜索方法
基本概念
open 表 保存未访问过的路径
close 表 保存访问过的路径，防止进入一个死循环。
具体算法
从某一个开始节点访问所有的可到达的顶点在很多场景下非常有用，例如下图中我们想从H点到C点如何遍历? 
具体步骤
- 从H开始，找到H的直接后继{B,D, L},从而构成了三条候选路径{H->B,H->D,H->L},此时{B,D,L}成为open vertices
- 将open vertices （及他们所属的路径)放入open表中。
- 从open表中选取一个vertex移除open表并生成此vertex的后继
- 例如我们选择了L，其后继为{M,F,H},
- 因为H已经被访问过了，所以不能放入open表中,否则会造成死循环，所以此时open表中有{B,D,M,F}
为了防止造成死循环，所以会有一个close表，记录已经被访问过的点，一旦一个点进入close表，就永远不会被访问第二次
- 如此继续知道找到目标顶点或者返回找不到目标顶点
注意：广度优先还是深度优先完全由从open表中的数据访问方式决定
* open表是先进后出则是深度优先
* open表是先进先出则是广度优先
样例及伪代码
深度优先样例
| Vertex visited (and hence closed) | Open list (stack top at left) |
|---|---|
| H | B D L |
| B | D D L |
| D | G J D L |
| G | J J D L |
| J | E I M J D L |
| E | K I M J D L |
| K | I M J D L |
| I | F M J D L |
| F | A L M J D L |
| A | L M J D L |
| L | M M J D L |
| M | C M J D L |
| C | M J D L |
深度优先伪代码
/* initialization */
queue openList = { startVertex }
/* loop */
while ( closedNodes != numberOfNodes && !openList.empty())
{
closingVertex = openList.dequeue();
increment number of closedNodes;
for each non-closed vertex not in the openList
and with an edge to it from closingVertex
{
openList.enqueue( vertex );
}
}广度优先类似
参考资料
http://jhave.org/algorithms/graphs/depthbreadth/depth-breadth.shtml