我正在比较两本书之间的图形遍历材料：CLRS的算法导论，第3版（简称为CLRS）和RN的人工智能：现代方法，第3版（简称为AIMA） .
在广度优先搜索和深度优先搜索的两个部分中，我注意到CLRS通过分别对白色，灰色和黑色着色来跟踪未访问的节点，边界节点和访问节点，同时AIMA跟踪未访问的，边界和访问的通过跟踪图形及其节点外部的数据结构来跟踪边界和受访节点 .
似乎AIMA中使用数据结构来跟踪边界和访问节点的方法更有效，并且在图中可能存在无限节点的情况下效果更好 . 是否有人更喜欢图形着色，或者两者之间有什么区别？
1 回答
在写这个问题时，我理解了答案：存在一些差异 .
CLRS正在处理这些部分中的有限图，而AIMA从一开始就处理未知和可能无限大小的图 . CLRS搜索算法的第一步是将每个图形节点着色为白色，因此这不适用于AIMA的情况 .
在AIMA中，如前所述，图表不应该像CLRS那样完整地遍历，因为至少部分是因为它可能是大的或无限大的 . 因此，当在AIMA的图形搜索中首次发现节点时，它立即被放置在边界中，因此白色着色没有用处，发现的每个节点都在边界或被访问，因此三色方案没有意义那种情况 .
这些图搜索的用例不同 . 在AIMA中，图搜索用于查找导致问题的解决方案目标状态的一系列操作 . 在CLRS中，遍历节点是一种学习整个图的属性的方法 . 参见例如：https://stackoverflow.com/a/38936312/5834035