ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Scheme Проверить граф на связность
25 сообщений из 39, страница 1 из 2
  1  все
Scheme Проверить граф на связность
    #35311323
lavash
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
lavash
Гость
Помогите, пожалуйста, нужно решить задачу: проверить граф на связность, граф задаётся списком пар: ((1 2) (2 3) (4 4)). (4 4)-это изолированная вершина. Что делать не знаю..
...
Рейтинг: 0 / 0
14.05.2008, 12:19
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35315271
ретти
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ретти
Гость
Простой волновой алгоритм.
Сначала список пар запишем в виде:
Код: plaintext
1.
2.
3.
4.
 1  ->  4 ,  8 ,  11 , ...
 2  ->  3 ,  4 ,  22 ,  567 , ...
...
...
Т.е. из вершины № 1 можно попасть в вершины №№ 4, 8, 11, ...

Стартуем. Берем два пустых сета (sets) А() и Б(). Добавляем в А() напр. вершину № 1: А(1)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
While True:
{
{
для каждой вершины из А добавляем в Б ее соседей, но только тех, которые еще никогда не проходились.
А этот факт можно помечать в булевском массиве С[ 1 ..N], где  1 ..N - номера всех вершин.
}
После прохода по всем вершинам из А, если Б пуст, то выходим из While, иначе продолжаем:

А := Б
Б := () -- опорожняем Б для следующей итерации

} // end of While


Теперь проходим по булевскому массиву и смотрим: есть ли там вершины никогда
не фигурировшие в нашем While цикле. Если есть хоть одна такая, то граф не связен.
End of Script
...
Рейтинг: 0 / 0
15.05.2008, 17:48
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35318651
sotny
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sotny
Гость
В Sheme нет циклов...
...
Рейтинг: 0 / 0
17.05.2008, 12:42
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35318656
lavash
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
lavash
Гость
А что делать?
...
Рейтинг: 0 / 0
17.05.2008, 12:44
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35318674
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
sotny пишет:
> В Sheme нет циклов...

Чего ? еще скажи, что GOTO там нет ...
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
17.05.2008, 13:05
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35318677
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
MasterZiv пишет:
> > В Sheme нет циклов...
>
> Чего ? еще скажи, что GOTO там нет ...

А даже если и нету, то есть рекурсия, которая циклы заменяет.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
17.05.2008, 13:09
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35318702
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
MasterZiv пишет:
> > > В Sheme нет циклов...

Если это единственная проблема, возможно,
этот материал поможет.
http://schemecookbook.org/Cookbook/IdiomLoopingConstructs
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
17.05.2008, 13:48
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35318833
Бананза
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бананза
Гость
ВМКшник чтоли?)))
...
Рейтинг: 0 / 0
17.05.2008, 18:16
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35319827
Фотография Gluk (Kazan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gluk (Kazan)
Участник
sotnyВ Sheme нет циклов...

Есть :)
...
Рейтинг: 0 / 0
19.05.2008, 08:43
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35321307
Фотография ПикеЯ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПикеЯ
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
g=[( 1 , 2 ),( 2 , 3 ),( 3 , 4 ),( 5 , 6 ),( 8 , 9 ),( 4 , 5 ),( 4 , 8 ),( 4 , 7 ),( 10 , 11 ),( 4 , 10 )]

def r(l,visited,p):
    visited.append(p)
    map(lambda x:((x[ 0 ]==p[ 1 ] and not(x in visited)) and (r(l,visited,x))), l)
    return len(visited)==len(g)

print(r(g,[],g[ 0 ]))
это не на сХеме а на какбыпитоне.
как оно работает я, есличестно, до конца не понял )))
изначально написал циклом и ИФом вместо МАП.
потом все поубирал.

работает, наверное, из-за того, что визитед получается глобальным?

ага. и тут еще (2,3)<>(3,2) . тоесть направление играет роль.
забыл как это поумному звучит.

анука скажитека - я правильно сделал? ))))
...
Рейтинг: 0 / 0
19.05.2008, 16:35
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35321324
Фотография ПикеЯ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПикеЯ
Участник
ой...
Код: plaintext
1.
2.
.....
return len(visited)==len(l)
...
Рейтинг: 0 / 0
19.05.2008, 16:39
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35321705
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
ПикеЯой...
Код: plaintext
1.
2.
.....
return len(visited)==len(l)

действительно, вот так, сходу и не поймешь как оно работает
...
Рейтинг: 0 / 0
19.05.2008, 18:45
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35322339
Фотография ПикеЯ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПикеЯ
Участник
retty ПикеЯой...
Код: plaintext
1.
2.
.....
return len(visited)==len(l)

