BFS的路径记录问题。。

你指的“工业”是那个“工业”吗？ C链表... 另外STL是神马？可以吃吗？ 【 在 FaceBasin 的大作中提到: 】 : 问题有点二，没敢发到ACM版。。 : 如题，BFS会形成一个链状的状态结构，一个状态总是指向其前一个状态。遍历完成后从最后一个状态倒回去，然后输出解就行。于是可以开两个够大的数组记录状态和前驱，偷懒的话似乎直接stl map也行。。 : 但还是很好奇会不会有更效率的记录办法，如果是工业级别的代码，会用何种方式实现呢？ : ...................

【 在 FaceBasin 的大作中提到: 】 : 问题有点二，没敢发到ACM版。。 : 如题，BFS会形成一个链状的状态结构，一个状态总是指向其前一个状态。遍历完成后从最后一个状态倒回去，然后输出解就行。于是可以开两个够大的数组记录状态和前驱，偷懒的话似乎直接stl map也行。。 : 但还是很好奇会不会有更效率的记录办法，如果是工业级别的代码，会用何种方式实现呢？ : ................... BFS 还是 DFS？BFS会形成什么样的链状的状态结构？

吃多了会消化不良…… 【 在 tonyjansan 的大作中提到: 】 : 你指的“工业”是那个“工业”吗？ C链表... : 另外STL是神马？可以吃吗？ :

是BFS。。大概我描述的不太对。。就是记录路径的时候，先记下当前遍历到的状态，然后再记下它的上一个状态，似乎有点链栈的意思？好像越描越黑。。 【 在 jffifa 的大作中提到: 】 : : BFS 还是 DFS？BFS会形成什么样的链状的状态结构？

【 在 FaceBasin 的大作中提到: 】 : 是BFS。。大概我描述的不太对。。就是记录路径的时候，先记下当前遍历到的状态，然后再记下它的上一个状态，似乎有点链栈的意思？好像越描越黑。。 : BFS记录路径？你的意思是记录每个节点访问的前继？这个是个颗树啊？

对对，书上也说是树，但是我又怕和DFS的那个树形解空间混起来。。 【 在 jffifa 的大作中提到: 】 : : BFS记录路径？你的意思是记录每个节点访问的前继？这个是个颗树啊？

不考虑特殊优化的话，每个节点加一个ptr纪录父节点。 搜到解了之后回溯即可。工业也得这么记，只不过纪录的方式可能会根据数据量大小有所不同。