Форум программистов, компьютерный форум CyberForum.ru

Поиск ободов в графе - C++

Восстановить пароль Регистрация
 
darthw
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
28.12.2009, 07:35     Поиск ободов в графе #1
К сожалению не получается решить эту задачу на Си.
Вот исходный текст задачи:
"Найти в графе все подграфы, которые являются ободами".
К сведению обод это подграф имеющий 3 и более вершины причем vn входит в v0. Ну, в общем, ясно, что это цикл. Однако не получается найти их ВСЕ в графе..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2009, 07:35     Поиск ободов в графе
Посмотрите здесь:

C++ поиск циклов в графе
Поиск на графе C++
C++ Поиск в ширину на графе
Поиск Ф-циклов в графе C++
C++ Поиск отрицательых циклов в графе
Поиск циклов в графе. Поиск центра взвешенного графа C++
C++ Перебор/поиск с возвратом в графе
C++ Поиск мостов в графе

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
solar_wind
 Аватар для solar_wind
740 / 731 / 39
Регистрация: 06.07.2009
Сообщений: 2,937
Завершенные тесты: 1
28.12.2009, 08:49     Поиск ободов в графе #2
Ну можно решить задачу через деревья.
Число вершин графа ограничено, так что от каждой точки графа строишь дерево обхода его вершин, исключая повторения. После этого ищешь по дереву вершины, которые находятся ниже 2-го уровня и связаны с начальной вершиной, это и будут циклы. Можно начальную вершину включать в дерево, и использовать как один из критериев остановки просмотра, тогда останется только найти все вхождения начальной вершины в дереве.
Ну а потом удаляешь повторы и выводишь.
Yandex
Объявления
28.12.2009, 08:49     Поиск ободов в графе
Ответ Создать тему
Опции темы

Текущее время: 11:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru