![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
|
Опции темы | Поиск в этой теме |
![]() |
#11 |
Пользователь
Регистрация: 15.12.2013
Сообщений: 42
|
![]()
Спасибо за решение, но не совсем понял вот это. Это для определения длин? Что вы имеет ввиду под исследованными и неисследованными ячейками?
|
![]() |
![]() |
![]() |
#12 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
![]()
Не. М-м-м. Как бы объяснить мысль?
Допустим G - это исходный граф v - некая его вершина Имеется некоторая операция вырезки вершины: G' = (G - v) , где G' - это такой же граф, но уже без вершины v и всех прилегающих к ней рёбер Имеется функция Count(G) - количество искомых циклов в графе G Имеется функция Circle(G,v) - количество циклов, в которые входит вершина v (если мы вышли из вершины v по одному из рёбер, то функция показывает сколькими путями можно вернуться обратонго в вершину v по другому ребру) Ключевая мысль такая: Count(G) = Circle(G,v) + Count(G') , где G' = (G - v) А пометить вершину, как исследованную - имелось в виду, что можно считать её как отсутствующую, ну или просто удалить её из графа. Вот собственно беда именно с Circle(G,v). Пытаюсь стягивать граф. Но путают взаимопересечения циклов (наложения и восьмерки). // ---------------------------------------- Вообще перед работой с графом можно его как следует потрясти ![]() Код:
Последний раз редактировалось Sibedir; 05.04.2015 в 02:14. |
![]() |
![]() |
![]() |
#13 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
![]()
Довольно жирно (полный перебор), но лучше навряд ли сделаю.
Код:
И хотя "1-2-1" мы за цикл здесь не считаем, "туда-сюда" ("1-2-3-1" и "1-3-2-1") пусть будут разные циклы. Ибо тогда, если убрать вызов Shave, то алгоритм будет работать и для ориентированного графа. P.S.: kappa937, если узнаешь правильное, ну или более изящное решение, выложи здесь. Последний раз редактировалось Sibedir; 05.04.2015 в 02:12. |
![]() |
![]() |
![]() |
#14 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]() Код:
|
![]() |
![]() |
![]() |
#15 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
![]()
Poma][a, поясни пожалуйста.
Почему именно 4, 6 и 8? Получается, что это просто частный случай для графа из поста #5 (просто идея)? Или как? |
![]() |
![]() |
![]() |
#16 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Потому что мы ищем циклы с весом 4, 6, 8.
А идея.. Все портит неориентированность.. У меня был вариант с dfs'ом с одним глобальным массивом (кстати мой use можно тоже сделать глобальным).. Но тот массив просто отмечал один раз и больше не трогался, но там был wave. Тогда я решил переписать это чудо в bfs. Но везде был косяк.. Есть вершина входит в два и более циклов, то некоторые из них не будут учитываться.. Именно поэтому нам и нужен use. (Поясню : Пусть есть граф из 6 вершин. В нем 7 ребер : Код:
Вот.. Именно поэтому пришлось крутить dfs для всех вершин.. Еще могут быть не очень понятны строки : Код:
Фух.. Вроде нигде не врал.. P.S. Я уверен, что есть классный вариант, который позволяет "Найти количество циклов веса M в неориентированном графе" за какую-то хорошую сложность.. Последний раз редактировалось Poma][a; 05.04.2015 в 13:16. |
![]() |
![]() |
![]() |
#17 | |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
![]() Цитата:
Кстати, проблема была в том, что одной длиной путь идентифицировать не удавалось. Ибо могут быть пересекающиеся пути одной длины (куча ветвлений одинаковой длины). Последний раз редактировалось Sibedir; 05.04.2015 в 13:52. |
|
![]() |
![]() |
![]() |
#18 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]()
Ну.. Сложность O(V^3)..
Если забыть про матрицу, то можно бахнуть O(V*E) А реализация.. Почти обычный dfs.. Только те идиотские развилки. |
![]() |
![]() |
![]() |
#19 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
![]()
А ну вот, да. вроде работает
Код:
Нет. показалось. Лишнего насчитывает. Последний раз редактировалось Sibedir; 05.04.2015 в 14:12. |
![]() |
![]() |
![]() |
#20 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
![]() Код:
|
![]() |
![]() |
![]() |
|
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как найти максимальный подграф или клику в неориентированном графе?(PASCAL)) | Artur1992 | Помощь студентам | 0 | 17.02.2011 16:31 |
Поиск в глубину и ширину в неориентированном графе | ya chef | Помощь студентам | 0 | 20.11.2010 18:25 |
В графе найти все его четырехвершинные полные подграфы[PROLOG] | Bruster | Помощь студентам | 1 | 24.12.2009 09:55 |