Построить список смежностей по представлению графа, заданному в виде матрицы смежностей - Lisp
Формулировка задачи:
Решение задачи: «Построить список смежностей по представлению графа, заданному в виде матрицы смежностей»
(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
будет содержаться список смежностей графа, который и будет возвращен функцией.