действительно, вот так, сходу и не поймешь как оно работает
ога, еще и "осмысленные" имена переменных )
идея какая - обходить граф и считать "посещенные" ребра, записывая их в список.
(я чево-то подумал, что в связном графе количество посещенных ребер должно быть равно вообще количеству ребер.)
...
Рейтинг: 0 / 0
20.05.2008, 10:00
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35322375
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
я тоже не большой знаток графов,
но мне кажется, что понятие связности относится (имеет смысл) только к НЕориентированным графам.
Или близко к этому.
...
Рейтинг: 0 / 0
20.05.2008, 10:16
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35322398
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
ПикеЯ retty ПикеЯой...
Код: plaintext
1.
2.
.....
return len(visited)==len(l)

действительно, вот так, сходу и не поймешь как оно работает
ога, еще и "осмысленные" имена переменных )
идея какая - обходить граф и считать "посещенные" ребра, записывая их в список.
(я чево-то подумал, что в связном графе количество посещенных ребер должно быть равно вообще количеству ребер.)
и почему ребер? вершин; "посетить ребро" звучит как-то двусмысленно.
Есть в этом какой-то оттенок непристойности ("обождь; я отскочу за угол; по нужде")
Хорошо что не по большой (я очень надеюсь). И это жизнь. А в жизни всякое случается.
Увы, как нам не хочется обратного. Я б тоже типа хотел курить щас сигару, в гамаке, и поучать
всех теории графов. Увы, ....
...
Рейтинг: 0 / 0
20.05.2008, 10:21
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35322531
Фотография ПикеЯ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПикеЯ
Участник
retty
и почему ребер? вершин; "посетить ребро" звучит как-то двусмысленно.
Есть в этом какой-то оттенок непристойности ("обождь; я отскочу за угол; по нужде")
Хорошо что не по большой (я очень надеюсь). И это жизнь. А в жизни всякое случается.
Увы, как нам не хочется обратного. Я б тоже типа хотел курить щас сигару, в гамаке, и поучать
всех теории графов. Увы, ....
во - ориентированный граф. точно ) пол-года дискретки тринадцать лет назад таки сгладились в моей голове полностью.

посетить вершину, но, согласись, "пройтись по ребру" тоже как-то по садистски звучит )))))
...
Рейтинг: 0 / 0
20.05.2008, 10:58
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35322580
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
все-таки "пройтись по ребру" звучит намного мягше и тщительнее;

а вот "посетить ребро" -- уже подозрения возникают.
...
Рейтинг: 0 / 0
20.05.2008, 11:10
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35322694
Фотография ПикеЯ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПикеЯ
Участник
rettyвсе-таки "пройтись по ребру" звучит намного мягше и тщительнее;
а вот "посетить ребро" -- уже подозрения возникают.

лаадн, согласен на фразу "посмотреть на ребро". ;)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
g=[( 1 , 2 ),( 2 , 3 ),( 4 , 3 ),( 5 , 3 ),( 5 , 6 ),( 1 , 8 ),( 2 , 8 ),( 10 , 9 ),( 10 , 11 ),( 11 , 8 )]
visited=[]

def r(p):
    global visited
    global g
    visited.append(p)
    map(lambda x:((((x[ 0 ] in p) or (x[ 1 ] in p)) and not(x in visited)) and (r(x))), g)
    return len(visited)

print r(g[ 0 ])==len(g)

вот тут вот ориентированность уже не требуется.
но как-то некрасиво однако ((
...
Рейтинг: 0 / 0
20.05.2008, 11:42
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35322907
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Еще лучше:
"пройти ВДОЛЬ ребра". Т.е., не по самому ребру, а возле него (т.е., "вдоль" (и быстро)).
2.
Красоты нам не нужны. Нужна точность.
...
Рейтинг: 0 / 0
20.05.2008, 12:25
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35322986
Фотография ПикеЯ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПикеЯ
Участник
rettyЕще лучше:
"пройти ВДОЛЬ ребра". Т.е., не по самому ребру, а возле него (т.е., "вдоль" (и быстро)).
2.
Красоты нам не нужны. Нужна точность.

во. "вдоль" - звучит красиво.
а вот за точность... как ее обеспечить-то, если алгоритм "понимается" где-то на уровне подсознания а отлаживается методом "а если вот так попробывать?"...

тестирование, вроде, показывает правильность работы.

некрасиво мне в том, что никак не придумаю "однострочную" r() .
из-за необходимости сделать visited.append() один раз при каждом "падении" в процедуру.
хотя...
Код: plaintext
1.
2.
3.
4.
5.
6.
g=[( 1 , 2 ),( 2 , 3 ),( 4 , 3 ),( 5 , 3 ),( 5 , 6 ),( 1 , 8 ),( 2 , 8 ),( 10 , 9 ),( 10 , 11 ),( 1 , 11 )]

def r(gg,visited,p):
    visited.append(p) or (map(lambda x:((((x[ 0 ] in p) or (x[ 1 ] in p)) and not(x in visited)) and (r(gg,visited,x))), gg))
    return visited

print len(r(g,[],g[ 0 ]))==len(g)

теперь про лямбду почитать надо...))
...
Рейтинг: 0 / 0
20.05.2008, 12:47
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35323047
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
ай, да нафик тебе эта лямбда, если алгоритм понимается на полу-уровне

