ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм определения циклических ссылок
25 сообщений из 50, страница 1 из 2
  1  все
Алгоритм определения циклических ссылок
    #35313377
Farus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Farus
Гость
Кто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.
...
Рейтинг: 0 / 0
15.05.2008, 07:22
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35313441
Станислав С...кий
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Станислав С...кий
Гость
FarusКто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.
Ну, скажем, такой алгоритм (типа поиска "в глубину"). Только он очень долгий :)
1. создаем массив вершин графа
2. создаем массив пройденных вершин графа
3. берем первую вершину
4. берем произвольное ребро графа, выходящее из этой вершины.
5. Если вторая вершина ребра графа содержится в массиве пройденных вершин, то мы нашли цикл.
6. В противном случае заносим вершину в пройденные, делаем ее текущей и идем на п.4
7. Если данная вершина является листом (т.е. из нее больше не выходит ребер), то возвращаемся на один уровень вверх (к предыдущей пройденной вершине) и возвращаемся к п.4
8. Если вершин больше не осталось, то мы обошли весь граф.
...
Рейтинг: 0 / 0
15.05.2008, 08:47
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35313486
Farus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Farus
Гость
Станислав С...кий FarusКто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.
Ну, скажем, такой алгоритм (типа поиска "в глубину"). Только он очень долгий :)
...
5. Если вторая вершина ребра графа содержится в массиве пройденных вершин, то мы нашли цикл.
...

Ну хорошо, эт вроде все будет работать.
А ежели мы накладываем дом условие - граф ориентированный. И тогда понятие цикла несколько меняется.
...
Рейтинг: 0 / 0
15.05.2008, 09:16
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35313670
Самоловских Виталий aka Kefir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Самоловских Виталий aka Kefir
Участник
Farus
Ну хорошо, эт вроде все будет работать.
А ежели мы накладываем дом условие - граф ориентированный. И тогда понятие цикла несколько меняется.
А в неориентированном графе две вершины и ребро уже цикл. Алгоритм как раз на ориентированных работает.
...
Рейтинг: 0 / 0
15.05.2008, 10:15
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35313676
Самоловских Виталий aka Kefir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Самоловских Виталий aka Kefir
Участник
Хотя нет. В этом случае нужно начинать с каждой вершины и чистить список пройденных. Наверное есть лучший алгоритм, надо книжки читать.
...
Рейтинг: 0 / 0
15.05.2008, 10:17
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35313930
Гость_0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость_0
Гость
FarusКто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.хотите написать свою реализацию Spanning Tree алгоритма ? :)
...
Рейтинг: 0 / 0
15.05.2008, 11:36
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35314019
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
FarusКто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.
Хочу тебя огорчить. Практически 100% алгорутмов теории графов уже были предложены в прошлом веке. Тебе остаётся только почитать теорию и выбрать алгоритм, который наиболее близко подходит к решению твоей задачи.
...
Рейтинг: 0 / 0
15.05.2008, 12:04
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35314033
Alexsalog
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexsalog
Участник
mayton FarusКто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.
Хочу тебя огорчить. Практически 100% алгорутмов теории графов уже были предложены в прошлом веке. Тебе остаётся только почитать теорию и выбрать алгоритм, который наиболее близко подходит к решению твоей задачи.

Ну я искал по гуглу. Готового не нашел. Хотя алгорим то вообщем то должен быть фундаментальным. :-)
...
Рейтинг: 0 / 0
15.05.2008, 12:08
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35314107
Alexsalog
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexsalog
Участник
Гость_0 FarusКто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.хотите написать свою реализацию Spanning Tree алгоритма ? :)

Это вроде коммуникации. Нее... мне для прикладной программки.
Хотя можно сделать и перебором тупым.... Только боюсь количество переборов будет возрастать в геометрической прогрессии.
...
Рейтинг: 0 / 0
15.05.2008, 12:28
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35314476
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
FarusКто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.
Зависит от того, что именно Вам нужно. Найти все циклы во всех вариантах? Найти фундаментальные циклы? Определить факт наличия циклов без поиска самих циклов? Еще что-нибудь?

