将图形的BFS代码转换为DFS代码

本文介绍了将图形的BFS代码转换为DFS代码的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

很抱歉，这个问题听起来模棱两可，但是我在采访中被问到了.

I'm sorry if this question sounds ambiguous but I was asked this in an interview.

在图形/树中为BFS编写程序.

我使用队列编写了流行的代码.

I wrote the popular code using a queue.

现在，他要求我通过只修改我刚刚编写的BFS代码的一行来将其转换为DFS代码.

Now he asked me to convert it to a DFS code by modifying just one line of the BFS code I had just written.

我唯一想到的答案是对DFS使用堆栈.然后，我使用2个队列实现了堆栈.

The only answer I could think of was to use a stack for DFS. Then I implemented the stack using 2 queues.

所以最后我的答案是:为BFS使用1个队列.对于DFS，请改用2个队列.

So in the end my answer was: use 1 queue for BFS. for DFS use 2 queues instead.

他没有给我任何反馈.没有被雇用:(

He did not give me any feedback . Wasn't hired :(

我的方法很好还是有更好的方法?请帮忙.:)

Is my approach fine or is there a better approach? Please help. :)

推荐答案

我假设您的BFS答案将一直将队列中的节点(FIFO数据结构)删除，直到完成为止，并且对于每个被删除/访问的节点，将该节点的子节点添加到队列中，因为您要在到目前为止找到的所有节点之后访问这些节点.

I'll assume that your BFS answer would keep removing nodes from the queue (a FIFO data structure) until done, and for each node removed/visited, would add that node's children to the queue, because you want to visit those nodes AFTER all the ones you've found out about so far.

在DFS中，您想要访问到目前为止已保存的其他任何子项，因此需要LIFO数据结构.

In DFS, you want to visit those children BEFORE any of the others you have saved so far, so you want a LIFO data structure.

或者，如@joews所说:将队列交换为堆栈.

Or, as @joews said: swap the queue for a stack.