如何在图形

应用迭代深化深度优先搜索（IDDFS）

我试图在树的形式第一次做这样的事图形应用IDDFS，结果是这样的：

At level 1: d,e,p 
At level 2: d,b,e,c,e,h,r,p,q 
At level 3: d,b,a,e,h,c,a,e,h,q,p,r,f,p,q 
At level 4: d,b,a,e,h,p,q,c,a,e,h,q,p,q,r,f,c,GOAL

我我对路径中那些重复的节点感到困惑，我们能消除它们还是会出现在最终路径中？

这是遍历图达到GOAL的正确方法吗？以及我们如何知道在图中下一个访问哪个节点（例如树中我们从左到右）。

如果我们在同一个图上应用DFS和BFS，路径是什么？

DFS结果和IDDFS会有什么不同吗？这似乎是类似

2016-11-14 Kashiii

这是一个功课题吗？ –

不做作业，我只是练习 – Kashiii

我找不到任何有用的材料在互联网上，关于如何在图表上应用IDDFS，这些都是我很少混淆 – Kashiii

是的，你可以和应该得到，当你实现DFS，通过保持你已经访问过的节点已经轨道摆脱重复节点。如果你不这样做，你的代码在找到一个循环时不会终止。不要忘记清除每个新级别的访问节点集。因此，从您的列表中删除已访问的节点，除非重要的是包含正在考虑但未被重新访问的节点。
如果你写出了BFS和DFS的扩展，你会发现IDDFS开始看起来像BFS，并且最终看起来越来越像DFS，越是提升级别。当等级=最长路径长度时，瞧，你会得到DFS，这并不奇怪，因为IDDFS 是 DFS，只有在给定数量的路径被切断;在这种特殊情况下，这个数字没有效果，因为没有足够长的路径可以被切断。
图中的顺序没有很好的定义。你自己选择一个或另一个订单。如果您随机选择下一个节点，则会得到非确定性算法。如果你选择他们，不知道，按字母顺序，那么你会得到一些决定论。有时候这种区别并不重要，但确定性对调试代码很有好处，等等。现在，当你做这个练习时，你会看到模式，所以最好省略随机性。

你的问题确实看起来像家庭作业。 ;）

2016-11-23 16:34:45

回答