|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
31.03.2015, 15:01 | #1 |
Пользователь
Регистрация: 15.12.2013
Сообщений: 42
|
Найти все циклы в неориентированном графе по матрице смежности
Здравствуйте.
Задача найти кол-во циклов в неориентированном графе с указанием их длин. Есть ли у кого-то примеры решенной задачи либо несложный алгоритм? Заранее спасибо. |
31.03.2015, 15:10 | #2 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
Качаем пример с интернета. А уж если чего не получилось - тогда сюда.
|
31.03.2015, 15:45 | #3 |
Пользователь
Регистрация: 15.12.2013
Сообщений: 42
|
Sibedir, примеров для неориентированных я не нашел
Вот моя попытка: Код:
new_graph[current_vertex, j] = -1; new_graph[j, current_vertex] = -1; отмечаю что это ребро было пройдено в start находится вершина, из которой мы на этом этапе ведем поиск и если она равна вершине, в которую хотим прийти (j) то увеличиваем счетчик. в мейн-функции в цикле вызываю solution() для каждой вершины, и делаю new_graph снова равным матрице смежности (убираю отметки о пройденных вершинах) Проблема в том, что у меня, к примеру, 1-2-4-3-1, 1-3-4-2-1 это разные пути, но при этом условие (j == start) выполняется. Соответственно если, к примеру, ребра такие: 1 2 1 3 2 4 4 3 То кол-во циклов будет 4 (равно кол-ву вершин), а должно быть по идее 1. И второй вопрос в том, как проще всего считать их длины, но мне бы для начала с кол-вом циклов разобраться. Последний раз редактировалось kappa937; 31.03.2015 в 15:52. |
31.03.2015, 16:50 | #4 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
1. https://ru.wikipedia.org/wiki/Поиск_в_глубину
2. http://neerc.ifmo.ru/wiki/index.php?...88%D0%B8%D0%BD 3. Мне кажется помечать нужно не ребра, а вершины. |
01.04.2015, 17:15 | #5 |
Пользователь
Регистрация: 15.12.2013
Сообщений: 42
|
Попытался написать с учетом теории.
Код:
Код:
Находит в данном случае 8 циклов. Хотя их 3. Как я понял, в условии if(color[r]==GRAY) не учитывается, что это та вершина, из которой пришли (например 3-1 и 2-1 считает за циклы) Подскажите, как исправить? |
01.04.2015, 20:05 | #6 |
Пользователь
Регистрация: 15.12.2013
Сообщений: 42
|
может кто помочь?
|
01.04.2015, 21:07 | #7 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Почему 3?
Их тут дофига Граф неориентированный (у нас не дуги, а ребра.. и движемся в обе стороны) Поэтому 1-2-1 уже цикл |
01.04.2015, 22:32 | #8 |
Пользователь
Регистрация: 15.12.2013
Сообщений: 42
|
Poma][a, просто по заданию нужно учитывать только вот такие циклы:
|
02.04.2015, 13:15 | #9 |
Тот ещё
Старожил
Регистрация: 14.11.2007
Сообщений: 2,242
|
М-дя. Я если честно в Си не очень, да и логика не очень ясна. Каждый вложеный вызов у тебя перекрашивает по своему и при выходе на уровень выше в ячейках уже не то, что нужно было в текущей итерации.
Или я вообще ни чё не понял... // Добавлено --------------------------------------------------- Блин. Интересно, но времени мало. Вчера перед сном посмотрел. Короче Пост #5 - это как в вики, обход в глубину. Он не ищет кол-во циклов, а определяет их наличие впринципе. Здесь в amount оказывается что-то типа - кол-во ячеек входящих в цикл. На делфе накида вот такое: Код:
Доделать не успел. Но вроде нужно так: Пройтись по всем не "Исследованным" ячейкам и найти для них все пути обратно (из ячейки U в U если путь длиннее чем 2) помечая их после как "Исследованные". Последний раз редактировалось Sibedir; 03.04.2015 в 06:20. |
04.04.2015, 17:29 | #10 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Могу предложить только такой вариант : сделать еще одним параметром bfs'a массив, который будет хранить наименьший путь до вершин. Если мы на некотором этапе получаем, что мы уже были в вершине K. То смотрим в наш массив, и если там число 6 или 8, или 4, то увеличиваем счетчик.
Но такое счастье нужно сделать для всех вершин.. Сложность O(N^3) |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как найти максимальный подграф или клику в неориентированном графе?(PASCAL)) | Artur1992 | Помощь студентам | 0 | 17.02.2011 16:31 |
Поиск в глубину и ширину в неориентированном графе | ya chef | Помощь студентам | 0 | 20.11.2010 18:25 |
В графе найти все его четырехвершинные полные подграфы[PROLOG] | Bruster | Помощь студентам | 1 | 24.12.2009 09:55 |