ну представь себе какие-нибудь бикфордовы шнуры, к вершинам

ты поджег ; побежали змеи..... :) какие-то вершины не загорелись
...
Рейтинг: 0 / 0
20.05.2008, 13:00
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35323082
Фотография ПикеЯ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПикеЯ
Участник
rettyай, да нафик тебе эта лямбда, если алгоритм понимается на полу-уровне

ну представь себе какие-нибудь бикфордовы шнуры, к вершинам

ты поджег ; побежали змеи..... :) какие-то вершины не загорелись

) да нее, это то понятно. кстати бикфордовы шнуры не катят - от вершины, в случае разветвления, огоньки одновременно поползуть по разным маршрутам. это не рекурсия)))
в рекурсии он должен догореть до конца по одной ветке, потом быстренько-быстренько вернуцца к развилке и начать гореть по другой.

лямда мне не нужна - намного понятней без нее, и скобок поменьше.
интерестно доделать так, чтобы переменных небыло. явных.
убрать, чем-то заменить, список посещенных ребер.
ой.
"список ребер, вдоль которых я уже ходил"
...
Рейтинг: 0 / 0
20.05.2008, 13:09
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35323343
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
Рекурсия (или цикл) в том, что мы начинаем с одной единственной вершины;
потом идем к ее детям; от детей -- к внукам (изначальной вершины) и т.д. пока
не достигнем "насыщения", или Конца Всего (как и предрекали сионские мудрецы).
...
Рейтинг: 0 / 0
20.05.2008, 14:26
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35323454
Фотография ПикеЯ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПикеЯ
Участник
rettyРекурсия (или цикл) в том, что мы начинаем с одной единственной вершины;
потом идем к ее детям; от детей -- к внукам (изначальной вершины) и т.д. пока
не достигнем "насыщения", или Конца Всего (как и предрекали сионские мудрецы).
вопщем конечно так то оно так, но:
в моем понимании рекурсия таки работает последовательно с откатами.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
"достигнут КОНЕц_ВСЕГО_1 !"
  возврат-возврат-возврат
" достигнут КОНЕЦ_ВСЕГО_2 !"
возврат-возырат
" достигнут КОНЕЦ_ВСЕГО_3 !"
возврат-возврат-возврат-возврат
"недостигнутых концов не осталось!"
возврат
КОНЕЦ_СВЕТА
...
Рейтинг: 0 / 0
20.05.2008, 14:59
| Ответить | Цитировать | Написать  
Scheme Проверить граф на связность
    #35323589
retty
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty
Участник
ПикеЯ rettyРекурсия (или цикл) в том, что мы начинаем с одной единственной вершины;
потом идем к ее детям; от детей -- к внукам (изначальной вершины) и т.д. пока
не достигнем "насыщения", или Конца Всего (как и предрекали сионские мудрецы).
вопщем конечно так то оно так, но:
в моем понимании рекурсия таки работает последовательно с откатами.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
"достигнут КОНЕц_ВСЕГО_1 !"
  возврат-возврат-возврат
" достигнут КОНЕЦ_ВСЕГО_2 !"
возврат-возырат
" достигнут КОНЕЦ_ВСЕГО_3 !"
возврат-возврат-возврат-возврат
"недостигнутых концов не осталось!"
возврат
КОНЕЦ_СВЕТА

с какими откатами? :)
пля, ну рекурсия -- это эвфемизм такой, для цикла.
Не нужна она совершенно тут. Сегодня 20-е. Конец Open Contest 2008 http://www.spoj.pl/ZFUN08/
Уважаю этих пацанов. И задачи были шикарные. Подскажи идею для чомпа:
http://www.spoj.pl/ZFUN08/problems/CLK/
...
Рейтинг: 0 / 0
20.05.2008, 15:32
| Ответить | Цитировать | Написать  
25 сообщений из 39, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Scheme Проверить граф на связность
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=35321705&tid=1345271]:
 0ms
get settings:
 8ms
get forum list:
 17ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 44ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 59ms
get tp. blocked users:
 1ms
others: 240ms
total:  385ms
созд. / загр.: 385ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]