Форум программистов, компьютерный форум, киберфорум
Haskell
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
0 / 0 / 0
Регистрация: 17.06.2014
Сообщений: 8
1

Граф задан цепными списками. Построить его реберный граф

17.06.2014, 18:41. Просмотров 1719. Ответов 14
Метки нет (Все метки)

Дорогие форумчане, прошу помочь с написанием данной программы:
Граф задан с помощью цепных списков. Построить его реберный граф.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.06.2014, 18:41
Ответы с готовыми решениями:

Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл
помогите очень срочно надо. считать граф из файла (граф задан матрицей) представить его в виде...

Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством пересечений
Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством...

Из неориентированого графа создать реберный граф
Из неориентированого графа создать реберный граф. Помогите !

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

14
162 / 162 / 22
Регистрация: 23.02.2011
Сообщений: 347
17.06.2014, 20:28 2
Цитата Сообщение от Printemps Посмотреть сообщение
Граф задан с помощью цепных списков
Это как?
0
Модератор
Эксперт Python
26759 / 13980 / 2669
Регистрация: 12.02.2012
Сообщений: 22,917
Записей в блоге: 2
17.06.2014, 21:50 3
Вот и мне это тоже интересно.
0
0 / 0 / 0
Регистрация: 17.06.2014
Сообщений: 8
17.06.2014, 23:31  [ТС] 4
Т.е. имеется ввиду связный список.
0
Модератор
Эксперт Python
26759 / 13980 / 2669
Регистрация: 12.02.2012
Сообщений: 22,917
Записей в блоге: 2
18.06.2014, 10:07 5
Вижу, что не доходит... Ладно. На картинке граф. Задай его "цепными списками"
0
Миниатюры
Граф задан цепными списками. Построить его реберный граф  
0 / 0 / 0
Регистрация: 17.06.2014
Сообщений: 8
18.06.2014, 12:49  [ТС] 6
В методичке преподавателя есть такой момент, но только с деревом: Картинки
Цепными списками: ((2 7 2)(7 6 5)(6 11)(2 5 9 4))

Следовательно, по вашему примеру, граф заданный цепными списками будет выглядеть так:
((1 2 5)(2 7 5)(7 3)( 1 3 5 8)(3 9 5)(9 8))
или подобным образом
0
649 / 259 / 16
Регистрация: 02.03.2014
Сообщений: 587
18.06.2014, 13:27 7
Тогда нужно нечто подобное. (по списку списков строит список рёбер)
Haskell
1
2
3
4
5
{-#Language LambdaCase#-}
 
transform :: [[Int]]->[(Int,Int)]
transform = let f = \case x:y:sx -> (x,y):f (y:sx); _ -> []
            in  foldl (\x y -> x ++ f y) []
0
Модератор
Эксперт Python
26759 / 13980 / 2669
Регистрация: 12.02.2012
Сообщений: 22,917
Записей в блоге: 2
18.06.2014, 15:24 8
Цитата Сообщение от Printemps Посмотреть сообщение
граф заданный цепными списками будет выглядеть так:
((1 2 5)(2 7 5)(7 3)( 1 3 5 8)(3 9 5)(9 8))
или подобным образом
- алгоритм составления списка не понятен. Давай так: список будет состоять из n подсписков, i-й список включает все вершины, смежные с i-й. Тогда граф будет представляться так:

Haskell
1
[[2,3],[1,5,7],[1,6,7,9],[3,9,8],[3,6,8]]
и задача станет осмысленной.
1
Модератор
Эксперт Python
26759 / 13980 / 2669
Регистрация: 12.02.2012
Сообщений: 22,917
Записей в блоге: 2
18.06.2014, 16:30 9
Haskell
1
2
3
4
5
6
7
8
vList :: [[Int]] -> [[Int]]
vList vl = setOf $ concatMap (\ n -> genV n (vl !! n)) [0,1..(length vl)-1]
           where genV p x = map (\ y -> [(min (p+1) y),(max (p+1) y)]) x
                 setOf    = foldl (\ acc z -> if z `elem` acc then acc else acc ++ [z]) []
 
Main> vList [[2,3,4],[1,4],[1,4],[1,2,3,5],[4,6,7],[5],[5]]
 
[[1,2],[1,3],[1,4],[2,4],[3,4],[4,5],[5,6],[5,7]]
1
Изображения
 
649 / 259 / 16
Регистрация: 02.03.2014
Сообщений: 587
19.06.2014, 01:53 10
Дамс... Catstail, вашим способом заданные графы обрабатывать сложнее...
Haskell
1
2
transform' s = concat [[(x,b) | x <- a] | (a,b) <- zip l [1..]] where
    l = [filter (<b) a | (a,b) <- zip s [1..]]
1
Модератор
Эксперт Python
26759 / 13980 / 2669
Регистрация: 12.02.2012
Сообщений: 22,917
Записей в блоге: 2
19.06.2014, 12:25 11
А еще проще - так:

Haskell
1
2
3
vList :: [[Int]] -> Int -> [[Int]]
vList [] _ = []
vList (x:xs) n = (map (\ y -> [n,y]) x) ++ (vList (map (\ z -> filter (/= n) z) xs) (n+1))
0
649 / 259 / 16
Регистрация: 02.03.2014
Сообщений: 587
19.06.2014, 14:18 12
Позволю себе довести ваше решение парой штрихов.
Haskell
1
2
3
vList :: [[Int]] -> Int -> [[Int]]
vList []     _ = []
vList (x:xs) n = [[n,a] | a <- x] ++ vList [filter (/= n) a | a <- xs] (n+1)
Добавлено через 11 минут
Всё я давёл, до логического конца своё решение. Теперь что-то улучшить здесь врядли получится.
Haskell
1
2
transform' ::[[Int]] -> [(Int, Int)]
transform' s = concat [[(x,b) | x <- a, x < b] | (a,b) <- zip s [1..]]
1
Модератор
Эксперт Python
26759 / 13980 / 2669
Регистрация: 12.02.2012
Сообщений: 22,917
Записей в блоге: 2
19.06.2014, 15:37 13
Цитата Сообщение от Araneo Посмотреть сообщение
Теперь что-то улучшить здесь врядли получится.
- улучшить (или найти недостаток) всегда можно... Ну, почти всегда. Задай граф с петлей (это когда вершина соединена сама с собой).
0
649 / 259 / 16
Регистрация: 02.03.2014
Сообщений: 587
19.06.2014, 17:01 14
Поправил...
Haskell
1
2
transform :: [[Int]] -> [(Int, Int)]
transform s = concat [[(x,b) | x <- a, x <= b] | (a,b) <- zip s [1..]]
0
Модератор
Эксперт Python
26759 / 13980 / 2669
Регистрация: 12.02.2012
Сообщений: 22,917
Записей в блоге: 2
19.06.2014, 18:25 15
Сходный вариант:

Haskell
1
2
task :: [[Int]] -> [[Int]]
task x = concatMap (\ n -> [[y,n] | y <- x !! (n-1), y<=n]) [1..length x]
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.06.2014, 18:25

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

Построить ориентированный граф, содержащий 5 вершин и 5 ребер и выяснить его свойства
Построить ориентированный граф, содержащий 5 вершин и 5 ребер и выяснить его свойства.

Построить граф отношения «быть сыном» на множестве людей и выяснить его свойства
Помогите построить, ничего не выходит


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.