Здравствуйте,

необходимо составить для графа, заданного списком ребер, соответствующую ему структуру смежности. То есть, если есть граф, состоящий из четырех вершин:

((1 2) (1 3) (1 4) (3 4)),

то соответствующая списку ребер структура смежности будет выглядеть так:

((1 . (2 3 4)) (2 . (1)) (3 . (1 4)) (4 . (1 3))),

то есть это список точечных пар, где левая часть - какая-то вершина, а правая - список всех других вершин, смежных с этой какой-то вершиной.

Самое трудное в этой проблеме - затолкать в структуру смежности (4 . (1 3)), т. к. 4 не является головой какого-либо вложенного в список ребер списка.

Буду надеяться на Вашу помощь.

я не знаю LISP, но если у Вас сложность с тем чтобы запихнуть пару для вершины, у которой нет выходов, то может быть продублировать каждый вектор по принципу "туда и обратно"?

в смысле: у Вас есть вектор (A B) -- добавьте также вектор (B A) и т.д.

можете так сделать? решится тогда Ваша проблема?

Код

(defun graph-adjacency (edges)   (let* ((vertexes (remove-duplicates (apply #'append edges)))          (graph-adjacency (mapcar #'(lambda (vertex) (cons vertex '()))                                   vertexes)))     (mapc #'(lambda (edge)               (destructuring-bind (from to)                   edge                 (push to (cdr (assoc from graph-adjacency)))                 (push from (cdr (assoc to graph-adjacency)))))           edges)     graph-adjacency)) (graph-adjacency '((1 2) (1 3) (1 4) (3 4))) => ((2 1) (1 4 3 2) (3 4 1) (4 3 1))

P.S: '(1 . (2 3 4)) == (1 2 3 4) == (cons 1 (2 3 4))

M Cr@$h

svg ++ за красивый код для новичка.