私の質問は主にアルゴリズム関連であり、特定のプログラミング言語に固有のものではありません
各内部リストが 2 つのノードと番号付きエッジを表すリストのリストで表されるグラフがあると仮定すると、次の 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 関数を実装した方法です。
- 再帰呼び出しには、実際には 2 つの基本ケースがあります。キューが空の場合 (つまり、検索していた要素に到達できなかったことを意味します)、およびキューからポップされる要素が検索していた要素である場合です。
- 各呼び出しで、現在のノードからパスを検索する関数を定義し (移動できるノードを検索するため)、これらのノードをキューにプッシュします。
- 次に、現在のノードを訪問済みリストにプッシュし、繰り返します
私の問題は、上記の関数リストにない 2 つの関数 (パスを検索する関数と、それらのパスのターゲット ノードを検索キューにプッシュする関数) を定義したことです。
これらの関数のみを使用して再帰的な BFS を実行できるかどうか疑問に思っていましたか?
PS: グラフのリストは無向グラフを表すはずですが、それが問題をどのように変えるかはわかりません
どんな種類の助けも心から感謝しています...