0

たとえば、次のようなグラフがあります。

(define graph
 '((a . (d b))
  (b . (c e))
  (c . (e)))
  (d . ())
  (e . ())

私は3つの関数を定義しています:

get-all-node: このグラフ内のすべてのノードのリストを(get-all-node graph)返します。(a b c d e)

find-node: これは、ノードがネストされたリストにあるかどうかに関係なく、ブール値の #t または #f を返します(find-node 'b '(a . (d b)))。

(find-inverse-node 'b '(a . (d b)))find-inverse-node: 特定のノードを含むペアの最初の要素を返します。たとえば、(a b)

get-all-node 関数で返された各要素を使用してグラフをループし、その要素がペアの 2 番目の部分にあるかどうかを調べ、含まれている場合は、見つかったノードのリストに追加します.

例:(loop-graph graph)返品((e b c) (e) (d) (c b) (d a) (b a))

私はこれを長い間試みましたが、成功していません。助けてください ！！前もって感謝します！！

4

1 に答える 1

0

個人的には、あなたが説明するプリミティブの観点からも解決策が見当たりません（ただし、グラフは私のお気に入りの主題ではありません）。したがって、ハッシュ テーブルの概念を知っていれば非常に理解しやすいソリューションを紹介します。これは Racket ですが、変更可能なハッシュ テーブルも従来の Scheme に存在します。

基本的に、最初のリストをループします。各（キー値...）要素について、キーが値のさまざまな要素であるハッシュマップを更新します...そして追加される要素はキーです。基本的に、キーと値の意味を逆にします。

ハッシュになってしまうので、これを最後にリストに変換する必要があります。

実装例:

(define (inv-graph g)
  (define h (make-hash))
  (map 
   (lambda (x)
     (define k (car x))
     (define v (cadr x))
     (map 
      (lambda (y) 
        (hash-set! h y (cons k (hash-ref h y '())))) 
      v))
   g)
  (hash-map h (lambda (k v) (cons k (list (reverse v))))))

そのような

(inv-graph '((a (d b)) (b (c e)) (c (e)) (d ()) (e ())))
=> '((b (a)) (d (a)) (e (b c)) (c (b)))
于 2013-11-07T20:36:31.907 に答える