图搜索算法UCS（一致代价搜索）通俗易懂图示详解

一致代价搜索实际上是在BFS（广度优先搜索算法）的基础上进行扩展的，我们在上一篇博客图搜索算法BFS和DFS通俗易懂图示详解中提到，BFS是基于队列数据结构的，既然UCS是BFS的扩展，那么UCS一定也是基于队列的，由此我们很容易想到，UCS是基于优先级队列数据结构的。

我们考虑从成都出发，搜索石家庄。
首先优先级队列（以下简称PQ）中只有成都，但它是起点，所以父节点为空

父节点	空
子节点	成都
代价	0

接下来从成都开始搜索，没有找到目标，把成都从PQ弹出，加入它的三个邻接城市西宁，兰州，重庆

父节点	空	成都	成都	成都
子节点	成都	西宁	兰州	重庆
代价	0	61	100	43

此时搜索重庆代价最小，将重庆弹出PQ，加入它的两个邻接城市西安与武汉，此时从成都到西安的代价变成了43+76=119，从成都到武汉的代价变成43+118=161

父节点	空	成都	成都	成都	重庆	重庆
子节点	成都	西宁	兰州	重庆	西安	武汉
代价	0	61	100	43	119	161

此时最小代价城市变成了西宁，把西宁从PQ弹出，它的邻接城市有兰州，银川，成都，但是成都不在PQ中不再考虑，而尽管兰州已在PQ中，但由于从成都到西宁再到兰州的代价大于从成都直接到兰州，所以不再将其加入PQ(倘若前者小于后者代价则需要替换掉原来的代价)，所以将尚未入PQ的银川加入PQ

父节点	空	成都	成都	成都	重庆	重庆	西宁
子节点	成都	西宁	兰州	重庆	西安	武汉	银川
代价	0	61	100	43	119	161	119

接下来最小代价城市为兰州，将其弹出，其邻接城市均已在PQ中且无需更新代价

父节点	空	成都	成都	成都	重庆	重庆	西宁
子节点	成都	西宁	兰州	重庆	西安	武汉	银川
代价	0	61	100	43	119	161	119

接下来最小代价城市有两个，其代价均为119，任选一个即可，这里以西安作为最小代价城市，其邻接城市中需要加入PQ的有郑州和太原，并将西安弹出

父节点	空	成都	成都	成都	重庆	重庆	西宁	西安	西安
子节点	成都	西宁	兰州	重庆	西安	武汉	银川	太原	郑州
代价	0	61	100	43	119	161	119	187	163

接下来是银川，将其从PQ弹出，其邻接城市均已被访问且不需要更新代价

父节点	空	成都	成都	成都	重庆	重庆	西宁	西安	西安
子节点	成都	西宁	兰州	重庆	西安	武汉	银川	太原	郑州
代价	0	61	100	43	119	161	119	187	163

然后是武汉，将其从PQ弹出，其邻接城市均已被访问且不需要更新代价

父节点	空	成都	成都	成都	重庆	重庆	西宁	西安	西安
子节点	成都	西宁	兰州	重庆	西安	武汉	银川	太原	郑州
代价	0	61	100	43	119	161	119	187	163

接下来是郑州，这时把石家庄加入PQ，然后把郑州弹出

父节点	空	成都	成都	成都	重庆	重庆	西宁	西安	西安	郑州
子节点	成都	西宁	兰州	重庆	西安	武汉	银川	太原	郑州	石家庄
代价	0	61	100	43	119	161	119	187	163	201

然后是太原，将其从PQ弹出，其邻接城市均已被访问且不需要更新代价

父节点	空	成都	成都	成都	重庆	重庆	西宁	西安	西安	郑州
子节点	成都	西宁	兰州	重庆	西安	武汉	银川	太原	郑州	石家庄
代价	0	61	100	43	119	161	119	187	163	201

最后将石家庄弹出，这样就找到了从成都到石家庄花费最少代价的路径

父节点	空	成都	成都	成都	重庆	重庆	西宁	西安	西安	郑州
子节点	成都	西宁	兰州	重庆	西安	武汉	银川	太原	郑州	石家庄
代价	0	61	100	43	119	161	119	187	163	201

回溯得到路径：成都 --> 重庆 --> 西安 --> 郑州 --> 石家庄,总代价为201