И таки да, гугль содержит более чем достаточно информации на эту тему.
...
Рейтинг: 0 / 0
15.05.2008, 13:55
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35315012
Фотография Lelikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lelikk
Участник
Alexsalog mayton FarusКто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.
Хочу тебя огорчить. Практически 100% алгорутмов теории графов уже были предложены в прошлом веке. Тебе остаётся только почитать теорию и выбрать алгоритм, который наиболее близко подходит к решению твоей задачи.

Ну я искал по гуглу. Готового не нашел. Хотя алгорим то вообщем то должен быть фундаментальным. :-)

Постройте по вашему графу остов. Все ребра, не вошедшие в остов - уже элементы циклов.
...
Рейтинг: 0 / 0
15.05.2008, 16:38
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35315279
ретти
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ретти
Гость
очень интересно, но неоднозначно
...
Рейтинг: 0 / 0
15.05.2008, 17:50
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35316451
Alexsalog
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexsalog
Участник
softwarer FarusКто поможет: предложите алгорим определения цикличиеских ссылок на графе произвольного размера.
Зависит от того, что именно Вам нужно. Найти все циклы во всех вариантах? Найти фундаментальные циклы? Определить факт наличия циклов без поиска самих циклов? Еще что-нибудь?

И таки да, гугль содержит более чем достаточно информации на эту тему.

Найти любые циклы, притом если граф строится итеративно - то сообщить об этом цикле и показать его в момент добавления решающего ребра.
...
Рейтинг: 0 / 0
16.05.2008, 11:33
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35316483
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Тогда есть совершенно очевидный алгоритм. Поддерживать список возможных путей между вершинами графа. То есть начать с одной вершины; далее добавили вершину - ничего не делаем, добавили ребро - достраиваем список путей, используя начинающиеся и заканчивающиеся в вершинах этого ребра. Каждый раз, когда при добавлении ребра АБ уже имеем путь БА или - внимание - несколько таких путей, вот вам, бабушка, и циклы.
...
Рейтинг: 0 / 0
16.05.2008, 11:40
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35316523
Alexsalog
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexsalog
Участник
softwarerТогда есть совершенно очевидный алгоритм. Поддерживать список возможных путей между вершинами графа. То есть начать с одной вершины; далее добавили вершину - ничего не делаем, добавили ребро - достраиваем список путей, используя начинающиеся и заканчивающиеся в вершинах этого ребра. Каждый раз, когда при добавлении ребра АБ уже имеем путь БА или - внимание - несколько таких путей, вот вам, бабушка, и циклы.

Получится дикое количество комбинаций......
...
Рейтинг: 0 / 0
16.05.2008, 11:49
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35316559
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
AlexsalogПолучится дикое количество комбинаций......
Это если ребра добавляются интерактивно-то? Не очень верится, раньше оператор устанет :)

А так - задача поиска всех циклов, если не ошибаюсь, np-полна, следовательно либо дикое количество комбинаций в памяти, либо перебор того же дикого количества комбинаций на ходу. Можно применять методы сокращения, скажем, железнодорожники строят граф только по узловым станциям (грубо говоря, по развилкам), сжимая вершины один вход - один выход.
...
Рейтинг: 0 / 0
16.05.2008, 11:56
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35316691
Alexsalog
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexsalog
Участник
softwarer AlexsalogПолучится дикое количество комбинаций......
Это если ребра добавляются интерактивно-то? Не очень верится, раньше оператор устанет :)

А так - задача поиска всех циклов, если не ошибаюсь, np-полна, следовательно либо дикое количество комбинаций в памяти, либо перебор того же дикого количества комбинаций на ходу. Можно применять методы сокращения, скажем, железнодорожники строят граф только по узловым станциям (грубо говоря, по развилкам), сжимая вершины один вход - один выход.

Насчет развилок - мысль. Про np полноту - тоже.

Ок, спасибо.

Хотя наверное как всегда есть вариант комбинированный - чать отдается на "память" а часть на перебор...
...
Рейтинг: 0 / 0
16.05.2008, 12:27
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35318373
ретти
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ретти
Гость
softwarerКаждый раз, когда при добавлении ребра АБ уже имеем путь БА или - внимание - несколько таких путей, вот вам, бабушка, и циклы.
При всем моем, откуда такая зашоренность отклика на вторую сторону?
Переформулировать вопрос и считать его решенным.

