Построить список смежностей по представлению графа, заданному в виде матрицы смежностей - Lisp

Узнай цену своей работы

Формулировка задачи:

Программа должна строить список смежностей по представлению графа, заданному в виде матрицы смежностей.

Решение задачи: «Построить список смежностей по представлению графа, заданному в виде матрицы смежностей»

textual
Листинг программы
(defun task (matr)
  (let ((n (length matr))
        (r nil))
     (dotimes (i n r)
       (dotimes (j (- n i) t)
          (when (/= 0 (nth (+ i j) (nth i matr))) (setq r (append r (list (list (+ i 1) (+ j i 1))))))))))
 
==> TASK
 
(task '((0 1 1 0) (1 0 0 1) (1 0 0 0) (0 1 0 0)))
 
==> ((1 2) (1 3) (2 4))
 
(task '((0 1 1 1) (1 0 0 1) (1 0 0 0) (1 1 0 0)))
 
==> ((1 2) (1 3) (1 4) (2 4))
 
(task '((0 1 1 1 0) (1 0 0 1 0) (1 0 0 0 1) (1 1 0 0 0) (0 0 1 0 0)))
 
==> ((1 2) (1 3) (1 4) (2 4) (3 5))

Объяснение кода листинга программы

В данном коде реализуется функция task, которая принимает на вход матрицу смежностей графа в виде списка списков и возвращает список смежностей вершин графа. Список смежностей вершины графа — это список смежных вершин этой вершины, то есть вершин, которые находятся в одной вершине графа. Внутри функции используется цикл dotimes, который перебирает все возможные значения индексов i и j от 1 до n-1, где n — длина матрицы смежностей. На каждой итерации цикла проверяется, является ли элемент матрицы смежностей по индексам i и j ненулевым. Если да, то это значит, что вершины с индексами i и j являются смежными, и их можно добавить в список смежностей результирующего графа. Также на каждой итерации цикла внутренний цикл dotimes перебирает все значения индексов j от 1 до i-1, чтобы проверить все возможные смежности вершины с индексом i. Если элемент матрицы смежностей по индексам i и j ненулевой, то это значит, что вершины с индексами i и j являются смежными, и их можно добавить в список смежностей результирующего графа. В итоге, после выполнения всех итераций цикла, в переменной r будет содержаться список смежностей графа, который и будет возвращен функцией.

Оцени полезность:

13   голосов , оценка 4.231 из 5
Похожие ответы