1

我的问题主要与算法相关，而不是特定于特定的编程语言

假设我们有一个由列表列表表示的图，其中每个内部列表代表两个节点和一个编号的边，是否可以仅使用以下 12 个函数来实现递归 BFS（广度优先搜索）函数？我们的 bfs 递归函数应该有 5 个参数：

  • 要搜索的图形
  • 要查找的元素
  • 搜索队列
  • 访问节点列表
  • 我们正在查看的当前元素

图表示例：

    e1
   / \
  e2  e3
  | \  |
  e5  e4

((e1 1 e2) (e1 2 e3) (e2 3 e4) (e3 4 e4) (e2 5 e5))

在以下函数中，我将图表中的每个单独列表称为图表元素

以下是功能：

create-graph              ; creates an empty list
is-graph-element:         ; check if a list is of the format above (for graph elements)
element-contains-node     ; check if a graph element contains an atom representing a node (e.g., a)
is-member                 ; check if a [generic] list contains an atom
push-unique               ; gets a list and an atom and inserts it at the end of the list if it's not already there
remove-visited            ; gets a graph (list of list), removing all the graph elements containing the specified atom
remove-all-visited        ; same as above, but we can pass a list of atoms to be removed
del-from-list             ; remove all occurrences of an atom from a list
del-all-from-list         ; same as above, but we can pass a list of atoms to be removed
first-member              ; return the first member of a graph element (e.g., for [a, 1, b], return a
third-member              ; return third member of a graph element
graph-to-list             ; receives a graph and returns a flat list of all first and third members listed in order

这就是我实现递归 BFS 函数的方式：

  • 我的递归调用实际上有两个基本情况：当队列为空时（这意味着我们无法到达我们正在搜索的元素），以及当要从队列中弹出的元素是我们正在搜索的元素时
  • 在每次调用中，我都定义了一个函数来查找从当前节点开始的路径（找到我们可以去的节点），然后我将这些节点推送到队列中
  • 然后我将当前节点推送到访问列表并重复

我的问题是我定义了两个不在上面的函数列表中的函数（一个用于查找路径，一个用于将这些路径的目标节点推送到搜索队列）。

我想知道是否可以仅使用这些函数来执行递归 BFS？

PS：我们为图表提供的列表应该代表一个无向图，但我不确定这将如何改变问题

真诚感谢任何形式的帮助...

4

0 回答 0