Ваще децсад. "уже имеем путь БА". И как мы узнаем что мы его, этот путь, "уже имеем"(или, уже "поимели")?
...
Рейтинг: 0 / 0
16.05.2008, 22:16
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35318378
ретти
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ретти
Гость
Alexsalog softwarer AlexsalogПолучится дикое количество комбинаций......
Это если ребра добавляются интерактивно-то? Не очень верится, раньше оператор устанет :)

А так - задача поиска всех циклов, если не ошибаюсь, np-полна, следовательно либо дикое количество комбинаций в памяти, либо перебор того же дикого количества комбинаций на ходу. Можно применять методы сокращения, скажем, железнодорожники строят граф только по узловым станциям (грубо говоря, по развилкам), сжимая вершины один вход - один выход.

Насчет развилок - мысль. Про np полноту - тоже.

Ок, спасибо.

Хотя наверное как всегда есть вариант комбинированный - чать отдается на "память" а часть на перебор...
Этот тоже. Как Добчинский раскланялся. Типа спасибо. Насчет развилок -- это мысль?
Про эту банальщину тут никто и не вспоминал. Она тебе поможет как мертвому припарки.
...
Рейтинг: 0 / 0
16.05.2008, 22:19
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35318399
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
реттиВаще децсад. "уже имеем путь БА". И как мы узнаем что мы его, этот путь, "уже имеем"(или, уже "поимели")?
Ваш вопрос показывает, что Вы либо не читали то, на что отвечаете, либо временно/постоянно не в состоянии воспринимать прочитанное. До тех пор, пока означенные факторы не изменятся, беседа вряд ли будет осмысленной.
...
Рейтинг: 0 / 0
16.05.2008, 22:48
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35318413
asvdfdsv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asvdfdsv
Гость
если речь только об интерактивной проверке, то проще и быстрее банально пускать волну из обеих вершин, которые соединяет новосозданное ребро
...
Рейтинг: 0 / 0
16.05.2008, 23:08
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35318415
asvdfdsv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asvdfdsv
Гость
asvdfdsvесли речь только об интерактивной проверке, то проще и быстрее банально пускать волну из обеих вершин, которые соединяет новосозданное ребро
из одной из этих вершин, разумеется, будет достаточно
...
Рейтинг: 0 / 0
16.05.2008, 23:09
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35318421
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
asvdfdsvесли речь только об интерактивной проверке, то проще и быстрее банально пускать волну
Если речь идет о том, чтобы найти какой-нибудь цикл, то да. Но автору нужны все - и тут не соглашусь, и не быстрее, и не проще.
...
Рейтинг: 0 / 0
16.05.2008, 23:13
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35318425
asvdfdsv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asvdfdsv
Гость
softwarer asvdfdsvесли речь только об интерактивной проверке, то проще и быстрее банально пускать волну
Если речь идет о том, чтобы найти какой-нибудь цикл, то да. Но автору нужны все - и тут не соглашусь, и не быстрее, и не проще.
ну если все, тогда лучше конечно действительно строить маршруты
но опять же - на лету, имхо
т.е. если есть условие интерактивной проверки, то я бы по-любому это использовал, сужая задачу до поиска циклов, проходящих через заданную вершину (например их которой исходит новое ребро), а не ваааааще всех на графе
...
Рейтинг: 0 / 0
16.05.2008, 23:17
| Ответить | Цитировать | Написать  
Алгоритм определения циклических ссылок
    #35318451
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
asvdfdsvну если все, тогда лучше конечно действительно строить маршруты
но опять же - на лету, имхо
Интуитивное "имхо" желательно бы подкреплять. Одного гигабайта оперативки - столько есть на любой современной рабочей станции - хватит, чтобы хранить матрицу связности графа примерно на 90'000 вершин. Также память нужна будет под уже найденные циклы итп - но порядок величин понятен.

Сколько времени будет обсчитываться волна "из точки во все" на таком графе - довольно интересный вопрос. Заснуть, конечно, не успеешь, но вот получить ответ за комфортное для интерактивного режима время - далеко не факт.
...
Рейтинг: 0 / 0
16.05.2008, 23:52
| Ответить | Цитировать | Написать  
25 сообщений из 50, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм определения циклических ссылок
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=35313930&tid=1345282]:
 0ms
get settings:
 8ms
get forum list:
 11ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 30ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 52ms
get tp. blocked users:
 1ms
others: 237ms
total:  355ms
созд. / загр.: 355ms
x
x
Закрыть


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