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)))返回#t，因为如果我使用memq，它根本不起作用。

find-inverse-node：返回对中包含特定节点的第一个元素，例如：(find-inverse-node 'b '(a . (d b)))将返回(a b)

我想遍历图形，使用 get-all-node 函数中返回的每个元素来查找该元素是否在该对的第二部分中，如果它在，则将其附加到找到的节点列表中.

例如：(loop-graph graph)返回((e b c) (e) (d) (c b) (d a) (b a))

我试图这样做很长时间，但没有成功。请帮忙 ！！提前致谢！！

4

1 回答 1

0

我个人也没有看到您描述的原语的解决方案（但是，图表不是我最喜欢的主题）。因此，如果您了解哈希表的概念，我将向您展示一个非常容易理解的解决方案。这是 Racket，但可变哈希表也存在于经典方案中。

基本上，您遍历初始列表。对于每个（键值...）元素，您更新一个哈希映射，其中键是值的各种元素...，添加的元素是键。所以基本上你颠倒了键和值的含义。

由于您最终得到一个哈希，因此需要在最后将其转换为一个列表。

示例实现：

(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 回答