对一个有向图，要找到从起始到终点的一条路径，既可以用图搜索，也可以用树搜索
- 图搜索不允许重复访问结点，即OPEN表 ∩ CLOSED表 = ø，此处重复的结点不一定是父节点。
- 树搜索允许重复访问结点。
下面以A* 搜索为例，分别解释图搜索和树搜索。
例子
A* 树搜索
允许重复访问结点
| 扩展路径 | 拓展但未经过的路径 |
|---|---|
| S | S-A(2+0); S-B(1+6); S-G(9+0) |
| S-A | S-A-D(5+1); S-B(1+6); S-A-C(4+4); S-G(9+0) |
| S-A-D | S-B(1+6); S-A-C(4+4); S-G(9+0); S-A-D-G(9+0) |
| S-B | S-B-D(3+1); S-A-C(4+4); S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
| S-B-D | S-B-D-G(7+0); S-A-C(4+4); S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
| S-B-D-G | S-A-C(4+4); S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
A* 图搜索
不允许重复访问结点，设置了CLOSED表
| 扩展路径 | CLOSED表 | 拓展但未经过的路径 |
|---|---|---|
| S | S | S-A(2+0); S-B(1+6); S-G(9+0) |
| S-A | S A | S-A-D(5+1); S-B(1+6); S-A-C(4+4); S-G(9+0) |
| S-A-D | S A D | S-B(1+6);S-A-C(4+4); S-G(9+0); S-A-D-G(9+0) |
| S-B | S A D B | S-A-C(4+4); S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
| S-A-C | S A D B C | S-A-C-G(8+0); S-G(9+0);S-A-D-G(9+0); S-B-E(5+10) |
| S-A-C-G | S A D B C G | S-G(9+0); S-A-D-G(9+0); S-B-E(5+10) |
