Существует ли путь между двумя вершинами графа

@Wizard13 · Регистрация: 18.05.2017

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

Текст задачи:
"Граф задан с помощью цепных списков. Определить, существует ли путь между двумя заданными вершинами."
Так как термин "цепные списки" мне не понятен, я граф представляю в ином виде (такое преподавателем не запрещалось): ((2 3) (1) (1)) - то есть, в каждом элементе списка перечисляю числа вершин, с которыми соединена вершина с порядковым номером данного элемента в списке.

Моё решение этой задачи на Лиспе:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(defun fin (A B L)
 (cond
   ((null L) nil)
   ((EQ A B) nil)
   (T (cond
       ((NOT(member B (nth (- A 1) L))) (let ((S (list A))) (F A B L S)))
       (T T)
      )
   )
 )
)
 
(defun F (X B L S)               ; S - список, куда записываются номера пройденных вершин
 (dolist (i (nth (- X 1) L))
             (cond
               ((member i S) ())   
               ((EQ (length S) (length L)) ())
               ((NOT(member B (nth (- i 1) L))) (F i B L (cons i S)))
               (T (return T))
             )
 )
)

Помогите, пожалуйста, с реализацией этого задания на Хаскеле.

@Catstail · 02.06.2017, 08:10

Здесь подойдет обход в глубину. Вот реализация:

Haskell
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
-- Отметка вершины m как посещенной
 
mark :: [Int] -> Int -> Int -> [Int]
mark chk n m | (n == 0) = m : (tail chk)
             | otherwise = (head chk) : (mark (tail chk) (n-1) m)
 
-- Дать вершину, связанную с k-й и еще непосещенную
             
getV :: [[Int]] -> [Int] -> Int -> Int
getV g chk k | lst == [] = -1
             | otherwise = head lst 
               where   lst=filter (\ x -> (chk !! x)==0) (g !! k);
             
-- Обход в глубину с накопительными параметрами
 
dfs' :: [[Int]] -> [Int] -> [Int] -> Int -> Int -> [Int]
dfs' g pth chk n m | pth == [] = []
                   | (last pth) == m = pth
                   | new == -1 = dfs' g (init pth) chk n m
                   | otherwise = dfs' g (pth ++ [new]) (mark chk new 1) n m
                     where new=getV g chk (last pth)
                              
-- Парадная функция
 
dfs :: [[Int]] -> Int -> Int -> [Int]
dfs g n m = dfs' g [n] (mark (take k (repeat 0)) n 1) n m
            where k=length g

Граф задается списками смежности - списком списков, в i-м элементе которого перечисляются вершины, связанные с i-й

Haskell
1
2
3
4
5
6
Main> dfs [[1,2],[0,2,3],[0,1,3,4],[1,2,4],[2,3]] 0 4
[0,1,2,3,4] -- путь из нулевой в 4-ю
Main> dfs [[1,2],[0,2,3],[0,1,4],[1,2,4],[2,3]] 0 4
[0,1,2,4]  -- путь из нулевой в 4-ю
Main> dfs [[1,2],[0,2],[0,1],[1,2,4],[2,3]] 0 4
[]  -- а в этом графе пути нет

@Curry · 02.06.2017, 08:17

Не по теме:

Сообщение от Catstail

Парадная функция

Термин, однако.

@Catstail · 02.06.2017, 11:17

Не по теме:

KolodeznyDiver, да, немного не того...

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@Catstail
	02.06.2017, 11:17
	Не по теме: KolodeznyDiver, да, немного не того... 0