Проверить , является ли граф связным

@Sandrinchen3003 · Регистрация: 21.11.2018

Студворк — интернет-сервис помощи студентам

Доброго времени суток. В очередной раз без Вашей помощи не обойтись!!!!!!
ЗАДАНИЕ:
Дан неориентированный граф, содержащий n вершин. Проверить, является ли этот граф связным, где Т-связный, nil-не связный
Буду очень признательна, если поможете разобраться в теме и задании!

@Catstail · 26.12.2018, 12:25

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
;; Дать следующую вершину при обходе в глубину
 
(defun get-next (graph v chk)
  (iter (for e in graph) 
   (when (and (eq v (car e)) (not (member (cadr e) chk))) (return (cadr e)))
   (when (and (eq v (cadr e)) (not (member (car e) chk))) (return (car e)))))
 
;; Обход в глубину с построением каркаса
 
(defun dfs (graph s chk tree)
  (let ((next-v (get-next graph (car chk) chk)))
    (cond ((null s) tree)
          ((null next-v) (dfs graph (cdr s) chk tree))
          (t (dfs graph (cons next-v s) (cons next-v chk) (cons (list next-v (car chk)) tree))))))
 
;; Решение задачи
 
(defun task (graph)
  (let ((vlist (setof (apply 'append graph)))
        (tree  (dfs graph (list (caar graph)) (list (caar graph)) nil)))
    (= (length (setof (apply 'append tree))) (length vlist))))
 
(task '((a b) (b c) (c d)))
==> T
 
(task '((a b) (b c) (e d)))
==> NIL

Новые блоги и статьи Все статьи Все блоги /
Как писать чистый, тестируемый и качественный код на Python py-thonny 12.07.2025 Помню свой первый проект на Python. Работал тогда быстро, грязно, лишь бы работало. Код был похож на запутанный клубок - переменные по одной букве, функции на 200 строк, комментарии отсутствовали как. . .	Blazor и контроллер сервопривода IoT Meadow Maple Wired 11.07.2025 Я решил разобраться, как можно соединить современные веб-технологии с миром "железа". Интересная комбинация получилась из Blazor в качестве веб-интерфейса и микроконтроллера Meadow с его веб-сервером. . .	Генерация OpenQASM из кода Q# EggHead 10.07.2025 Летом 2024-го я начал эксперименты с библиотекой Q# Bridge, и знаете что? Она оказалась просто находкой для тех, кто работает на стыке разных квантовых экосистем. Основная фишка этой библиотеки -. . .	Изучаем новый шаблон ИИ-чата .NET AI Chat Web App stackOverflow 10.07.2025 В . NET появилось интересное обновление - новый шаблон ИИ-чата под названием . NET AI Chat Web App. Когда я впервые наткнулся на анонс этого шаблона, то сразу понял, что Microsoft наконец-то. . .	Результаты исследования от команды ARP (июль 2025 г.) Programma_Boinc 10.07.2025 Результаты исследования от команды ARP (июль 2025 г. ) Африканский проект по дождям (ARP) World Community Grid снова запущен! Мы рады поделиться обновленной информацией о нашем прогрессе с осени. . .
Angular vs Svelte - что лучше? Reangularity 09.07.2025 Сегодня рынок разделился на несколько четких категорий: тяжеловесы корпоративного уровня (Angular), гибкие универсалы (React), прогрессивные решения (Vue) и новая волна компилируемых фреймворков. . .	Code First и Database First в Entity Framework UnmanagedCoder 09.07.2025 Entity Framework дает нам свободу выбора, предлагая как Code First, так и Database First подходы. Но эта свобода порождает вечный вопрос — какой подход выбрать? Entity Framework — это. . .	Как использовать Bluetooth-модуль HC-05 с Arduino Wired 08.07.2025 Bluetooth - это технология, созданная чтобы заменить кабельные соединения. Обычно ее используют для связи небольших устройств: мобильных телефонов, ноутбуков, наушников и т. д. Работает она на частоте. . .	Руководство по структурам данных Python AI_Generated 08.07.2025 Я отчетливо помню свои первые серьезные проекты на Python - я писал код, он работал, заказчики были относительно довольны. Но однажды мой наставник, взглянув на мою реализацию поиска по огромному. . .	Тестирование энергоэффективности и скорости вычислений видеокарт в BOINC проектах Programma_Boinc 08.07.2025 Тестирование энергоэффективности и скорости вычислений видеокарт в BOINC проектах Опубликовано: 07. 07. 2025 Рубрика: Uncategorized Автор: AlexA Статья размещается на сайте с разрешения. . .

@Sandrinchen3003 0 / 0 / 0 Регистрация: 21.11.2018 Сообщений: 6

	Проверить , является ли граф связным 26.12.2018, 11:46. Показов 2297. Ответов 1 Метки homelisp, lisp (Все метки) Доброго времени суток. В очередной раз без Вашей помощи не обойтись!!!!!! ЗАДАНИЕ: Дан неориентированный граф, содержащий n вершин. Проверить, является ли этот граф связным, где Т-связный, nil-не связный Буду очень признательна, если поможете разобраться в теме и задании! 0

Опции темы