|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
04.04.2015, 19:38 | #11 |
Пользователь
Регистрация: 15.12.2013
Сообщений: 42
|
Спасибо за решение, но не совсем понял вот это. Это для определения длин? Что вы имеет ввиду под исследованными и неисследованными ячейками?
|
04.04.2015, 23:46 | #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. |
05.04.2015, 02:08 | #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. |
05.04.2015, 08:40 | #14 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Код:
|
05.04.2015, 12:44 | #15 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
Poma][a, поясни пожалуйста.
Почему именно 4, 6 и 8? Получается, что это просто частный случай для графа из поста #5 (просто идея)? Или как? |
05.04.2015, 13:13 | #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. |
05.04.2015, 13:26 | #17 | |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
Цитата:
Кстати, проблема была в том, что одной длиной путь идентифицировать не удавалось. Ибо могут быть пересекающиеся пути одной длины (куча ветвлений одинаковой длины). Последний раз редактировалось Sibedir; 05.04.2015 в 13:52. |
|
05.04.2015, 13:31 | #18 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Ну.. Сложность O(V^3)..
Если забыть про матрицу, то можно бахнуть O(V*E) А реализация.. Почти обычный dfs.. Только те идиотские развилки. |
05.04.2015, 14:06 | #19 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
А ну вот, да. вроде работает
Код:
Нет. показалось. Лишнего насчитывает. Последний раз редактировалось Sibedir; 05.04.2015 в 14:12. |
05.04.2015, 15:13 | #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 |