tree - 在 lisp 中创建一棵树

Question

我一直在用 lisp 对树进行大量研究，并试图解决一个 uva 问题(11695 飞行计划(http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2742)供引用)。我目前已经解决了大部分问题，但在将输入更改为树的第一个障碍上我有点难过。输入的示例将采用

的形式

1 2

2 3

3 4

我在 Internet 上遇到了很多关于如何设置树的信息，但大多数情况下，数字本身适合在树中而不是采用这种格式。我也研究过图论，但这让我无处可去。

我在这方面取得的唯一进展是我可能将每个“路径”放入它们自己的列表中，并且基本观察到每个列表的第一个是父列表，每个列表的第二个将是成为他们的 child (也可能成为另一个 child 的 parent )

如果有人对我如何处理这个问题有任何建议，那就太好了。我还没有找到任何我可以在线应用的东西，所以我想我会看看其他人的想法是什么。

我对 Lisp 比较陌生，但我对它的工作原理有相当好的理解。

Answer 1

您可以只创建一个 n 元素(城市)的数组，最初全部为 NIL，然后对于每一对 a/b 您只需做

(push b (aref cities a))
(push a (aref cities b))

一旦读取了所有定义，数组的第 k 元素将是您可以从城市 k 乘坐直飞航类到达的城市列表。