方案：递归广度优先树遍历

发布于 2024-08-30 17:51:47 字数 211 浏览 2 评论 0原文

我正在绞尽脑汁试图找出如何在方案中实现广度优先树遍历。我已经用 Java 和 C++ 完成了。如果我有代码，我会发布它，但我不确定到底如何开始。

给定下面的树定义，如何使用递归实现广度优先搜索？

(define tree1 '( A ( B (C () ()) (D () ()) ) (E (F () ()) (G () ())) ))

原文

I'm pulling my hair out trying to figure out how to implement breadth first tree traversal in scheme. I've done it in Java and C++. If I had code, I'd post it but I'm not sure how exactly to begin.

Given the tree definition below, how to implement breadth first search using recursion?

(define tree1 '( A ( B (C () ()) (D () ()) ) (E (F () ()) (G () ())) ))

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

伪装你 2024-09-06 17:51:47

我敢打赌，当您用其他语言执行此操作时，您使用了 dfs 的堆栈和 bfs 的队列。当您进行深度优先搜索时，您基本上是使用堆栈来决定下一步要探索哪个节点，而递归为您提供了一个函数调用堆栈，因此很容易概念化两者如何相互镜像。使用广度优先搜索，问题就变成了，如何递归地遍历队列？

现在回想一下，任何可以迭代执行的操作，都可以递归执行。在您可能会写“while x < 10: x += 1”的地方，您可以改为写

(define (my-loop x)
  (if (< x 10)
      (my-loop (+ x 1))
      ... ;; your base case
      ))

，突然您正在递归地进行迭代。伟大的。

所以我们有这个队列。我们把东西放在一端，把东西从另一端取下。就像我们在上面的循环中传递循环控制变量 x 一样，您必须显式传递队列。在下一个“迭代”中，现在成为下一个递归级别，您需要将一些新的子级放入队列中，并且下一个递归将从队列的另一端取出一个子级，或者停止（返回）如果没有更多的孩子。

现在，调用堆栈不再反映您在树中的位置，因此很难看出为什么递归会更好或更直观，但它总是可能的。

希望有帮助，
格雷姆

I bet when you did this in other languages you used a stack for dfs and a queue for bfs. When you do depth first search, you're fundamentally using a stack to decide which node to explore next, and recursion gives you a function call stack, so it's easy to conceptualize how the two mirror each other. With breadth first search, the question becomes, how do you traverse a queue recursively?

Now recall that anything you can do iteratively, you can do recursively. Where you might write "while x < 10: x += 1", you can instead write

(define (my-loop x)
  (if (< x 10)
      (my-loop (+ x 1))
      ... ;; your base case
      ))

and suddenly you're doing the iteration recursively. Great.

So we have this queue. We put things on one end, take things off the other. Just like we passed around the loop control variable x in the loop above, you'll have to explicitly pass around the queue. In the next "iteration", which becomes now the next level of recursion, you'll want to have put some new children on the queue, and that next recursion will take one child off the other end of the queue, or stop (return) if there are no more children.

Now the call stack no longer mirrors your location in the tree, so it's hard to see why recursion would be better or more intuitive, but it's always possible.

Hope that helps,
Grem

回复收藏 0 原文

一袭白衣梦中忆 2024-09-06 17:51:47

这是作业吗？如果是这样，请停止阅读:)。

BFS算法：如果队列为空，则放弃。否则，将队列分为第一个和剩余，检查第一个是否是您想要的，否则重复使用包含剩余元素和所有新可到达元素的队列。

当然，我可以在方案中“说”同一句话：

#lang scheme

(define (bfs pred queue)
  (match queue
    [empty #f]
    [(cons elt queue-rest) 
     (or (pred elt)
         (bfs pred (append queue-rest (remove* queue-rest (reachable-from elt)))))]))

完全未经测试，几乎肯定有错误（尽管不是在测量理论意义上:)）
您需要自己的图形和图形表示形式。 “可到达的来源”。
列表并不是一个很好的队列实现。

Is this homework? If so, stop reading :).

BFS algorithm: if the queue is empty, give up. Otherwise, separate the queue into first and remaining, check to see if the first is the one you want, otherwise recur with a queue containing the remaining elements and all of the newly reachable ones.

Of course, I can "say" the same sentence in Scheme:

#lang scheme

(define (bfs pred queue)
  (match queue
    [empty #f]
    [(cons elt queue-rest) 
     (or (pred elt)
         (bfs pred (append queue-rest (remove* queue-rest (reachable-from elt)))))]))

totally untested, almost surely buggy (altho not in the measure-theoretic sense :))
you need your own representation of graphs & "reachable-from".
lists aren't a great queue implementation.

回复收藏 0 原文

甲如呢乙后呢 2024-09-06 17:51:47

你可以这样做：
有一个递归辅助函数，深度为 n，并将元素与行连接...输出将是一个列表，其中包含深度为 n 的树的所有元素。

(defun findAtN (tree n)
(cond ((equal tree nil) nil)
      ((equal (n 0)     (car tree))
      (t                (append (findAtN (cadr tree) (- n 1))
                                (findAtN (caddr tree) (- n 1))))))

然后是增加深度的第二个函数，在每个级别中搜索给定的节点。

(defun ContainsElt (tree Elt n)
(cond ((equal (findAtN tree n) nil)   nil)
      ((member Elt (findAtN tree n))  true)
      (t                              (ContainsElt tree Elt (+ n 1)))))

这是未经测试的，并且根据你的 lisp 参数/方言可能略有不同，以及如果你想做的不仅仅是测试一个项目是否在树中，但也许它会帮助你了解如何做到这一点。

you could do something like this:
have a recursive helper function that goes to depth n, and concats the elements with a row... the output would be a list with all elements of the tree at depth n.

(defun findAtN (tree n)
(cond ((equal tree nil) nil)
      ((equal (n 0)     (car tree))
      (t                (append (findAtN (cadr tree) (- n 1))
                                (findAtN (caddr tree) (- n 1))))))

then a second function that increases the depth, searching each level for a given node.

(defun ContainsElt (tree Elt n)
(cond ((equal (findAtN tree n) nil)   nil)
      ((member Elt (findAtN tree n))  true)
      (t                              (ContainsElt tree Elt (+ n 1)))))

This is untested and probably slightly different based on your parameters/dialect of lisp, as well as if you want to do more than just test if an item is in the tree, but maybe it'd help with an idea how to do it.

回复收藏 0 原文

~没有更多了~